# wwblog Willie Wheeler's personal blog. Mostly tech.

In Four Flavors of Functional Programming with Map and Filter we looked at `map` and `filter`, two higher-order functions for list processing. This time around we'll look at folding, which has two main varieties. The first is called `foldl`, or left fold, and it processes the list from left to right. The other is `foldr` and has the corresponding behavior.

## foldl

The idea with folding is that sometimes we want to process a list in such a way as to yield some accumulated result. For example, if we have a list of numbers, then we might want to calculate their sum. Now we can certainly do this without folding. Here's a recursive approach:

``````sum' :: (Num a) => [a] -> a
sum' [] = 0
sum' [x] = x
sum' (x:xs) = x + sum' xs
``````

Here's one way to do this with `foldl`:

``````foldlSum :: (Num a) => [a] -> a
foldlSum xs = foldl (\acc x -> acc + x) 0 xs
``````

`foldl` takes three arguments:

• A two-arg step function to step through the list, folding the current element into the accumulated value. The first argument is the accumulator and the second is the element we're processing.
• An initial value for the accumulation.
• A list.

At the end `foldl` returns the accumulated value.

The step function combines a given list element with the current accumulated value to produce a new accumulated value. In the example above it simply adds the list element `x` to `acc`.

Using partial application we can simplify the definition a bit:

``````foldlSum :: (Num a) => [a] -> a
foldlSum = foldl (\acc x -> acc + x) 0
``````

Also, since our lambda expression is really just a sum, we can recast `foldlSum` more economically as

``````foldlSum :: (Num a) => [a] -> a
foldlSum = foldl (+) 0
``````

That makes it clear what this function is doing. Basically it says to initialize the sum at 0, and gobble up list elements from the left, accumulating using `(+)`.

## foldr

I mentioned above that there's a `foldr` function that processes the list from right to left. Given the examples above, you might wonder what difference it makes. Whether we compute the sum from left to right or right to left, the result is the same, and the performance characteristics are the same.

It turns out though that there are cases where `foldr` is helpful. One kind of example is where we're generating a list. (Note that folding isn't restricted to generating scalars—we can generate lists or really anything else.) Suppose that we wanted to take a list and duplicate every element, so that [3, 4, 3, 1, 0] becomes [3, 3, 4, 4, 3, 3, 1, 1, 0, 0]. Here's how we can do this with `foldl` (again taking advantage of partial application):

``````foldlDupList :: [a] -> [a]
foldlDupList = foldl (\acc x -> acc ++ [x] ++ [x]) []
``````

This works, but we can do better. It is less expensive to build our list using `:` (prepending, or "consing") than it is using `++` (concatenation). But to do this we would need to use `foldr` to start from the right, and keep prepending the processed element to the accumulated list:

``````foldrDupList :: [a] -> [a]
foldrDupList = foldr (\x acc -> x: x: acc) []
``````

Note that with `foldr`, the step functions arguments are reversed: that is, the first argument is the processed element, and the second is the accumulated value.

## foldl1 and foldr1

One interesting case is computing a maximum (or minimum). Take a look at this:

``````foldlMax :: (Ord a) => [a] -> a
foldlMax [] = error "empty list"
foldlMax (x:xs) = foldl step x xs
where step acc x
| x >= acc  = x
| otherwise = acc
``````

Notice that here we used the first element `x` as an initial value. That makes sense since we can't arbitrarily choose 0 as the maximum. (The list might contain only negative numbers.) Haskell has a special version of `foldl` called `foldl1` that initializes the accumulator with the first element of the list. Likewise there's a `foldr1` function that initializes the accumulator with the last element of the list. With `foldl1` we can define a new max function as follows:

``````foldl1Max :: (Ord a) => [a] -> a
foldl1Max = foldl1 max
``````

As you can see, using `foldl1` (and `foldr1`) can significantly clean up a function definition for the common case were we want to initialize the accumulator with an existing list element.