5. Lists I:  Definitions and Examples

Last revision: January 26 1998

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.

Mathematica operations/structures introduced: 
     Factorial[]
     Range[]
     Apply[]
     Do[]
     Module[]
     Part[]
     Position[]
     Sort[]
     Reverse[]
     Attributes[]
     Map[]
     Union[]
     Append[]
     Prepend[]
     First[]
     Last[]
     Transpose[]
     Table[]
     Take[]
     Partition[]

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 programmig 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 computer 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 oppostite 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 = 
{{"Jimmy", "Carr"}, {"Charles", "Babbage"}, {"Toby", "Crabtree"}, {"Where's", "Waldo"}, {"Parker", "Dixon"}, {"BJ", "Herbert"}, {"Denny", "Jones"}, {"North", "Moore"}, {"David", "Moskowitz"}, {"Marc", "Naples"}, {"Matt", "Phillips"}, {"Austin", "Rice-Stitt"}, {"Matthew", "Schenk"}, {"Ryan", "Seifert"}, {"Alan", "Turing"}, {"Todd", "Slaby"}, {"Mike", "Tarver"}, {"Wilhelm", "Schickard"}, {"Ada", "Byron"}, {"John", "Atanasoff"}, {"Where's", "Waldo"}, {"Konrad", "Zuse"}, {"Claude", "Shannon"}};

(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]]}

Aside: Experiment with the appearance of the preceding output cell in OutputForm, StandardForm, and TraditionalForm.

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 position number(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's and 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 a 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]]