7. Lists III:  Repetition with Lists

Last revision: January 26 1998

In the previous section, we learned how to perform operations repeatedly on separate values.  In this section we learn how to perform operations repeatedly, using a value from the previous operation in the next:  this sort of repetition is called repetition with feedback.

Mathematica operations/structures introduced: 
     Nest[]
     NestList[]
     Fold[]
     FoldList[]

Nest, Fold

Nest, NestList

We have seen several functions which take another function as an argument, such as "Map[]" and "MapThread[]".  These higher-order functions, or "adverbs", as well called them in the last section, are some of Mathematica's most powerful functions.  We present two more, "Nest[]" and "Fold[]".

"Nest[]" is used to apply the same function repeatedly to a value, in the following way:  each time, the function is applied to the result of the previous application.  For instance, applying the squaring function three times in this way to the value 2, we would find the square of 2, namely, 4; its square, namely 16; and finally its square, namely 256.  The Mathematica command "Nest[]" takes the function to be applied as the first argument, the initial value as the second, and the number of repetitions of the function as the third.  Hence our squaring of 2 can be accomplished with the following command:

Clear[square];
square[x_] := x^2;
Nest[square,2,3]

"NestList[]" is similar to "Nest[]" in that it takes as arguments a function, a starting value, and the number of times to "iterate" or "nest" the function, but "NestList[]" returns a list of all intermediate calculations, including the initial value.  We can see successive square roots of 10 as follows:

NestList[Sqrt,10,4]

If we want to see the decimals we can wrap this command inside "N[]", or we can just plug in a decimal to start with.

NestList[Sqrt,10.0,4]

"Nest[]" and "NestList[]" are more elegant ways to achieve repetition---and certainly use fewer keystrokes---than performing the same operation over and over in separate commands:

Sqrt[10.0]

Sqrt[%]

Sqrt[%]

Sqrt[%]

Fold, FoldList

The function "Fold[]" is similar to "Nest[]", except that the function named in the first argument to "Fold[]" must be one that requires two arguments, such as "Plus[]", "Times[]", "Subtract[]", or "Divide[]", for example.  Since the function requires two arguments, we must examine how "Fold[]" will use the result from one application of the named function in applying the function again.  What happens is that "Fold[]" takes the result of the previous application and uses it as the first argument in the next application, drawing the second argument in the next application from a list we provide "Fold[]".  Each time, then, a new second argument is drawn from the list.  The only issue, then, is how "Fold[]" first begins; what will it use for the first argument of the first application?  The answer is that we must provide this first, initial value, separately.  Let's look at an example.  We will use "Plus" for the function, "a" for the initial value, "{b,c,d,e}" for the list.

Clear[a,b,c,d,e];
Fold[Plus,a,{b,c,d,e}]

Mathematica first computes "Plus[a,b]", namely "a+b"; then "Plus[a+b,c]", namely "a+b+c"; then "Plus[a+b+c,d]", namely "a+b+c+d"; and finally "Plus[a+b+c+d,e]", namely "a+b+c+d+e".  Note in particular how all of the second arguments came from the list passed to "Fold[]" as its third argument.  As one might expect, "FoldList[]" returns a list of all intermediate calculations, including the initial value.

FoldList[Plus,a,{b,c,d,e}]

Let us examine another example, using "Times[]", the familiar multiplication operator.  Take a moment to guess what the output of the following would be.

FoldList[Times,0,Range[10]]

Not too interesting; we'll find all of the intermediate products of 0*1*2*...*10.  If we start with 1, however, we can find 10 factorial, or 1*2*...*10:

FoldList[Times,1,Range[2,10]]

10!

Repetition With and Without Feedback

"Nest[]" and "Fold[]" are examples of what we call repetition with feedback.  To explain repetition with feedback, let us define instead what it is not:  repetition without feedback.  The function "Table[]" is an example of an implementation of repetition without feedback, which means that no iteration depends on the one before.

sayHi := "Hello"

Table[sayHi,{5}]

However, "Nest[]" and "Fold[]" each use the result of the previous iteration in the current one.  "Nest[]" applies a function to the result of the previous iteration, while "Fold[]" applies a function to the result of the previous iteration and a new value taken from a list.

Example:  Powers of 2

Let's examine two ways to compute successive powers of 2, using repetition with and without feedback.  One way is to determine, ahead of time, what exponents we need, and then use "Map[]" to apply the appropriate function to each of these powers.  Suppose we want the first 10 powers of 2.  We use "Range[]" to find the first ten integers:

Range[10]

Then we can raise 2 "to" the entire list, i.e., we can raise 2 to each element of the list using a list operation, "^":

2 ^ Range[10]

What Mathematica executed, however, was "2^1", "2^2", "2^3", and so on, to "2^10".  We notice that each result is simply 2 times the previous result; Mathematica does not need to start with 2 and multiply many 2's each time.  A more efficient way to solve the problem, then, is to use repetition with feedback, as follows:

Clear[times2];
times2[x_] := x*2;
NestList[times2,2,9]

Note that we used 9 iterations, not 10, since the initial value is placed in the list.

Reading Code

To test your comprehension of the material covered so far, try to determine the output of the following cells without executing them on your machine.   Then execute the cells to check.  This exercise is a good skill to develop, for those who cannot predict the results of their code are performing more guessing than problem solving.

midpoints[list_] := 
   (Drop[list,-1] + Drop[list,1]) / 2

xs = Range[0,1,.2]

NestList[midpoints,xs,5]

%//TableForm