For Jacob Stanley, who introduced me to wonderful insights and neat ideas in every conversation we had without making me feel stupid. Thank you!
Functional Programming (FP) can sometimes be seen as a bit of a black art.
This short series of posts helps to demystify some of these concepts, shows some neat symmetries and patterns, and provides a real-life practical example where FP indeed makes life easier.
My hope is that at least one person will be inspired to take their first steps digging into FP after reading this series.
Functions as mappings
Most programming languages support functions as a kind of sub-routine returning a computed value. This is a useful introductory way of getting some intuition around them, but functional programmers take things a step further - they lean on the mathematical definition of functions, and aim to derive some benefits from building on this foundation.
From a mathematical perspective, a function is nothing more than a mapping between an input set and an output set. That is, the function represents a transformation for every element in an input set to some element in an output set.
This may seem an overly restrictive definition, but let’s explore what that really means:
- Each element of the input set is mapped to a single element in the output set. This, for example, implies that once we have computed the output of a given input, we would never need to do the computation again - we could just store the (input, output) pair and refer to that instead. This can have profound implications in how we write our programs - but that is really another story for another day.
- The function does nothing more than transform an input element to an output. This means no side-effects can take place in the function - no missile-launches, no calls to the internet, and, if we’re being super strict, no printing to the console. Many languages relax this rule for convenience sake, but some don’t. The ones that don’t allow us to write code that is significantly easier to reason about.
- Because there are no side-effects, the size of the mapping between a finite sized input set and a finite sized output set becomes definitely finite. It could still be a large number but it is definitely finite. Again, this can have profound implications, but it is a story for another day.
I’ll be using
F# to demonstrate these concepts in this series of posts. F# does relax the no side-effect rule, but we’ll just be strict by convention and not put in side-effects to illustrate the benefits.
Here’s how you define a function in F#. This function computes whether a given
byte is even.
Type Signature of the function is:
isEven : byte -> bool. Read it as “isEven is a function that takes a
byte and returns a
As you can see, there are no side-effects in this function - so with sufficiently large memory (how much memory, exactly?), we could replace this function with a look-up table!
To extract a result from a function, we need to apply it to an input value. This input value is traditionally called an “argument”.
In F#, we can do this multiple ways. The first form might be more familiar to programmers of other langugages
Of course, the parantheses are optional in F#, so this is equivalent (and preferable)
However, F# has a more idiomatic way of “giving” an argument to a function. This is more than an intellectual curiosity, and it’s useful to learn this F# idiom.
You can read this as “
23 given to
The reason this is idiomatic in F# is that it provides for an elegant way to chain function applications:
Traditionally, this is done “maths-style” where you have read right-to left:
Written idiomatically, this reads more naturally (left-to-right and top-to-bottom) than the traditional way to chain applications.
Apart from readability, this way of “feeding” values to a transform leads to some neat symmetries, as we will see in the future.
If we continue with the perspective that a function is a transform between elements, then it follows that we can compose transforms together to make new transforms. When we compose two transforms, we get a single transform that goes from the input set of the first transform to the output set of the second - eliminating the intermediate set from the equation.
In F#, we can write
>> operator composes the functions in the given order and returns the composite function.
Let’s explore the relationship between
>> a little more. These expressions both evaluate to the same value:
Indeed, mathematically they are operationally equivalent, but the ability for us to compose functions means that we can compute and cache (and reason about) the composite function as a single entity.
Let’s look at composition again and figure out how to implement the composition operator:
Let’s take a closer look at the
(>>) function. It’s a transform between elements of an input set and an element of an output set. But these sets aren’t
bytes, as we have traditionally encountered. Hover over the
(>>) function and you’ll see that the type signature is a tad more complex:
The way to read that is “compose is a function that takes a function of type
('a -> 'b), and a function of type
('b -> 'c), and returns a function of type
('a -> 'c).
The first observation we can make is that there are sets of function, just like we have sets of int and byte.
Specifically, there is a set of functions that take
'b, which is denoted as the set of
('a -> 'b). Similarly, there are the sets of functions denoted
('b -> 'c) and
('a -> 'c).
(>>) is a transform that takes one member each from
('a -> 'b) and
('b -> 'c), and maps that pair to a member of
('a -> 'c).
It’s almost like stacking lego-blocks, so that you get a single block with twice the height. Of course, these blocks stack as high as you want, as long as you match up the output set with the input set of the next level.
The next observation is that we can implement
>> in terms of
|>. What this means is that chained application can be abstracted into function composition.
We have introduced a minimalistic, mathematically-founded intuition for how to view functions, and we have explored function application, function chaining, and function composition.
We have also introduced idiomatic F# constructs for each of these operations, and it is worth getting familiar with these idioms because patterns start emerging once we start playing with different input and output sets.
In the next post, we’ll talk about these sets and how important they are to programming.