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.
Unravelling the Mystery
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 \\ = ((n1)! \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 

Folding from different sides
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 

The following code nicely illustrates the three kinds of folds:
1 2 3 4 5 6 7 8 

Examplar Implementations
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 4merge [] 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 2mergesort :: (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:
1factorial = 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 8def fact num (1..num).inject { acc, i acc * i } end =begin Example: > fact 3 6 =end