# Fold you so

The ultimate structure-reducing functions.

Photo by Timothy Dykes under the Unsplash license

A higher-order function is a function that receives a function as a parameter and/or returns a function as its result.

The **fold** family of functions apply an operator over a data structure in a single pass. They are present in many languages, sometimes with a different name of such as **reduce**.

Depending on how the operation is grouped when traversing the list there are two variants of a fold:

- fold-right (
`foldr`

) where the operation groups to the right. - fold-left (
`foldl`

) where the operation groups to the left.

## Foldr

Letβs start with the simplest one and take a look to the following functions:

Can you spot a common pattern in those functions? Can you spot the differences with this:

Correct! there are no differences! So, wouldnβt be nice that we abstracted the previous functions pattern? Well, we can do that it, and we call the abstraction `foldr`

:

Visually, applying `foldr`

to a list looks like this:

now you should have a clue on why it is called foldr because it groups the operations to the right. Using it, we can re-implement the above functions in this way:

Now, letβs see the implementation of foldr along with its type signature:

What conclusions do we can get from it? Letβs see:

`foldr`

is a recursive function.`v`

is used as the result when the list is empty.`β`

has to be a binary function (an operator), thatβs what`a -> b -> b`

means.`β`

first parameter is of type a so it has to be an element of the list because the list has type`[a]`

.`β`

second parameter is of type b so it has to be v because thatβs the type of, well, v, moreover, its result is also of type b which is telling us that the result is used as a new`v`

.

Our examples have something else in common, letβs first see whatβs the definition of a **Monoid**:

In abstract algebra, a branch of mathematics, a Monoid is an algebraic structure with a single associative binary operation and an identity element. β Wikipedia

In our examples `(+)`

is an associative operation and zero itβs its identity element, so we say that natural numbers form a Monoid under addition. The same happens with `(*)`

and one.

Whenever `β`

and `v`

form a Monoid, we can state `foldr`

will have the type:

## Foldl

We already know about `foldr`

and we know it groups the operation to the right, so letβs define a `foldl`

that instead groups the operation to the left:

The recursive pattern abstracted by foldl looks like this:

So its implementation along with its type signature must be:

## Similarities between foldr and foldl

As you have seen `foldr`

and `foldl`

functions are very similar, in fact, as with `foldr`

, when `β`

and `v`

form a monoid we can state its type will be:

so in the presence of a Monoid `foldr`

and `foldl`

have both the **same** type. This guides us to what is called the first **duality theorem**:

whenever `β`

and `v`

form a Monoid and `xs`

is a finite list.

So our example functions, sum and product, can be implemented using any of the two because of the first duality theorem, and whenever this is the case, using `foldl`

is going to result in a more efficient solution since its algorithm is tail recursive.