Fold you so

Jul 10, 2015
functional-programming
haskell

The ultimate structure-reducing functions.

Image of a folding structure in nature.

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:

sum' [] = 0
sum' xs = head xs + sum' (tail xs)
product' [] = 1
product' xs = head xs * product' (tail xs)

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

f [] = v
f xs = head xs ⊕ f (tail xs)

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:

foldr ⊕ v [x1, x2, ..., xn] = x1 ⊕ (x2 ⊕ (...(xn ⊕ v)...))

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:

sum' = foldr (+) 0
product' = foldr (*) 1

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

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr ⊕ v [] = v
foldr ⊕ v xs = head xs ⊕ (foldr ⊕ v (tail xs))

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:

foldr :: (a -> a -> a) -> a -> [a] -> a

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:

foldl ⊕ [] = v
foldl ⊕ [x1, x2, ..., xn] = ((...(v ⊕ xn)...⊕ x2) ⊕ x1)

The recursive pattern abstracted by foldl looks like this:

f v [] = v
f v xs = f (v ⊕ head xs) (tail xs)

So its implementation along with its type signature must be:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl ⊕ v [] = v
foldl ⊕ v xs = foldl ⊕ (v ⊕ head xs) (tail xs)

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:

foldl :: (a -> a -> a) -> a -> [a] -> a

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:

foldl ⊕ v xs = foldr ⊕ v xs

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.