Foldlist

LikeMapandFilter, foldlists are an important part of the list processor's, as well asfunctional programmer'stoolbox. 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.

评估的事实orial 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 Lprocedurally can be written like this

1 23 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 fora1: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 23 4 5 6 7 8 9

foldtfz[]=zfoldtf_[x]=xfoldtfzxs=foldtfz(pairsfxs)foldifz[]=zfoldifz(x:xs)=fx(foldifz(pairsfxs))pairsf(x:y:t)=fxy:pairsftpairs_t=t

The following code nicely illustrates the three kinds of folds:

1 23 4 5 6 7 8

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

Haskell

In haskell, we have alreadyfoldlandfoldralready defined in the prelude.

Once we have defined have definedfoldtas above and merge as follows

1 23 4

merge[]ys=ysmergexs[]=xsmergexs@(x:xt)ys@(y:yt)|x<=y=x:mergextys|otherwise=y:mergexsyt

we could implementMergeSortthis way:

1 2	mergesort::(Orda)=>[a]->[a]mergesortxs=foldtmerge[][[x]|x<-xs]

Python

In python, thereducefunction 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=lambdan:reduce(lambdaa,b:a*b,xrange(1,n+1))

In Python 3, thereducefunction has been removed from the standard library. One needs toimport functoolsto use it.

Ruby

Factorial implementation in Ruby.

1 23 4 5 6 7 8

deffactnum(1..num).inject{|acc,i|acc*i}end=beginExample:> fact 36=end