Fold Operators - Maple Programming Help

Fold Operators

compose a binary operator

 Calling Sequence foldl(rator, id, r1,r2, ...) foldr(rator, id, r1, r2, ...)

Parameters

 rator - operator to apply id - identity or initial value r1, r2, ... - (optional) operands for the call

Description

 • 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.

Examples

 > foldl( F, id, a, b, c, d );
 ${F}{}\left({F}{}\left({F}{}\left({F}{}\left({\mathrm{id}}{,}{a}\right){,}{b}\right){,}{c}\right){,}{d}\right)$ (1)
 > foldr( F, id, a, b, c, d );
 ${F}{}\left({a}{,}{F}{}\left({b}{,}{F}{}\left({c}{,}{F}{}\left({d}{,}{\mathrm{id}}\right)\right)\right)\right)$ (2)
 > foldl( +, 0, a, b, c );
 ${a}{+}{b}{+}{c}$ (3)
 > foldl( and, true, a, b, c );
 ${a}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{b}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{c}$ (4)

Define a dot product as follows.

 > dot := ( u, v ) -> foldl( +, 0, op( zip( *, u, v ) ) ):
 > dot( [ 1, 2, 3 ], [ -1, -2, -3 ] );
 ${-14}$ (5)
 > define( aF, 'associative' ):
 > foldl( aF, NULL, a, b, c );
 ${\mathrm{aF}}{}\left({a}{,}{b}{,}{c}\right)$ (6)
 > foldr( aF, NULL, a, b, c );
 ${\mathrm{aF}}{}\left({b}{,}{c}{,}{a}\right)$ (7)

Although it is not implemented this way, the left-fold operator can be written as one line in Maple.

 > myfoldl:=(rator,id)->@(seq((t->(u->rator(u,t)))(args[1+nargs-i]),i=1..nargs-2))(id):
 > myfoldl( F, id, a, b, c, d );
 ${F}{}\left({F}{}\left({F}{}\left({F}{}\left({\mathrm{id}}{,}{a}\right){,}{b}\right){,}{c}\right){,}{d}\right)$ (8)

A typical use of the fold operators is in the implementation of n-ary variants of binary operators. The and operator in Maple accepts only two arguments. A version that accepts any number of arguments can be implemented by using a fold operator as follows. Note that it does not matter which one is used, given that and is associative.

 > andn := () -> foldl( and, true, args );
 ${\mathrm{andn}}{≔}\left(\right){↦}{\mathrm{foldl}}{}\left({\mathrm{and}}{,}{\mathrm{true}}{,}{\mathrm{args}}\right)$ (9)
 > andn();
 ${\mathrm{true}}$ (10)
 > andn( a );
 ${a}$ (11)
 > andn( a, b );
 ${a}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{b}$ (12)
 > andn( a, b, c, d, e );
 ${a}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{b}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{c}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{d}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{\mathbf{and}}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{e}$ (13)

Compute horner forms using foldl.

 > p := sort( randpoly( 'x' ) );
 ${p}{≔}{-}{7}{}{{x}}^{{5}}{+}{22}{}{{x}}^{{4}}{-}{55}{}{{x}}^{{3}}{-}{94}{}{{x}}^{{2}}{+}{87}{}{x}{-}{56}$ (14)
 > foldl( (a,b) ->a*x+b, op(map2(op,1,[op(p)])));
 $\left(\left(\left(\left({-}{7}{}{x}{+}{22}\right){}{x}{-}{55}\right){}{x}{-}{94}\right){}{x}{+}{87}\right){}{x}{-}{56}$ (15)

Count the number of elements of a list.

 > count := L -> foldr( (x,n) -> 1+n, 0, op( L ) );
 ${\mathrm{count}}{≔}{L}{↦}{\mathrm{foldr}}{}\left(\left({x}{,}{n}\right){↦}{n}{+}{1}{,}{0}{,}{\mathrm{op}}{}\left({L}\right)\right)$ (16)
 > count( [a,b,c,d,e] );
 ${5}$ (17)

Reverse a list. Note that this is not the fastest method.

 > lreverse := L -> foldl( (u,v) -> [v,op(u)], [], op(L) );
 ${\mathrm{lreverse}}{≔}{L}{↦}{\mathrm{foldl}}{}\left(\left({u}{,}{v}\right){↦}\left[{v}{,}{\mathrm{op}}{}\left({u}\right)\right]{,}\left[\right]{,}{\mathrm{op}}{}\left({L}\right)\right)$ (18)
 > lreverse( [1,2,3,4,5] );
 $\left[{5}{,}{4}{,}{3}{,}{2}{,}{1}\right]$ (19)

By generating lists, you can compute more than one quantity at a time.

 > SumLen := L -> foldr( (n,u) -> [n+u[1],1+u[2]], [0,0], op( L ) );
 ${\mathrm{SumLen}}{≔}{L}{↦}{\mathrm{foldr}}{}\left(\left({n}{,}{u}\right){↦}\left[{n}{+}{{u}}_{{1}}{,}{1}{+}{{u}}_{{2}}\right]{,}\left[{0}{,}{0}\right]{,}{\mathrm{op}}{}\left({L}\right)\right)$ (20)
 > SumLen( [ 1, 2, 3, 4, 5 ] );
 $\left[{15}{,}{5}\right]$ (21)

The following example demonstrates an efficient way to test whether a particular predicate returns true for some member of a set or list. The example uses careful sequencing of automatic simplifications and Maple's evaluation rules (which include McCarthy rules for the evaluation of the Boolean operators and and or) to ensure that the procedure returns as early as possible.

 > 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:
 > my_ormap( p, [ seq( i, i = 1 .. 10 ) ] );
 ${1}$
 ${2}$
 ${\mathrm{true}}$ (22)

References

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