Higher-Order Functions on Lists II: Folds

In addition to map and filter from the last lesson, there is a third ubiquitous higher-order function on lists: the fold (or reduce) operation that reduces a list to a single value.

List folds

Let’s first look at a few examples of this reduction pattern. The first one is a function which reduces a list of integers to their sum. It is defined in the Haskell Prelude as sum.

sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs

The sum function operates by providing an initial sum of 0 for the empty list, and then successively adding list elements.

The second example is the concat function (also from the Prelude) which operates on a list of lists and returns a single flattened list with all the elements of the list of lists.

concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss

Again this function accumulates the result by starting with the empty list and successively appending the elements of each list in the input.

The general recursion pattern captured by these functions is:

1. The input is a list with elements of type a and the output is a value of type b.
2. There is a base value z (e.g. 0, []) which is the result on the empty list.
3. The final result is computed by going over the input list element by element and modifying an accumulator. Starting with the base value z as the accumulator, a folding function f (e.g. +, ++) is used to combine the accumulator with successive list elements.

This pattern is captured by the foldr function from the Prelude. Here is its implementation on lists:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

In many cases, the output type b is the same as the list element type a, and we can see foldr as a reduction of the list to a single value. This is also where the name fold originates: the idea is to successively fold together the linear list to a single value, like folding a piece of paper.

The function sum and concat from above can be written succinctly as: