The left-fold operator foldl composes a binary operator rator, with identity or initial value id onto its arguments r1,r2,... (which may be zero in number), associating from the left. For example, given three arguments a, b, and c, and initial value id, $\mathrm{foldl}\left(\mathrm{rator}\,\mathrm{id}\,a\,b\,c\right)=\mathrm{rator}\left(\mathrm{rator}\left(\mathrm{rator}\left(\mathrm{id}\,a\right)\,b\right)\,c\right)$.

The right-fold operator foldr is similar but associates operands from the right. For example, $\mathrm{foldr}\left(\mathrm{rator}\,\mathrm{id}\,a\,b\,c\right)=\mathrm{rator}\left(a\,\mathrm{rator}\left(b\,\mathrm{rator}\left(c\,\mathrm{id}\right)\right)\right)$.

More formally, the left-fold operator foldl is defined recursively by $\mathrm{foldl}\left(\mathrm{rator}\,\mathrm{id}\right)=\mathrm{id}$ and $\mathrm{foldl}\left(\mathrm{rator},\mathrm{id},e_1,e_2,...,e_n\right)=\mathrm{foldl}\left(\mathrm{rator},\mathrm{rator}\left(\mathrm{id},e_1\right),e_2,...,e_n\right)$ for a positive integer n.

Similarly, the right-fold operator foldr is defined recursively by $\mathrm{foldr}\left(\mathrm{rator}\,\mathrm{id}\right)=\mathrm{id}$ and $\mathrm{foldr}\left(\mathrm{rator},\mathrm{id},e_1,e_2\dots ,e_n\right)=\mathrm{rator}\left(e_1,\mathrm{foldr}\left(\mathrm{rator},\mathrm{id},e_2,\dots ,e_n\right)\right)$ for a positive integer n.

When the operator rator being folded is an associative binary operator, both the left-fold and right-fold operators produce the same result. However, foldl is more efficient than foldr.

The fold operators are useful for implementing operations of variable arity in terms of binary operations. See the and example in the Examples section.

$\mathrm{foldl}\left(F\,\mathrm{id}\,a\,b\,c\,d\right)$

$F\left(F\left(F\left(F\left(\mathrm{id}\,a\right)\,b\right)\,c\right)\,d\right)$

$\mathrm{foldr}\left(F\,\mathrm{id}\,a\,b\,c\,d\right)$

$F\left(a\,F\left(b\,F\left(c\,F\left(d\,\mathrm{id}\right)\right)\right)\right)$

$\mathrm{foldl}\left(\mathrm{`+`}\,0\,a\,b\,c\right)$

$a+b+c$

$\mathrm{foldl}\left(\mathrm{`and`}\,\mathrm{true}\,a\,b\,c\right)$

$a\mathbf{and}b\mathbf{and}c$

$\mathrm{dot}≔\left(u\,v\right)\mapsto \mathrm{foldl}\left(\mathrm{`+`}\,0\,\mathrm{op}\left(\mathrm{zip}\left(\mathrm{`*`}\,u\,v\right)\right)\right)\:$

$\mathrm{dot}\left(\left[1\,2\,3\right]\,\left[-1\,-2\,-3\right]\right)$

$\mathrm{-14}$

$\mathrm{define}\left(\mathrm{aF}\,'\mathrm{associative}'\right)\:$

$\mathrm{foldl}\left(\mathrm{aF}\,\mathrm{NULL}\,a\,b\,c\right)$

$\mathrm{aF}\left(a\,b\,c\right)$

$\mathrm{foldr}\left(\mathrm{aF}\,\mathrm{NULL}\,a\,b\,c\right)$

$\mathrm{aF}\left(b\,c\,a\right)$

$\mathrm{myfoldl}≔\left(\mathrm{rator}\,\mathrm{id}\right)\mapsto \left(\mathrm{`@`}\left(\mathrm{seq}\left(\left(t\mapsto u\mapsto \mathrm{rator}\left(u\,t\right)\right)\left(\mathrm{args}\left[1+\mathrm{nargs}-i\right]\right)\,i=1..\mathrm{nargs}-2\right)\right)\right)\left(\mathrm{id}\right)\:$

$\mathrm{myfoldl}\left(F\,\mathrm{id}\,a\,b\,c\,d\right)$

$F\left(F\left(F\left(F\left(\mathrm{id}\,a\right)\,b\right)\,c\right)\,d\right)$

$\mathrm{andn}≔\left(\right)\mapsto \mathrm{foldl}\left(\mathrm{`and`}\,\mathrm{true}\,\mathrm{args}\right)$

$\mathrm{andn}≔\left(\right)\mapsto \mathrm{foldl}\left(\mathrm{and}\,\mathrm{true}\,\mathrm{args}\right)$

$\mathrm{andn}\left(\right)$

$\mathrm{true}$

$\mathrm{andn}\left(a\right)$

$a$

$\mathrm{andn}\left(a\,b\right)$

$a\mathbf{and}b$

$\mathrm{andn}\left(a\,b\,c\,d\,e\right)$

$a\mathbf{and}b\mathbf{and}c\mathbf{and}d\mathbf{and}e$

$p≔\mathrm{sort}\left(\mathrm{randpoly}\left('x'\right)\right)$

$p≔-7x^5+22x^4-55x^3-94x^2+87x-56$

$\mathrm{foldl}\left(\left(a\,b\right)\mapsto a\cdot x+b\,\mathrm{op}\left(\mathrm{map2}\left(\mathrm{op}\,1\,\left[\mathrm{op}\left(p\right)\right]\right)\right)\right)$

$\left(\left(\left(\left(-7x+22\right)x-55\right)x-94\right)x+87\right)x-56$

$\mathrm{count}≔L\mapsto \mathrm{foldr}\left(\left(x\,n\right)\mapsto n+1\,0\,\mathrm{op}\left(L\right)\right)$

$\mathrm{count}≔L\mapsto \mathrm{foldr}\left(\left(x\,n\right)\mapsto n+1\,0\,\mathrm{op}\left(L\right)\right)$

$\mathrm{count}\left(\left[a\,b\,c\,d\,e\right]\right)$

$5$

$\mathrm{lreverse}≔L\mapsto \mathrm{foldl}\left(\left(u\,v\right)\mapsto \left[v\,\mathrm{op}\left(u\right)\right]\,\left[\right]\,\mathrm{op}\left(L\right)\right)$

$\mathrm{lreverse}≔L\mapsto \mathrm{foldl}\left(\left(u\,v\right)\mapsto \left[v\,\mathrm{op}\left(u\right)\right]\,\left[\right]\,\mathrm{op}\left(L\right)\right)$

$\mathrm{lreverse}\left(\left[1\,2\,3\,4\,5\right]\right)$

$\left[5\,4\,3\,2\,1\right]$

$\mathrm{SumLen}≔L\mapsto \mathrm{foldr}\left(\left(n\,u\right)\mapsto \left[n+u\left[1\right]\,1+u\left[2\right]\right]\,\left[0\,0\right]\,\mathrm{op}\left(L\right)\right)$

$\mathrm{SumLen}≔L\mapsto \mathrm{foldr}\left(\left(n\,u\right)\mapsto \left[n+u_1\,1+u_2\right]\,\left[0\,0\right]\,\mathrm{op}\left(L\right)\right)$

$\mathrm{SumLen}\left(\left[1\,2\,3\,4\,5\right]\right)$

$\left[15\,5\right]$

my_ormap := proc( pred::procedure, L::{list,set} )
    option    inline;
    eval(foldl( '`or`', false, op( map( ''pred'', L ) ) ))
end proc:

p := proc(n) print( n ); isprime( n ) end proc:

$\mathrm{my\_ormap}\left(p\,\left[\mathrm{seq}\left(i\,i=1..10\right)\right]\right)$

$1$

$2$

$\mathrm{true}$

Hutton, Graham. "A tutorial on the universality and expressiveness of fold." J. Functional Programming, Vol. 1(1). (January 1993): 1-17.