The basic example of Fold is given below, but first I clear values from all variables.


f[f[f[x, a], b], c]

The basic example above doesn't do much to help one understand how to make a useful program using Fold.  Some more illuminating examples are given below.  If you don't understand the #& notation see the discussion of Function. The three examples below aren't very useful, but they demonstrate the form that is normally needed when using Fold.

From these examples we get:

((((a b)c)d)e)


Fold[(#1 + #2) &, 0, {a, b, c, d, e}]

a + b + c + d + e

Fold[(#1 * #2) &, 1, {a, b, c, d, e}]

a b c d e

Fold[StringJoin[#1, #2] &, "", {"a", "b", "c", "d", "e"}]


A more useful application of Fold is given in the next cell.  Here we have a function that expresses a polynomial using Horner's rule.

HornerForm[poly_ ? PolynomialQ, x_Symbol] := Fold[(x #1 + #2) &, 0, Reverse[CoefficientList[poly, x]]]  HornerForm[2 + 3x + x^2 - 4x^3 + 2x^4, x]

2 + x (3 + x (1 + x (-4 + 2 x)))

In the Cell below Fold is used to make an Alternating Series.  If ( lst ) was used instead of (Reverse[lst] ),  the first term would be multiplied by (-1) when the Length of ( lst ) is even.  Jerry Keiper posted this solution to the MathGroup.

alternate[lst_List] := Fold[(#2 - #1) &, 0, Reverse[lst]]  Clear[a1, a2, a3, a4, a5, a6, a7, a8] ; alternate[{a1, a2, a3, a4, a5, a6, a7, a8}]

a1 - a2 + a3 - a4 + a5 - a6 + a7 - a8

Another application of Fold is shown below (copied from the Help Browser).  This function (EvaluateAt) takes an expression and a list of positions, and evaluates in place only the parts at the specified positions.

EvaluateAt[expr_, positions_] := Fold[ReplacePart[#1, Part[#1, Sequence @@ #2], #2] &, expr, positions]

To demonstrate this function consider the expression below which is wrapped in HoldForm to prevent evaluation.

expr = HoldForm[{{Cos[π], 8^(1/2), Cos[π], (x y z)^2},  {12^(1/2), Sin[ArcCos[x]], 2, 0}}] ;

First we use ReleaseHold to see what the expression evaluates to without HoldForm.


{{-1, 2 2^(1/2), -1, x^2 y^2 z^2}, {2 3^(1/2), (1 - x^2)^(1/2), 2, 0}}

In the next cell EvaluateAt (defined above) is used to evaluate only the parts of (expr) that contain trigonometric functions.

EvaluateAt[expr, {{1, 1, 1}, {1, 1, 3}, {1, 2, 2}}]

{{-1, 8^(1/2), -1, (x y z)^2}, {12^(1/2), (1 - x^2)^(1/2), 2, 0}}

If you have trouble figuring out the position of a portion of a sub-expression you are interested in you might want to down load a package Called (ExpressionManipulation.m) from .

An alternate method of getting the same result in this example is given in the discussion of Block.

For another elegant application of Fold see the program Alan Hayes wrote which quickly finds the integers Relatively Prime to an integer n using Fold.

Created by Mathematica  (May 16, 2004)

Back to Ted’s Tricks index page