Macaulay2 » Documentation
Packages » Macaulay2Doc :: fold
next | previous | forward | backward | up | index | toc

fold -- apply a binary operator repeatedly



Suppose L=\{x0, x1, ..., xn\}. Then for any binary operator f, fold(f, L) computes f(...f(f(x0, x1), x2), ...). In other words, the binary operator is applied to the first two elements of L, then to that result along with the next unused element of L, and so forth.

i1 : fold(plus, {0,1,2,3,4,5})

o1 = 15
i2 : fold(identity, {a,b,c,d,e})

o2 = ((((a, b), c), d), e)

o2 : Sequence
i3 : fold((i,j) -> i|j|i, {"a","b","c","d","e"})

o3 = abacabadabacabaeabacabadabacaba

If fold(f, x, L) is called, the element x is used as the first argument of the binary function f. In other words, fold(f, \{x0, x1, \ldots, xn\}) is equivalent to fold(f, x0, \{x1, \ldots, xn\}).

i4 : fold(plus, 0, {1,2,3,4,5})

o4 = 15
i5 : fold((x, y) -> x^y, 2, {3,2,1,2})

o5 = 4096

The function fold(\{x_0, x_1, \ldots, x_n\}, f) returns f...f(f(x_{n-2}, f(x_{n-1}, x_n))). That is, f is applied to the last two elements of the list first, then the repeated calls to f proceed backwards through the list. The optional argument x in fold(L, x, f) is used as the second argument in the first evaluation of f. So fold(\{x_0, x_1, \ldots, x_{n-1}\}, x_n, f) is equivalent to fold(\{x_0, x_1, \ldots, x_n\}, f).

i6 : fold({a,b,c,d,e}, identity)

o6 = (a, (b, (c, (d, e))))

o6 : Sequence
i7 : fold({a,b,c,d}, e, identity)

o7 = (a, (b, (c, (d, e))))

o7 : Sequence
i8 : fold({2,3,2,1}, 2, (x, y) -> x^y)

o8 = 512

If L is an instance of class the the iterator method installed, e.g., a string, then it may also be used with fold, but only the versions with f as the first argument.

i9 : fold(identity, "abcde")

o9 = ((((a, b), c), d), e)

o9 : Sequence
i10 : fold(identity, "a", "bcde")

o10 = ((((a, b), c), d), e)

o10 : Sequence

The difference between fold and accumulate is that fold returns the final result of all the nested evaluations of f, while accumulate lists all the intermediate values as well.

i11 : accumulate({2,3,2,1}, 2, (x, y) -> x^y)

o11 = {512, 9, 2, 1}

o11 : List

See also

Ways to use fold :

For the programmer

The object fold is a method function.