Foldlist

Like Map and Filter, foldlists are an important part of the list processor's, as well as functional programmer's toolbox. They let you digest a list and create a value that comes from the repeated application of the function on that list.

Folds maybe also called reduce, accumulate, aggregate, compress, or inject depending upon the language.

Intuitively, fold is like folding a chain (the list) from one end (left or right) with glue (the function) and producing just a compressed small thing (the output).

A possible example where you want to do is the factorial function.

To evaluate the factorial of $n$, you want to fold the list of integers from $1$ to $n$ with the multiplication function.

This actually means something like this: $(1 \times 2 \times 3 \times 4 \times \cdots n) \\ = (2 \times 3 \times 4 \times \cdots n) \\ = (6 \times 4 \times \cdots n) \\ \vdots \\ = ((n-1)! \times n) = n!$

What we mean by folding the list [1..n]with the (*) function is to apply it repeatedly to two selected elements and then apply the function to the previous result and the third element and so on.

Oh yes, foldl f z L procedurally can be written like this

1
2
3
4

init = z
FOR EACH x IN L:
   init = f(init, x)
return init

In case the operator is not associative, the result certainly depends on the direction in which the fold proceeds.

With the knowledge that every list written in the form [a1, a2, a3... aN] is just syntactic sugar for a1:a2:a3:...:aN:[] where [] is the empty list, the following illustrations should be sufficient to explain the left and right folds.

Note that $f$ is the function with which we are folding. $z$ is a initialisation value with which folding starts. It is often useful to use an identity element as $z$.

Folding could also take in a tree like fashion that one would define in haskell as follows:

1
2
3
4
5
6
7
8
9

foldt f z []     = z
foldt f _ [x]    = x
foldt f z xs     = foldt f z (pairs f xs)

foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))

pairs f (x:y:t)  = f x y : pairs f t
pairs _ t        = t

The following code nicely illustrates the three kinds of folds:

1
2
3
4
5
6
7
8

Prelude> putStrLn $ foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))

Prelude> putStrLn $ foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)

Prelude> foldt (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))

Haskell

In haskell, we have already foldl and foldr already defined in the prelude.

Once we have defined have defined foldt as above and merge as follows

1 2 3 4

merge [] ys = ys merge xs [] = xs merge xs@(x:xt) ys@(y:yt) | x <= y = x : merge xt ys | otherwise = y : merge xs yt

we could implement MergeSort this way:

1 2	mergesort :: (Ord a) => [a] -> [a] mergesort xs = foldt merge [] [[x] | x <- xs]

Python

In python, the reduce function serves the purpose of fold. Also, the initialization value is not mandatory in python.

One could define the factorial function the following way:

1	factorial = lambda n: reduce(lambda a,b : a*b, xrange(1,n+1))

In Python 3, the reduce function has been removed from the standard library. One needs to import functools to use it.

Ruby

Factorial implementation in Ruby.

1 2 3 4 5 6 7 8

def fact num (1..num).inject { |acc, i| acc * i } end =begin Example: > fact 3 6 =end