## Folds

### February 2, 2018

Folds, in the parlance of functional programming, are a way to convert lists to a value of some other type; a fold applies a function pair-wise to each element of a list and an accumulator, then returns the accumulator when the list is exhausted. The fundamental fold is `foldr`

:

foldr f a [x1, x2, ..., xn] = f x1 (f x2 (... (f xn a)...))

Here, *f* is a function with two arguments, *a* is an initial value, and `[x1, x2, ..., xn]`

is the input list. The name `foldr`

stands for “fold right”, because the parentheses stack on the right side of the expansion, the items in the list are processed right-to-left, and the accumulator is on the right side of the binary function. `Foldl`

is similar:

foldl f a [x1, x2, ..., xn] = (...((f a x1) x2) ... xn)

The arguments have the same meaning, with “fold left” referring to the fact that the parentheses stack on the left, the items in the list are processed left-to-right, and the accumulator is on the left side of the binary function. Note that foldl and foldr have different types, because the binary function takes its arguments in opposite order. In some cases, that makes a difference; for instance, when *f* is `cons`

, you must use `foldr`

. But when the function is associative, such as `+`

, you can use either `foldl`

or `foldr`

. Here are some examples:

foldr + 0 [1,2,3,4] → 10 foldl + 0 [1,2,3,4] → 10 foldr cons [] [1,2,3,4] → [1,2,3,4] foldl cons [] [1,2,3,4] → [[[[[],1],2],3],4] foldr plusone 0 [1,2,3,4] → 4 foldl snoc [] [1,2,3,4] → [4,3,2,1]

Sometimes there is no obvious starting value. For instance, if you want to find the maximum item in a list, there is no “guaranteed to be less than anything else” value to use for *a*. In that case you can use the `foldl1`

and `foldr1`

variants that take the first item in the list as the initial value. Here, `max`

is a binary function that takes two numbers and returns the larger; it is applied pair-wise at each item in the list (we ignore the fact that the built-in `max`

can take more than two arguments):

foldr1 max [1,2,3,4] → 4 foldl1 min [1,2,3,4] → 1

Related to `foldl`

is `scan`

, which applies `foldl`

to every initial segment of a list:

scan f a [x1, x2, ..., xn] = [a, f(a, x1), f(f(a, x1), x2), ..., f(f(f(a, x1), x2), x3)]

For instance:

scan + 0 [1,2,3,4] → [0,1,3,6,10] scan snoc [] [1,2,3,4] → [[], [1], [2,1],[3,2,1],[4,3,2,1]]

Your task is to implement all the various folds shown above; if your language provides them natively, you should re-implement them from first principles. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Here’s a fully tail-recursive solution in standard R7RS Scheme.

Here’s a solution in C.

Output:

Folds make sense for any algebraic data type, so we can fold over trees, for example:

Implementation of the various derived folds is left as an exercise.

Here’s one that takes a two-argument function:

Here’s some Haskell…