Fold Operators - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Programming : Data Types : Rtables, Arrays, Matrices, and Vectors : Functions : fold

Fold Operators

compose a binary operator

 

Calling Sequence

Parameters

Description

Examples

References

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, foldlrator,id,a,b,c=ratorratorratorid,a,b,c.

• 

The right-fold operator foldr is similar but associates operands from the right. For example, foldrrator,id,a,b,c=ratora,ratorb,ratorc,id.

• 

More formally, the left-fold operator foldl is defined recursively by foldlrator,id=id and foldlrator,id,e1,e2,...,en=foldlrator,ratorid,e1,e2,...,en for a positive integer n.

• 

Similarly, the right-fold operator foldr is defined recursively by foldrrator,id=id and foldrrator,id,e1,e2,en=ratore1,foldrrator,id,e2,,en 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

foldlF,id,a,b,c,d

FFFFid,a,b,c,d

(1)

foldrF,id,a,b,c,d

Fa,Fb,Fc,Fd,id

(2)

foldl`+`,0,a,b,c

a+b+c

(3)

foldl`and`,true,a,b,c

aandbandc

(4)

Define a dot product as follows.

dotu,v→foldl`+`,0,opzip`*`,u,v:

dot1,2,3,1,2,3

14

(5)

defineaF,'associative':

foldlaF,NULL,a,b,c

aFa,b,c

(6)

foldraF,NULL,a,b,c

aFb,c,a

(7)

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

myfoldlrator,id→`@`seqt→u→ratoru,targs[1+nargsi],i=1..nargs2id:

myfoldlF,id,a,b,c,d

FFFFid,a,b,c,d

(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

andn:=→foldland,true,args

(9)

andn

true

(10)

andna

a

(11)

andna,b

aandb

(12)

andna,b,c,d,e

aandbandcanddande

(13)

Compute horner forms using foldl.

psortrandpoly'x'

p:=7x5+22x455x394x2+87x56

(14)

foldla,b→ax+b,opmap2op,1,opp

7x+22x55x94x+87x56

(15)

Count the number of elements of a list.

countL→foldrx,n→1+n,0,opL

count:=L→foldrx,n→n+1,0,opL

(16)

counta,b,c,d,e

5

(17)

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

lreverseL→foldlu,v→v,opu,,opL

lreverse:=L→foldlu,v→v,opu,,opL

(18)

lreverse1,2,3,4,5

5,4,3,2,1

(19)

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

SumLenL→foldrn,u→n+u[1],1+u[2],0,0,opL

SumLen:=L→foldrn,u→n+u[1],1+u[2],0,0,opL

(20)

SumLen1,2,3,4,5

15,5

(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_ormapp,seqi,i=1..10

1

2

true

(22)

References

  

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

See Also

andmap

function

map

operator

ormap

procedure

seq

zip

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam