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.

6. Lists II:  Iteration and List Handlers

Last revision: September 10 1996

We introduce iterators in some generality, and then we continue our
exploration of list-based functions, exploring ways to construct a list
(typically of numbers) and ways to deconstruct a list into various pieces.
Some of this material you have seen before, and if you fully understand it,
feel free to move on.  Finally, we outline an analogy between Mathematica
code and language grammar, studying how some functions in Mathematica
affect the operation of others.

Iterators

Iterators are lists which instruct functions such as Sum[ ], Table[ ], Do[
], and Range[ ] on how many iterations, or steps, a certain operation
should be repeated.

If an iterator is of the form "{number}", then the function is instructed
to do the operation "number" times.  For example, "{30}" as iterator means
to repeat the operation 30 times.  We have already used this in our Table[
] command:

Table[r,{5}]

If an iterator is of the form "{variable, number}", then the function is
instructed to do the operation "number" times, where the first time
"variable" will be 1, the second time 2, and so on, up until "number".

Table[r, {r,5}]

If an iterator is of the form "{variable, number1, number2}", then the
function is instructed to do the operation "number" times, where the first
time "variable" will be the value of "number1", the second time "number1"
plus 1, and so on, until "variable" reaches "number2".  "number1" is a
minimum value; "number 2" is a maximum value.

Table[r, {r,2,6}]

If an iterator is of the form "{variable, number1, number2, number3}", then
the function is instructed to do the operation "number" times, where the
first time "variable" will be the value of "number1", the second time
"number1" plus "number 3", the third time "number1" plus 2 times "number3"
and so on, until "variable" reaches "number2".  "number1" is a minimum
value; "number2" a maximum value; "number3" a step value.

Table[r, {r,2,6,0.5}]

The "number" expressions need not be numbers but larger expressions if
necessary, and it is possible to have several iterators in a row.  In this
case it is not true that the first iterator executes, finishes, and then
the next one executes, and so on.  Instead the iterators are nested.  For
instance, in the two-iterator case, the first iterator starts at its first
value, the second iterates through all of its valued, and then the first
iterator steps to its next value, the second iterates through all of its
values, and so on.  Here is an example:

Table[Pi^r E^s,{r,2,6},{s,1,5}]

Note that "Table[expression,{a,amin,amax},{b,bmin,bmax}]" operates in the
same fashion that nested "Table[ ]" functions do, with the iterators
reversed; for example, the previous expression is the same as

Table[Table[Pi^r E^s,{s,1,5}],{r,2,6}]

List Generators (List, Table, Range, Operations)

First, recall that the functional form of a list (given by "FullForm[ ]")
is simply "List[x, y, z, .... ]"; thus, the most naive way to form a list
is simply to write out each of its elements.

List[1,2,3,4]

{1,2,3,4}//FullForm

Another way to create a list is to form a table of values, using an iterator.

Table[x,{x,0,1,.2}]

Table[x^2,{x,0,1,.2}]

A third way is to use "Range[ ]", a primitive form of "Table[ ]" which
simply gives the value of the iterator (with no variable specified).
Notice that for "Range[ ]" braces are unnecessary.

xlist = Range[0,1,.2]

Finally, many operations which usually apply to numbers can be applied to
list, and typically the operation is applied to each element of the list.
Experiment with other operations!

ylist = xlist^2

zlist = xlist + 5

Extracting from List (Part, Take, Drop)

We've already seen one way to get a n element or portion of a list, using
double brackets [[]].  Recall that the functional form of [[ ]] is
"Part[list, ... ]".  "Part[ ]", "Take[ ]", "Drop[ ]" are the "core" of list
extraction operators.  In fact, "Take[ ]" and "Drop[ ]" can be defined
using "Part[ ]".  Let's look at some examples.

Let's say we want the first "n" elements of a given list.  In the first
argument of "Part[ ]" we must place the list from which we want elements
extracted, and in the second argument of "Part[ ]" we must place a list of
the positions, or indices, we want extracted from the list.  To form a list
with the indices from 1 through "n", we will use the expression "Range[n]".
Here's a function definition of our operation:

myTake[list_, n_] := Part[list, Range[n]]

Clear[a,b,c,d,e,f];
myTake[{a,b,c,d,e,f},3]

Actually, though, there's a Mathematica function which does exactly what
we've defined.  This function is Take[ ]:  "Take[list,number]" gives the
first "number" elements of the list.  Similarly,
"Take[list,{number1,number2}]" gives the elements from position "number1"
to position "number2".  An interesting variation is that if "number" is
negative, Take[ ] gives that many elements from the end.  (Note that
"myTake[ ]" does not have these additional features; some additional
programming is necessary to make "myTake[ ]" fully match "Take[ ]".)

Take[{a,b,c,d,e,f},3]

Take[{a,b,c,d,e,f},-3]

A related function is "Drop[ ]".  "Drop[list,n]" returns "list" with its
first "n" elements dropped (omitted); if "n" is negative, the last "n"
elements are dropped; and if "n" is of the form "{number1, number2}", then
the elements from position "number1" to position "number2' are dropped.

Drop[{a,b,c,d,e,f},2]

Drop[{a,b,c,d,e,f},-2]

Drop[{a,b,c,d,e,f},{3,5}]

Example of List-Based Programming:  Finding Midpoints of Lists

Let's use these operations to consider a larger problem, that of finding
all of the midpoints of a list of numbers.  A midpoint of two numbers "x"
and "y" is the number "(x+y)/2"; it's the average of the two numbers.
Finding all of the midpoints of a list means, for us, finding midpoints of
all consecutive numbers in the list, i.e., the midpoint of the first and
second numbers, the midpoint of the second and third, and so on.  This
problem is a good one for list-based programming, because it affords us an
opportunity to use list operations.

We'll begin with a list "xlist".

xlist = {0., 0.2, 0.4, 0.6, 0.8, 1.}

What we want to do is add consecutive numbers and then divide by 2, but how
might we do this only with list operations?  Well, we need a list of the
numbers we want to add, and we need a list of the numbers we want added to
the first list.  More precisely, we want a list of the left-hand addends,
and a list of the right-hand addends.  We can do this with "Drop[ ]".
First, the left-hand addends:

Drop[xlist,-1]

Then, the right-hand addends:

Drop[xlist,1]

Now we'll simply add the two lists and divide by 2!  Note that lists are
added element-by- element, and the divide-by-2 operation is applied to each
element of the resulting list.

(Drop[xlist,-1] + Drop[xlist,1]) / 2

Let's make a function out of this:

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

midpoints[xlist]

Another Example:  Riemann Sums

For another example, let's consider how we might evaluate some Riemann sums
of the function "x^2".  The algorithm is somewhat complicated, but nothing
we cannot accomplish using the operations we have covered.  A Riemann sum
for "x^2" with "n" divisions between x-values "a" and "b" (with "a"<"b") is
formed by finding "n" numbers equally spaced between "a" and "b",
evaluating "x^2" at each of them, multiplying these values by "(b-a)/n",
and adding up the results.  As always, we approach the problem by taking
small steps first.

To find "n" numbers equally spaced between "a" and "b", we use a result
from our mathematics class that the numbers "a", "a+(b-a)/n", "a+2(b-a)/n",
"a+3(b-a)/n", up to "a+(n-1)(b-a)/n" are equally spaced from "a" to
"b"---being "(b-a)/n" apart, each time.  How do we generate these numbers?
We can use "Range[ ]", with the appropriate iterator.  Note that the
beginning value is "a", the ending value is "a+(n-1)(b-a)/n", and the step
value is "(b-a)/n".  To aid us in working out the code, let's look at a
specific example first, say with 1 for "a", 2 for "b", and 10 for "n".  We
want, then, "Range[1, 1+(9)(2-1)/10, (2-1)/10]":

Range[1,1+(9)(2-1)/10,(2-1)/10]

Now we want to evaluate "x^2" at each of them.  Using list-based
operations, we can instruct Mathematica to raise each value to the second
power:

Range[1,1+(9)(2-1)/10,(2-1)/10] ^ 2

Now we must multiply each of these values by "(b-a)/n", or, in our case,
"(2-1)/10".  We'll place the multiplication operation at the end of the
line:

Range[1,1+(9)(2-1)/10,(2-1)/10] ^ 2 * (2-1)/10

Finally, we must use "Apply[Plus, ]" to add up each of the values in the
list.  ("Sum[ ]" requires an iterator, which we do not have; similarly,
"Apply[Sum, ]" would be incorrect.)

Apply[Plus,
   Range[1,1+(9)(2-1)/10,(2-1)/10] ^ 2
   * (2-1)/10
]

Our code is correct.  Looking back, however, we find that we can improve
the speed of the code, using the distributive property of multiplication,
as follows.  Instead of multiplying each element of the list by "(b-a)/n"
and then adding them up---which takes "n" multiplications followed by "n"-1
additions---we could add the elements up first and then multiply by
"(b-a)/n".  We then save "n"-1 of those multiplications:  adding the
elements up first and multiplying once takes "n"-1 additions and 1
multiplication.  Let's rewrite our code to take advantage of this improved
method:

Apply[Plus,
   Range[1,1+(9)(2-1)/10,(2-1)/10] ^ 2
] * (2-1)/10

Leaving the definition of "square[ ]", we can form the rest of the code into a function:

Clear[mySquareSum]
mySquareSum[a_,b_,n_] := Apply[
   Plus,
   Range[
      a,
      a+(n-1)(b-a)/n,
      (b-a)/n
   ] ^ 2
] * (b-a)/n

Let's check that it works:

mySquareSum[1,2,10]

Finally, we point out that one can accomplish the same operations using
"Sum[ ]" instead of "Apply[ ]" and "Range[ ]".  Consider the similarities
and differences between "mySquareSum[ ]" and the following function,
"newSquareSum[ ]":

Clear[newSquareSum]
newSquareSum[a_,b_,n_]:=
        (b-a)/n * Sum[i^2,{i,a,a+(n-1)(b-a)/n,(b-a)/n}]

newSquareSum[1,2,10]

Grammar and Examples of Adverbs (Inner, Outer, Apply, MapThread)

A good analogy which might be made between Mathematica code and language
grammar is as follows.  A "noun" is anything defined with an equals sign
and no formal parameters (expressions followed by underscores inside
brackets); a "verb" is anything defined with colon-equals and with formal
parameters; and an "adverb" is a function which takes another function and
applies it in a certain fashion.  In this section we want to consider some
"adverbs".

Suppose we have a function which takes two arguments and we wish to apply
it to two lists in the following fashion:  we want to use the function with
the first argument taken from the first list and the second taken from the
second list, and we want to do so for all possible combinations.  The
adverb which applies a function in this fashion is "Outer[ ]".  Let's make
two lists and watch it work.

sideList = Range[.16,.20,.01]

topList = Range[10,15]

Outer[Times, sideList, topList]

Sometimes it's useful to show the output of a list of lists in a tabular
form.  "Expression// TableForm" or "TableForm[expression]" will accomplish
this for us.  Note that each innermost list is a row (not a column) of the
table.

%//TableForm

Note:  It's best not so save the lists with "TableForm[ ]", since this
isn't the easiest way for Mathematica to work with them.

What if we don't want a function so complicated as "Outer[ ]", but simply
want to apply a function to all elements of the list together, such as + or
*?  Here "Apply[ ]" is the function (adverb) we want.

xlist

Apply[Plus,xlist]

Apply[Times,xlist]

What if we want a function like "Outer[ ]", except that we don't want all
possible combinations of taking a first argument from a first list and a
second from a second?  Let's say we want to take arguments, one at a time,
from each list, say using the first elements of each list together, then
the second, and so forth.  "MapThread[ ]" is the function (adverb) we want:
it takes a function of two or more arguments and matches up arguments from
a list of lists.

First we'll define an averaging function.

ave2[a_, b_] := (a+b)/2

ave2[3,7]

And now we'll use this function to average grades, say for students, where
the first list is the scores on the first test and the second list is the
scores on the second list (in the same order).

MapThread[ave2,{{3,4,5},{7,8,9}}]

xlist

This average function gives us a new way to find our midpoints; we simply
use "MapThread[ ]" with "ave2[ ]" and our two truncated lists.  First we'll
need to make a list of the two lists:

twolists = {Drop[xlist,-1],Drop[xlist,1]}

And then here we go:

MapThread[ave2,twolists]

A dot product

A certain operation in mathematics is to take two lists, multiply
corresponding entries, and add up all of the products.  We will do this
with the Mathematica commands we know.  First, though, let's note that
Mathematica already knows how to do this, with the "." operator:

Clear[a,b,c];
{1,2,3}.{a,b,c}  (* Built-in dot product *)

Dot[{1,2,3},{a,b,c}]

First we want to multiply corresponding entries.  This is accomplished just
by using "MapThread[ ]" with "Times[ ]".

MapThread[Times,{{1,2,3},{a,b,c}}]

Then we want to add up all the elements. Recalling that "%" denotes the
result of the previous expression, we try the following:

Apply[Plus,%]

The code appears to work, so we'll put the two lines together, programming
bottom-up:

Apply[Plus,
   MapThread[Times,{{1,2,3},{a,b,c}}]
]

Finally, satisfied with our code thus far, we form the code into a function:

myDot[list1_,list2_] :=
        Apply[ Plus, MapThread[ Times, {list1,list2} ] ]

Note how we had to put brackets around the two lists to make a
list-of-lists for "MapThread[ ]".