Exploring Folds: A Powerful Pattern Of Functional Programming
When learning functional programming (FP) for the first time, you might have heard about different definitions of what FP means. Some people will name a few concepts from FP (partial application or function composition for example), others will try to explain by using the
reduce function for arrays.
In this article, we will take a close look at a couple of programming tasks, identify what they have in common (the pattern) and eventually extract that pattern into a function. Basically, we will implement the
fold function from scratch which is very similar to
Back To Basics
Alright, that wasn’t too hard. Now I want to find the product of the numbers of the list. For example the product of [1, 2, 3, 4, 5] = 1 * 2 * 3 * 4 * 5 = 120:
What about counting the number of elements in a list (assuming we don’t want to use the
length property directly):
So far so good. Another (less intuitive) task is finding whether or not a list of booleans is made out of
true values only:
Now, before moving on, take a second to think about what all these examples have in common. Do you see what we are doing everytime?
- We have the Initial Value (
totalCountetc.) that we are defining at the very beginning. This initial value is also called the Identity Value or the Neutral Element.
- We are going through all the elements within the input list (traversing the list).
- We are doing an Operation inside the for-loop and accumulating the result before returning it.
What do I mean by “operation” ? Well for
sum function, the operation was the
+ (plus) function because you are adding every element of the list and the accumulating the value that you return eventually. For the
product function, the operation was the
* (times) function. For the
count function, the operation was still the plus function, only now, we just ignore the current element of list and add the number one instead to the accumulator. Notice that these operations are functions accepting two parameters (binary functions): the accumulated result and the current element of the list. The Operation functions must produce a new value.
The Relationship between the Operation and the Identity Value
The choice of the Identity Value, as you might have guessed, is not random. There is a relationship between the Operation you are using and the Identity Value: Assume the operation is any binary function called
operation and the Identity Value is called
identity , then you can deduce the Identity Value from the relationship:
operation(identity, x) = x
Therefore, it follows that the Identity Value for the
+ (plus) Operation is 0 because:
plus(0, x) = 0 + x = x
The same holds for the
* (times) Operation, with Identity Value of 1 and the
&& (and) operation with identity value of
times(1, x) = 1 * x = xand(true, x) = true && x = x
Extracting the common parts and the definition of Fold
Now that we understand what the examples represented above have in common, we can extract the main two things into parameterr: the Identity Value and the Operation. By doing this, we get our
We will not abstract the array traversal part (looping through the array) because we want to fold arrays. But folds can be more general and work with other structures such as binary trees.
You can now define all of the previous functions, in terms of
Pretty cool, isn’t it? Actually, while we are at it, the
forAll function is more useful when you you want to check whether or not all of the elements of a list match a certain creteria
p (short for predicate),
What about checking whether or not some of the elements of a list match a creteria? We follow the same logic of the
Here, the Operation was the
|| (or) function and Identity Value was
or(false, x) = false || x = x.
Another application is merging a list of lists into one list (concatenating lists). For example merging [[1, 2], , [4, 5, 6]] into [1, 2, 3, 4, 5, 6]. First of all you will need the Operation of merging only two lists into one and then you need the Identity Value. The Operation of merging two lists together might look something like this:
We got our binary function, can you guess what the Identity Value would be? An empty list maybe?
mergeLists(, anotherList) = anotherList
Then the definition of concatenating lists becomes:
Ofcourse I could have defined
concatLists using a double for-loop but where is the fun in that when you can
No ID Required . . . Sometimes
For some cases,
fold will work without an Identity Value predefined, for these cases, the identity value will just be the first element of the array. Notice that we are assuming the array is non-empty. An example of these cases would be finding the maximum or minimum value of the array, again using
fold. The Operation would still be a binary function producing a value. Let’s define a function
maximum that returns the maximum number of a list. For example the max of [1,2, 5, 9, 3] is 9.
Ofcourse, this function will return
Following the same logic, you can implement the other side of coin to find the
minimum value of an array:
Notice the difference between the operations
min from both functions
So you think you can
So far we have mostly worked with numbers because there are obvious ways of combining them (adding and multiplying). But we have also worked with booleans, which might have given you the idea that
fold could also work with other types of elements.
In essense, eveytime you want to
fold any array, you will only need an operation of combining two elements of that array into a third one and an identity element such that when combinding that identity element with an element of the array, just returns that same element of the array.
One special group of elements I want to examine now and try to fold is the group of functions themselves! Can we fold them? Ofcourse, this is FP after all. You can fold a list of functions into one as long as you have an Operation to combine them. You probably know that function composition can be used to combine two functions and produce a third one, so that qualifies for being an appropriate Operation:
Next you need an Identity Element. Hmm, what would be the identity element of functions? you need to find a function
f such that:
compose(f, g) = g
That would be the Identity function: a function that just returns the input it gets:
fold, the output function we get is a function such that the input of that function would go through all the functions of the list. We will these simple functions:
Now, to fold all these functions, we will create a function
composeMany that takes a list of functions and combine them all into one function. Notice that because the way we defined
compose such that it first evaluates function
g and then
f ,we will be evaluating these functions in the list from the left to the right:
Nice! As you can see, the functions are evaluated from left to right. If you wanted to evaluate them from right to left, you would have to change the definition of
compose to evaluate the
f function first, then
number -> number , which means they take in a number as input and return a number as output. This is very important when we are doing function composition and it matters whether or not we are folding the functions from right to left or from left to right. This is because the types have to match up. For example, given that you want to
fold the list of functions
[f1, f2, f3] , then the types of these functions would have to be the following:
fn1 : C -> D
fn2 : B -> C
fn3 : A -> B
D could be any type.
The resulting function from the
fold would be:
and the type of
A -> D .
Function composition is just one way of combining two functions into a third one. When working with functions of type
number -> number it is even easier because we can use the Operations and Identity Values of the type
number and apply them to functions of type
number -> number . Here is an example with adding two function (using the
+ Operation on their output):
The Identity Value in this case will not be the identity function (check for yourself that it would not work), but rather a function that returns the Identity Value of the
Now it follows
plusFn(plusIdentity, anotherFunction) = anotherFunction
Folds and Group Theory
Without a doubt, folds go way beyond the examples I have shown you in this article: simply because there many many structures that form a group. A group is a set of things where you have an Operation and an Identity Element and some other constraints:
- Closure: the result value of the Operation must of the same type of the input values
operation(x, operation(y, z)) == operation(operation(x, y), z)
- Existence of an Inverse Element for each other element
operation(inverse_of_x, x) = identity
Can you verify which of the examples of fold we have seen form a group with these other constraints?
I highly recommend reading the paper “A tutorial on the universality and expressiveness of fold” by Graham Hutton where the he explains the full extent of fold. Ofcourse, picking up A Book of Abstract Algebra should be interesting if you are into the theoritical stuff.
Next time you see a list of things, ask yourself: “Can I fold it?” You probably can. That was it for today, if you liked this article, hit the 💚 button and share!