Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will.  Free for
distribution to college and university instructors for personal,
non-commercial use.  If these notebooks are used in a course, the authors
request $20 per student.

7. Lists III:  Repetition with Lists

Last revision:  September 12 1996

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.

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