Exploring Folds: A Powerful Pattern Of Functional Programming

With examples in Javascript

Introduction

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 map and filter functions in Javascript or Linq operators in C#.

For me, FP is all about identifing patterns in our code and extract these patterns into functions. Folding is one of these delightful patterns. You most likely have used folding one way or the other. In Javascript, it is implemented as 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 reduce from Javascript. Once we have the definition, we will explore the many many functions you can derive just from the fold function.

I will be using Javascript for this article but the ideas will work with any language. In fact, it should be a fun exercise to follow along with your language of choice and implement the same functions represented here in that language.

Back To Basics

We will now take a look at some simple programming tasks. Imagine you were given the task of summing up the numbers of a list. For example the sum of [1, 2, 3] = 1+ 2 + 3 = 6. In Javascript, you might write the following:

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 (totalSum, result, totalCount etc.) 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 true:

times(1, x) = 1 * x = x
and(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 fold function:

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 fold :

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), forAll becomes:

What about checking whether or not some of the elements of a list match a creteria? We follow the same logic of the forAll function:

Here, the Operation was the || (or) function and Identity Value was false because or(false, x) = false || x = x.

Another application is merging a list of lists into one list (concatenating lists). For example merging [[1, 2], [3], [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 fold.

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 undefined for an empty array which is somewhat acceptable if you are using javascript. But if you are using a statically-typed language, please make sure to include that information in the output type of function. Totality of functions is important when working with functions for getting the expected results.

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 max and min from both functions maximum and minimum .

So you think you can fold?

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:

Time to 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 g .

Although it may not be obvious because we are using Javascript, all the functions were of type 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

Where A, B, C and D could be any type.

The resulting function from the fold would be:

and the type of ouputFn is 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 plus Operation:

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
  • Associativity: operation(x, operation(y, z)) == operation(operation(x, y), z)
  • Existence of an Inverse Element for each other element x such that 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?

Furthur Reading

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.

The End

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!