# Exploring Folds: A Powerful Pattern Of Functional Programming

## 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 = 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 `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], , [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 -> Dfn2 : B -> Cfn3 : 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?