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.

5. Lists I:  Definitions and Examples

Last revision: September 10 1996

In this section we introduce a particular programming paradigm (list-based
programming), briefly contrast it with other programming paradigms we have
encountered or will consider, and continue with our survey of functions
which support list-oriented programming.  We do so in the context of
manipulating the roster of a class in school.

List-Based Programming

Congratulations!   You have completed the introductory section of this
course.  We now consider a particular programming paradigm:  list-based
programming.  This style of programming privileges lists over other types
of data; nearly every function takes a list as a parameter or argument and
returns a list as its output.  In this mode, we must consider how we may
accomplish our programming tasks by using functions which apply to entire
lists, not how we might use each element of a list separately.  In some
situations, when for instance data is written in a formatted way to a laser
printer, data will not be strictly in the form of a list, but for the bulk
of computing in list-based programming, data will be primarily, if not
exclusively, represented and manipulated in the form of a list.

Repetition and Programming Paradigms

Before we spend several sections on this particular paradigm, it is useful
to have an idea of what several progamming paradigms are---and how similar
operations may be carried out in each.  First, it is important to realize
that programming paradigms are only structures for programming,
perspectives with which to view the programming task.  By themselves,
programming paradigms do not offer any particular functions or abilities.
In fact, any programming task should be solvable in any programming
paradigm.  We study programming paradigms primarily because knowing
particular paradigms allows one to solve certain programming problems more
efficiently.  While we may be comfortable, for instance, manipulating
elements of lists instead of entire lists, it may be the case for a
particular problem that we may reach a solution which is much shorter (in
lines of code), or simpler (in method), or faster (in time to execute it on
a machine), if we consider how we could accomplish similar actions,
operating only on entire lists.

To illustrate this difference, let's consider the notion of repetition.
The idea that some operations should be carried out over and over again on
different data is a notion central to computing, for that is precisely what
computers can do better (or at least faster) than we can.  Therefore,
considering how different paradigms provide for the repetition of an
operation is a useful way to distinguish between the paradigms. In what
follows we will examine the various ways we can instruct Mathematica to
evaluate factorials, which are products of consecutive integers, beginning
with some integer and continuing down to the integer 1, such as
9*8*7*6*5*4*3*2*1.  Please note that you are not expected to understand
each line of every input cell, but instead to have a first look at the
difference in programming styles.  We will take up the particular details
of other programming paradigms later in the course.

Paradigm 1: Pre-Definition

One extremely restricted programming paradigm is pre-definition, which
incorporates two guiding ideas:  first, that any operation we wish to
accomplish should have a named function which performs the operation, and,
second, that no combination of these functions should be allowed.  One
example of a computer which operates under this programming paradigm would
be an old, scientific calculator which does not provide the capability to
program in the traditional sense---the user is allowed only to use
individual functions on the calculator, one at a time, but not to put
several together into a new function.  This is not to say that such a
calculator cannot be used to accomplish many operations---it can---but the
ability of a programmer to affect the versatility or even the number of
functions on the machine is limited. In order to provide a new function,
the machine itself would have to be changed---buttons added, extra chips
installed, and so on---which would certainly be a real burden to any
programmer!   In Mathematica, the analogy would be to use single functions
in Mathematica, never in combination.  It so happens that Mathematica has a
command to compute factorials, called "Factorial[ ]". (The operator form of
the function is the exclamation point:  "9!")

Factorial[9]

9!

Paradigm 2: List-based programming

How would we think of accomplishing the same task in list-based
programming?  We know that we must instruct the computer to operate on
entire lists, so we might wish to begin by finding the list of all integers
1 through 9.  At that point, we would use a list-based function which takes
a list, multiplies together all of its elements, and returns the result.
(The result, although a number, might be placed in a list by itself.)  We
follow this plan.  We generate a list of the first 9 integers by using
"Range[ ]":

Range[9]

Then we tell Mathematica to apply the function "Times[ ]" to all of the
elements of the list:

Apply[Times,Range[9]]

We may even define a function to do exactly these operations for any given
integer:

listFac[n_] := Apply[Times,Range[n]]

Let's see that it works:

listFac[9]

Paradigm 3: Recursion

Recursion is a more advanced paradigm than list-based programming and
incorporates a clever way of organizing repetition.  The guiding idea of
recursion is that a function should be designed with two characteristics:
first, the function should perform only one instance of the operation to be
repeated, so that the programming task has one small part accomplished,
and, second, that the rest of the programming task should be accomplished
by having the function use the result of invoking the same function with
different initial parameters.  Admittedly, this paradigm seems complicated
at first blush; we will consider recursion in much more detail later in the
course.  Here we show how our factorial task may be implemented using a
recursive function.

Our function will take an integer as an input value, invoke itself with the
input value one smaller, and multiply the result by the original integer.
What will happen?  When the original integer is 9, the function will
execute itself with 8 as input and multiply the result by 9.  If the
function returned 8*7*6*5*4*3*2*1 when 8 was placed inside, then clearly
our factorial function will work. Let's examine what will happen when the
function receives 8 as the input value.  Then it will call itself with 7 as
input and multiplies the result by 8.  Again, we hope that when the
function receives 7 as input it will return 7*6*5*4*3*2*1.  If we continue
analyzing the function in this manner, we realize that if the integer 1 is
the input value, we should make sure the function returns a 1; otherwise,
it might return the result of 1*0*-1*..., which is certainly not desired.
If the function returns the integer 1 when the integer 1 is the input
value, we can convince ourselves that the function, thus defined, will
actually produce the correct factorials.  Here is the code:

recurFac[n_] := n * recurFac[n-1]
recurFac[1] = 1

(We will see later that Mathematica first checks the input value against a
list of special cases; in our case, it will check first of the input value
is a 1, returning a 1 if so and otherwise using the definition given
above.)

recurFac[9]

Paradigm 4: Procedural programming (using loops)

Finally, we consider procedural programming, a less advanced paradigm than
list-based recursion. Procedural programming is, in one sense, at the
opposite extreme from list-based programming; in procedural programming we
focus on individual items of data.  In order to repeat an operation, we set
up what is called a loop, which is programming code instructing the
computer to execute the same lines of code over and over.       Inside the loop
we write the instructions which will be repeated.  In order to have the
loop stop executing when it is finished, a loop usually contains a stopping
condition. When the computer encounters a loop, it executes each of the
instructions inside the loop and tests whether or not the stopping
condition is true.  If the condition is not true, it begins again at the
start of the loop, executing the instructions and testing the stopping
condition again.  When the stopping condition finally is true, the computer
moves on to the next instruction.  Frequenly loops use a special variable,
called an iterator, which counts the number of times the loop's
instructions have been executed and which can be used to decide when the
loop should stop.  The iterator might begin with a value of 1, and the
instructions inside the loop say to increment the iterator by 1.  In this
way the stopping condition can look at the value of the iterator, and for
instance test whether or not the loop has been executed enough times.

In our case we could begin with 1 and multiply each integer consectively
until we reach the final value, 9.  We implement this plan as follows.  We
declare a variable "sofar" which is initialized to 1 and which keeps track
of the product thus far.  We perform a loop with an iterator "i" which
begins at 2, has 1 added to it each loop, and stops at 9, and inside the
loop we instruct the computer to multiply "sofar" by "i" and place the
result back inside "sofar".  One way to do this in Mathematica is to use
the "Do[ ]" function, which performs the operation given by the first
argument over and over, with the iterator, the beginning iterator value,
and the ending iterator value given as a list as the second argument:

sofar = 1;
Do[
   sofar = sofar * i
,{i,2,9}];
sofar

Another way to accomplish the same operation in procedural programming in
Mathematica is to define a function which executes each of these statements
for us, and specifies that "sofar" should be forgotten once we're done
finding the factorial.  Here is the Mathematica code:

loopFac[n_] :=  Module[ {sofar},
   sofar = 1;
   Do[
      sofar = sofar * i
   ,{i,2,n}];
   sofar
]

loopFac[9]

A Class Roster

Here is a list of names of people in a class, with some additions.

roster = {{"Brent", "Dennis"},
{"Thomas", "Beadle"}, {"Brent", "Gilbert"},
{"Matthew", "Lake"}, {"David", "Wick"},
{"Amy", "Jones"}, {"Emily", "Katzfey"},
{"Patricia", "Sabrinsky"}, {"Daniel", "Tedrick"}, {"Marek", "Blicharz"},
{"Pamela", "Hockert"},
{"Rachel", "Gimpel"}, {"Claytonia", "Boular"}, {"Eric", "Bourn"}, {"Alan",
"Turing"},
{"Where's", "Waldo"}, {"David", "Kearfott"}, {"Lynsay", "Madley"},
{"Where's", "Waldo"},
{"Jack", "Morse"}, {"Robert", "Briggs"},
{"Patrick", "Cahan"}, {"Nicholas", "Carpenter"}
};

(Note to instructor:  Define a "random" roster with names placed in
positions 10 and 2 as below, add Alan Turing in position 15 and two
"Where's Waldo"'s.)

Part and Parcel (Part, Position)

It is a stretch to call this a roster since the names are not in
alphabetical order.   We can fish out the first two last names by counting
to see that they are the 10th and 2nd names in the list.

roster[[10]]

roster[[2]]

Rather than stringing the names down the page, let's keep them gathered in
a list.

{roster[[10]], roster[[2]]}

Now we do not have to keep typing "roster"; we can instruct Mathematica to
select out each of several elements of the list.  For the parameter in
double-brackets, we place a list containing, in order, the positions of the
elements which we would like.

roster[[ {10,2} ]]

If, however, we do not use a list, Mathematica will perform another
operation:  it will find the element whose position we specify as the first
argument, and then inside that element find the element whose position we
specify as the second argument, and so on.  Examine closely what
Mathematica does to the following expression.

roster[[10,2]]

This code did not give us the 10th and 2nd names; instead it took the 10th
element of the list and gave us the 2nd part of that list.

This operation of indexing into a list has the functional name "Part[ ]".
The command "list[[ positionNumber(s)]]" is just shorthand for "Part[ list,
positionNumber(s) ]".  This notation can be helpful if you get dizzy with
multiple brackets.

Part[roster, {10, 2}]

Part[roster, 10, 2]

Now "Part[ list, positionNumber(s) ]" takes positionNumber(s) and returns
the item(s); we may wish to do the opposite, determine where inside the
list a particular element lies.  This opposite operation is performed by
"Position[ ]".  This function enables us to find where in the list is the
name "Turing".

Position[roster, "Turing"]

{"Alan", "Turing"} is in the 15th slot of the roster, and "Turing" is in
the second position of the list {"Alan", "Turing"}.

roster[[15,2]]

It checks.  (By the way, Alan Turing is not actually in the class.  He is a
founding father of computer science who proposed the theoretical Turing
machine in a work entitled "On Computable Numbers" in 1937.)

Roster Sorting  (Map, Reverse)

We could attempt to alphabetize our list by hand, or we could use the
"Sort[ ]" command.  We attempt to do so:

Sort[roster]

This result, however, is probably not what we wanted; instead, we would
like to sort the list by last names.

When we sort a list of lists, it is the first element of each sublist that
is ranked, or ordered.   To sort by last names, our plan should be to
reverse the order of the elements inside the sublists so that, for example,
{FirstName, LastName} becomes {LastName, FirstName}; afterwards, "Sort[ ]"
will sort the elements in the correct fashion.  If the tutorial ended right
here and you were wondering how to reverse the elements of a list, then we
hope you would enter:

?Reverse

Excellent!  Just what we need.  Let's try it out on three simple examples.

{Reverse[{1,2}], Reverse[{1,2,3}], Reverse[{a,b,c,d}] }

Now let's try to reverse the names on the roster.

Reverse[ roster ]

What happened?  Each element is still in the form {FirstName, LastName}.
This operation reversed the whole list instead of each sublist.

The situation we have just encountered is common to list-based programmers.
Sometimes when we apply a function to a list, the function automatically
"enters inside" and is applied to each element in the list, which may be a
list itself.  The Mathematica terminology for this behavior is that the
function is mapped onto the list. For example, the "Sin[ ]" function is
automatically mapped onto lists.

Sin[{1,2,3}]

Now why wasn't the "Reverse[ ]" function mapped onto the list of names?  To
see why we may not want that behavior, let's suppose we wanted to transform
the list { {1,2},{a,b} } into {{a,b},{1,2}}.

Reverse[{ {1,2},{a,b} } ]

In this instance we would be very annoyed if "Reverse[{{1,2},{a,b}}]" was
mapped inside to give us "{{2,1},{b,a}}".  Sometimes, then, we may want
"Reverse[ ]" to "go inside" and sometimes not. Consequently, as the
Mathematica developers agreed, it is better not to have "Reverse[ ]" mapped
onto a list unless we specifically ask for it.

Functions like "Sin[ ]" that do automatically go inside a list are called
"Listable" functions.  You can find out whether a function is "Listable" by
asking for its "Attributes".

{Attributes[Sin],Attributes[Reverse]}

Both functions are "Protected" so that you cannot accidentally redefine
them, but "Sin[ ]" is also Listable.   At this point we are clear on how to
tell if a function has the "Listable" behavior, but we need to know how to
force such behavior when Mathematica will not do so automatically.  To map
a function that is not "Listable", we use the "Map[ ]" function.  Let's
look at an example.

Clear[f]
f[{1,2,3}]

We see that the function "f" is not Listable, but we can map it onto a list
using "Map[ ]":

Map[f,{1,2,3}]

"Map[ ]" takes two arguments, a function and a list.  (Note that we need
only give the name of the function, not any brackets with it.)  Think of
"Map[ ]" whenever you want to apply a non-"Listable" function to every
element in a list.  Let's try mapping "Reverse[ ]" onto "roster".

Map[Reverse,roster]

Yes!  All elements are now in the form {LastName, FirstName}.  Using "Sort[
]" should now do exactly what we want.

Sort[ % ]

Let's check that we are on the right track, and determine the answer to
"Who's the first person on the roster?"

roster[[1]]

What?  But we just sorted the roster!

The problem here is that we never indicated that we wanted to change the
roster.  The first person on the original roster is still the first person
on "roster".  To change "roster" we need to use the assignment operator
"=".     Let's put the whole thing together here.

roster = Sort[ Map[Reverse,roster] ]

Now, we've sorted the roster and recorded the new ordering.  As a last step
let's return to the friendlier {FirstName,LastName} form.

roster = Map[ Reverse, roster]

More List Functions  (Transpose)

Now where in the list is Waldo?

Position[ roster, "Waldo"]

This tells us that Waldo's name appears twice.  To get rid of multiple
copies in a list we can use "Union[ ]".

{ Union[{1,1,1,1,1}], Union[{c,b,a,b}], Union[{5,5,4,5}]  }

roster = Union[roster]

The "Union[ ]" function also sorts the remaining elements, so the list has
been sorted by first names again.

Now that the list is duplicate-free, let's ask how many people are on the
roster.

Length[roster]

Let's have someone join the class.  Since we have Alan Turing a founding
father, we add Grace Hopper a founding mother.  (Grace Hopper headed a team
that developed one of the first languages widely used in business, COBOL.
It is said that she found "the first computer bug" in 1945.)  We use the
function "Append[ ]".

roster = Append[ roster, {"Grace", "Hopper"} ]

The "Append[ ]" function takes two arguments, the first a list and the
second what we want to add to the end of the list.  "Prepend[ ]" works the
same way, except that the new element is added to the start of the list.
Let's re-sort the list according to last names..

roster = Map[ Reverse, Sort[ Map[Reverse,roster] ] ]

Note that we just carried out a rather complicated operation.  Make sure
that you understand exactly what happened---and how we instructed the
computer to perform that operation---before scrolling on.  If you cannot
decipher something, then scroll back up for a review, and if that does not
help, then signal your instructor for some help!

Now let's find a list of everybody's first names.  To get the first element
of a list we use "First[ ]".

{ First[{1,2,3}], First[{"paper","rock","scissors"}] }

Think for a moment about how we can produce a list of the first names of
everyone in the class.  We want to apply "First[ ]" to each element in the
list "roster".   Think Map!

Map[First,roster]

How about a list of last names?

?Last

Looks good.

Map[Last,roster]

Now there is another, somewhat sneaky, but very useful, way to separate out
the first and last names of our list.  We can use Tranpose whenever we have
a list of pairs, such as { {x1,y1}, {x2,y2},...,{xn,yn} } and you want to
produce the list { {x1,x2,...,xn}, {y1,y2,...yn} }.  Let's see a specific
example.

Transpose[{ {"a",1},{"b",2},{"c",3},{"d",4} } ]

On the other hand, the function "Transpose[ ]" can take a list containing a
list of x's and a list of y'sand produce a list of {x,y} pairs.   Thus,
applying "Transpose[ ]" to the last output from above should return us to
the list of pairs, instead of the pair of lists.

Transpose[%]

Now let's try this sneaky way of separating the first and last names.

Transpose[roster]

Looks good.  Now here's a puzzle.  We want to sort the first and last names
independently and then pair them back  together so that the first first
name and the first last name get paired up.  The second first name and
second last name should be paired up, and so on.

We know that "Transpose[ ]" will split the roster into first and last
names.  We'd like to sort each sublist separately (the same thing to each
sublist sounds like a job for Map) and then recombine the two sorted lists.
To understand that the next command will really do all this, you need to
read it from inside out.  First we transpose, then sort each sublist, then
transpose back.

Transpose[ Map[Sort, Transpose[roster] ] ]

If you're having trouble understanding what a complicated command is doing,
then copy out small sections of the innards to see what they are doing.
Then think about what effect each additional layer of the command has.

Making Lists (Table)

Let's take a break from the roster for a moment.   How can you create a
list of your own?
There are two basic ways:  enter one in by hand, or use "Table[ ]".  Here
are some examples:

Create a list of your favorite colors.

{"Blue","Green","Azure"}

There's no pattern to these favorite colors so all we can do is list them
by hand.

Create list of the squares of the integers from 1 to 5.

We could enter this by hand, but it's easier to use the "Table[ ]" function.

Table[i^2,{i,1,5}]

Recall that the "i" in "{i,1,5}" is called an iterator.   Each value of "i"
from 1 to 5 will be squared and put in the list.

Create a list showing the squares and cubes of the integers from 1 to 5.

Table[{i^2,i^3},{i,1,5}]

Here {i^2,i^3} gets recorded for each value of the iterator "i" from 1 to 5.

Create a list of five lists, where the first list is {1}, the second list
{1,2}, the third list {1,2,3}, and so on.

Table[ Table[i,{i,1,j}], {j,1,5}]

The outside "Table[ ]" command asks for a list of five things as "j" steps
from 1 to 5.  These five things happen to be lists themselves, generated by
"Table[i,{i,1,j}]".  For example, when  j=1 the element is produced by
"Table[i,{i,1,1}]", which gives {1}.  Consider what happens when j=2.

Shuffling and Matching (Partition)

Let's create a list of 10 random Real numbers between 0 and 1.  The
function "Random[type, {smallest, largest}]" returns a random number of
data type "type" which lies between "smallest" and "largest".  Hence we
wish to invoke "Random[Real,{0,1}]".  (In fact, the default arguments of
"Random[ ]" are exactly these, so that "Random[]" performs the same
function.)

rand10 = Table[ Random[Real,{0,1}], {i,1,10}]

Now let's return to the roster and work on getting a random ordering of the
first ten people on the roster.  We start by getting the first 10 names of
the roster.

first10 = Take[ roster,10]

This takes the first 10 elements from the roster list.  "Take[roster,-10]"
would take the last 10 elements.

To mix the order of the names we can pair the names with the 10 random
numbers in "rand10" and sort the list.  The names will tag along with the
numbers as the numbers are rearranged.  Finally we will get rid of the
numbers, to leave a random ordering of the ten names.  Here's a command
incorporating each of these steps.

Map[ Last, Sort[ Transpose[rand10,first10] ] ]

The command, however, does not work.  And, to be honest, it is not easy to
figure out what went wrong.  One problem with our approach is that we tried
to do too much all at once.  It is not a good idea to try to write down a
long sequence of commands in one go;  much better to build up the command
slowly, using bottom-up analysis and testing as one goes along.  We follow
this plan.

Step 1:  Pair a random number with each name.

If we think of the numbers as x's and the names as y's, then we have a list
of x's and a list of y's and want a list of {x,y} pairs.  This is a job for
"Transpose[ ]".

Transpose[rand10,first10]

What went wrong here is that "Transpose[ ]" takes a list as input, and we
have given it two separate lists, "rand10" and "first10".  We need to group
these two lists together into the single list "{rand10,first10}".  We
correct our mistake now, before we have a chance to compound it with
subsequent commands.

Transpose[{rand10,first10}]

Step 2:  Sort the list.

Sort[%]

Note that the first elements of the sublists, namely the random numbers,
were sorted---the names just came along for the ride.

Step 3:  Get rid of the random numbers.

We have a list of sublists.  Each sublist looks like "{randomNumber,
{firstName, lastName}}", and we want to keep just "{firstName, lastName}".
We should then take the last part of each sublist.  We try "Last[ ]":

Map[Last,%]

Putting it all together.

Map[ Last, Sort[ Transpose[{rand10,first10}] ] ]

Try to do all of your Mathematica programming this way.  Start small, test
as you go, and then add additional layers to the command.

We are now able randomly to order the roster, as in the command below.
We've written the command in a format which is simpler to grasp than
leaving it all on one line; let's take a look at what we've done.  First,
the command is split onto several lines and, within this framework,
arguments to functions have been indented by two spaces and the closing
bracket "]" for each function appears below the first letter of the
function. We can tell, for instance, that the final bracket is for the
"Map[ ]" function, the one above it with "Sort[ ]", and the one above that
one with "Transpose[ ]".  We notice also that "Map[ ]" has two arguments:
the function "Last[ ]", and the results of the "Sort[ ]" function.

Map[
  Last,
  Sort[
    Transpose[
      {Table[Random[],{i,1,Length[roster]}], roster}
    ]
  ]
]

This still may look unclear, and another programming method is to define
functions to perform specific subtasks, then placing them together at the
end.  We define functions to do specific parts of the task to a generic
list.  The usefulness of the intermediate functions is debatable, but the
final product is definitely a great reusable function:  we will have
created a "Shuffle" function.   Let's break it into sub-steps:  (a)
creating corresponding random numbers we will call "tags", (b) pairing up
with tags, (c) sorting by tags, and (d) removing tags.

randTags[someList_] := Table[Random[], {Length[someList]}]

randTags[{1,2,3,4,5}]

attachTags[someList_] := Transpose[{randTags[someList], someList}]

attachTags[{1,2,3,4,5,6}]

Use "Range[ ]" to avoid typing (or using "Table[ ]") for simple lists formed by uniform steps.

test = attachTags[Range[8]]

removeTags[taggedList_] := Map[Last, taggedList]

removeTags[test]

Sort[test]

shuffle[someList_] := removeTags[Sort[attachTags[someList]]]

shuffle[Range[52]]

shuffle[roster]

Finally, we consider how we might randomly match partners from the roster.
This task consists of two steps:  (1)  randomly order the roster and (2)
break this list up into pairs.  Thankfully, "shuffle[ ]" performs (1) and
the Mathematica function "Partition[ ]" performs step (2).  Check
"?Partition" for information on "Partition[ ]".

Partition[{"a","b","c","d","e","f","g"},2]

Partition[{"a","b","c","d","e","f","g"},3]

Pause a moment and convince yourself how "Partition[ ]" works.  What if we
use "Partition[ ]" on a list of odd length and partition by 2?

pairs = Partition[shuffle[roster],2]

Although the nesting of braces can be confusing, we have produced a list of
pairs of names.  Who's the third pair?

pairs[[3]]