Skip to content

Folds

As said in the introduction of this chapter, a fold abstracts the idea of combining the elements in a container into a single value. Let's warm up by reviewing the foldl and foldr operations for lists.

We can add the elements in a list of numbers together:

GHCi
>>> sum [1,2,3,4]
10

or multiply them:

GHCi
>>> product [1,2,3,4]
24

A fold generalizes this. Consider how we would implement sum in Python:

def sum(xs):
    total = 0
    for x in xs:
        total += x
    return total

We have an accumulator total, which we initialize to 0, and then we add every element in the input list xs to total.

Similarly,

def product(xs):
    prod = 1
    for x in xs:
        prod *= x
    return prod

In general, the accumulator does not need to have the same type as the list elements, and we aren't restricted to addition and multiplication. To implement a fold over a list of as, what we need is an accumulator variable of type b, an initial value of type b (0 in the case of sum, 1 in the case of product), and a function that takes the current accumulator value and a list element to produce the new accumulator value. This was addition in the case of sum and multiplication in the case of product. Since the function takes the accumulator value of type b and a list element of type a to produce a new accumulator value of type b, this function must have the type b -> a -> b.

This general pattern is expressed in the following function type:

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

We want foldl f init xs to

  • Initialize the accumulator to init.
  • Take each element x in the list xs, from left to right, and update the accumulator value to the result of applying f to the current accumulator value and x.
  • Return the final accumulator value once we are done traversing the list.

This is exactly what the two Python implementations of sum and product do.

Here's how we implemented this in Haskell:

foldl f = go
  where
    go accum []     = accum
    go accum (x:xs) = go (f accum x) xs

With foldl in hand, we do not need to implement sum and product from scratch. We can simply use 0 as the initial value, and addition as the accumulation function f to obtain:

sum = foldl (+) 0

For product, we choose 1 as the initial value, and multiplication as the accumulation function f:

product = foldl (*) 1

Now, there was a reason why we called this function foldl, not fold. This function has a sibling called foldr. If you look at the implementation of foldl, it is obvious that it accumulates the list elements from left to right, from the beginning of the list to the tail. That's the l in foldl. foldr traverses the list in the opposite direction: it starts at the tail of the list. Here is how we implemented this:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f = go
  where
    go accum []     = accum
    go accum (x:xs) = f x (go accum xs)

For sums and products, the result is the same whether we accumulate from left to right or from right to left. That's because addition and multiplication are associative operators: \(x + (y + z) = (x + y) + z\) and \(x * (y * z) = (x * y) * z\). Other combinator functions may not be associative, so the direction of accumulation matters. For example,

GHCi
>>> foldr (/) 1 [1,2,4]
2.0
>>> foldl (/) 1 [1,2,4]
0.125

That's why it's important to have both foldl and foldr at our disposal.

Exercise

Figure out why the results of foldr (/) 1 [1,2,4] and foldl (/) 1 [1,2,4] are the ones shown above.

Solution

First foldl (/) 1 [1,2,4]:

This starts with the accumulator value being 1. Since foldl traverses the list left to right, the first thing we do is divide 1 by 1, which makes the "new" accumulator value 1 again. The next list element is 2. We divide 1 by 2 to get 1/2. Finally, we divide 1/2 by 4 to obtain 1/8 or 0.125.

Now foldr (/) 1 [1,2,4]:

We start with the accumulator value being 1. foldr traverses the list from right to left, and the order of the arguments to the accumulator function are being reversed. Thus, the first thing we do is divide 4 by 1. This gives the new accumulator value 4. Next we divide 2 by this value, which gives 0.5. Finally, we divide 1 by 0.5 to obtain 2.

Another way to say all this is that foldl (/) 1 [1,2,4] computes

\[((1 / 1) / 2) / 4 = 0.125\]

while foldr (/) 1 [1,2,4] computes

\[1 / (2 / (4 / 1)) = 2.\]

Both effectively build an expression that combines the operands in the list using the accumulator function (/). foldl adds the initial accumulator value at the left end of the sequence of operands and parenthesizes the expression from left to right. fldr adds the initial accumulator value at the right end of the sequence of operands and parenthesizes the expression from right to left.