How to Think Like a Computer Scientist: Learning with Python 2nd Edition/Lists

Lists

A list is an ordered set of values, where each value is identified by an index. The values that make up a list are called its elements. Lists are similar to strings, which are ordered sets of characters, except that the elements of a list can have any type. Lists and strings --- and other things that behave like ordered sets --- are called sequences.

List values

There are several ways to create a new list; the simplest is to enclose the elements in square brackets ( [ and ]):

The first example is a list of four integers. The second is a list of three strings. The elements of a list don't have to be the same type. The following list contains a string, a float, an integer, and (mirabile dictu) another list:

A list within another list is said to be nested.

Finally, there is a special list that contains no elements. It is called the empty list, and is denoted [].

Like numeric 0 values and the empty string, the empty list is false in a boolean expression:

With all these ways to create lists, it would be disappointing if we couldn't assign list values to variables or pass lists as parameters to functions. We can:

Accessing elements

The syntax for accessing the elements of a list is the same as the syntax for accessing the characters of a string---the bracket operator ( [] -- not to be confused with an empty list). The expression inside the brackets specifies the index. Remember that the indices start at 0:

Any integer expression can be used as an index:

If you try to read or write an element that does not exist, you get a runtime error:

If an index has a negative value, it counts backward from the end of the list:

numbers[-1] is the last element of the list, numbers[-2] is the second to last, and numbers[-3] doesn't exist.

It is common to use a loop variable as a list index.

This while loop counts from 0 to 4. When the loop variable i is 4, the condition fails and the loop terminates. So the body of the loop is only executed when i is 0, 1, 2, and 3.

Each time through the loop, the variable i is used as an index into the list, printing the i-eth element. This pattern of computation is called a list traversal.

List length

The function len returns the length of a list, which is equal to the number of its elements. It is a good idea to use this value as the upper bound of a loop instead of a constant. That way, if the size of the list changes, you won't have to go through the program changing all the loops; they will work correctly for any size list:

The last time the body of the loop is executed, i is len(horsemen) - 1, which is the index of the last element. When i is equal to len(horsemen), the condition fails and the body is not executed, which is a good thing, because len(horsemen) is not a legal index.

Although a list can contain another list, the nested list still counts as a single element. The length of this list is 4:

List membership

in is a boolean operator that tests membership in a sequence. We used it previously with strings, but it also works with lists and other sequences:

Since pestilence is a member of the horsemen list, the in operator returns True. Since debauchery is not in the list, in returns False.

We can use the not in combination with in to test whether an element is not a member of a list:

List operations

The + operator concatenates lists:

Similarly, the * operator repeats a list a given number of times:

The first example repeats [0] four times. The second example repeats the list [1, 2, 3] three times.

List slices

The slice operations we saw with strings also work on lists:

The range function

Lists that contain consecutive integers are common, so Python provides a simple way to create them:

The range function takes two arguments and returns a list that contains all the integers from the first to the second, including the first but not the second.

There are two other forms of range. With a single argument, it creates a list that starts at 0:

If there is a third argument, it specifies the space between successive values, which is called the step size. This example counts from 1 to 10 by steps of 2:

If the step size is negative, then start must be greater than stop

or the result will be an empty list.

Lists are mutable

Unlike strings, lists are mutable, which means we can change their elements. Using the bracket operator on the left side of an assignment, we can update one of the elements:

The bracket operator applied to a list can appear anywhere in an expression. When it appears on the left side of an assignment, it changes one of the elements in the list, so the first element of fruit has been changed from 'banana' to 'pear', and the last from 'quince' to 'orange'. An assignment to an element of a list is called item assignment. Item assignment does not work for strings:

but it does for lists:

With the slice operator we can update several elements at once:

We can also remove elements from a list by assigning the empty list to them:

And we can add elements to a list by squeezing them into an empty slice at the desired location:

List deletion

Using slices to delete list elements can be awkward, and therefore error-prone. Python provides an alternative that is more readable.

del removes an element from a list:

As you might expect, del handles negative indices and causes a runtime error if the index is out of range.

You can use a slice as an index for del:

As usual, slices select all the elements up to, but not including, the second index.

Objects and values

If we execute these assignment statements,

we know that a and b will refer to a string with the letters "banana". But we can't tell whether they point to the same string.

There are two possible states:

List illustration In one case, a and b refer to two different things that have the same value. In the second case, they refer to the same thing. These things have names---they are called objects. An object is something a variable can refer to.

Every object has a unique identifier, which we can obtain with the id function. By printing the identifier of a and b, we can tell whether they refer to the same object.

In fact, we get the same identifier twice, which means that Python only created one string, and both a and b refer to it. Your actual id value will probably be different.

Interestingly, lists behave differently. When we create two lists, we get two objects:

So the state diagram looks like this:

List illustration 2 a and b have the same value but do not refer to the same object.

Aliasing

Since variables refer to objects, if we assign one variable to another, both variables refer to the same object:

In this case, the state diagram looks like this:

List illustration 3 Because the same list has two different names, a and b, we say that it is aliased. Changes made with one alias affect the other:

Although this behavior can be useful, it is sometimes unexpected or undesirable. In general, it is safer to avoid aliasing when you are working with mutable objects. Of course, for immutable objects, there's no problem. That's why Python is free to alias strings when it sees an opportunity to economize.

Cloning lists

If we want to modify a list and also keep a copy of the original, we need to be able to make a copy of the list itself, not just the reference. This process is sometimes called cloning, to avoid the ambiguity of the word copy.

The easiest way to clone a list is to use the slice operator:

Taking any slice of a creates a new list. In this case the slice happens to consist of the whole list.

Now we are free to make changes to b without worrying about a:

Lists and for loops

The for loop also works with lists. The generalized syntax of a for loop is:

This statement is equivalent to:

The for loop is more concise because we can eliminate the loop variable, i. Here is the previous loop written with a for loop.

It almost reads like English: For (every) horseman in (the list of) horsemen, print (the name of the) horseman.

Any list expression can be used in a for loop:

The first example prints all the multiples of 3 between 0 and 19. The second example expresses enthusiasm for various fruits.

Since lists are mutable, it is often desirable to traverse a list, modifying each of its elements. The following squares all the numbers from 1 to 5:

Take a moment to think about range(len(numbers)) until you understand how it works. We are interested here in both the value and its index within the list, so that we can assign a new value to it.

This pattern is common enough that Python provides a nicer way to implement it:

enumerate generates both the index and the value associated with it during the list traversal. Try this next example to see more clearly how enumerate works:

List parameters

Passing a list as an argument actually passes a reference to the list, not a copy of the list. Since lists are mutable changes made to the parameter change the argument as well. For example, the function below takes a list as an argument and multiplies each element in the list by 2:

If we put double_stuff in a file named ch09.py, we can test it out like this:

The parameter a_list and the variable things are aliases for the same object. The state diagram looks like this:

Stack illustration 5 Since the list object is shared by two frames, we drew it between them.

If a function modifies a list parameter, the caller sees the change.

Pure functions and modifiers

Functions which take lists as arguments and change them during execution are called modifiers and the changes they make are called side effects.

A pure function does not produce side effects. It communicates with the calling program only through parameters, which it does not modify, and a return value. Here is double_stuff written as a pure function:

This version of double_stuff does not change its arguments:

To use the pure function version of double_stuff to modify things, you would assign the return value back to things:

Which is better?

Anything that can be done with modifiers can also be done with pure functions. In fact, some programming languages only allow pure functions. There is some evidence that programs that use pure functions are faster to develop and less error-prone than programs that use modifiers. Nevertheless, modifiers are convenient at times, and in some cases, functional programs are less efficient.

In general, we recommend that you write pure functions whenever it is reasonable to do so and resort to modifiers only if there is a compelling advantage. This approach might be called a functional programming style.

Nested lists

A nested list is a list that appears as an element in another list. In this list, the element with index 3 is a nested list:

If we print nested[3], we get [10, 20]. To extract an element from the nested list, we can proceed in two steps:

Or we can combine them:

Bracket operators evaluate from left to right, so this expression gets the three-eth element of nested and extracts the one-eth element from it.

Matrices

Nested lists are often used to represent matrices. For example, the matrix:

might be represented as:

matrix is a list with three elements, where each element is a row of the matrix. We can select an entire row from the matrix in the usual way:

Or we can extract a single element from the matrix using the double-index form:

The first index selects the row, and the second index selects the column. Although this way of representing matrices is common, it is not the only possibility. A small variation is to use a list of columns instead of a list of rows. Later we will see a more radical alternative using a dictionary.

Test-driven development (TDD)

Test-driven development (TDD) is a software development practice which arrives at a desired feature through a series of small, iterative steps motivated by automated tests which are written first that express increasing refinements of the desired feature.

Doctest enables us to easily demonstrate TDD. Let's say we want a function which creates a rows by columns matrix given arguments for rows and columns.

We first setup a test for this function in a file named matrices.py:

Running this returns in a failing test:

**********************************************************************
File "matrices.py", line 3, in __main__.make_matrix
Failed example:
    make_matrix(3, 5)
Expected:
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
Got nothing
**********************************************************************
1 items had failures:
   1 of   1 in __main__.make_matrix
***Test Failed*** 1 failures.

The test fails because the body of the function contains only a single triple quoted string and no return statement, so it returns None. Our test indicates that we wanted it to return a matrix with 3 rows of 5 columns of zeros.

The rule in using TDD is to use the simplest thing that works in writing a solution to pass the test, so in this case we can simply return the desired result:

Running this now the test passes, but our current implementation of make_matrix always returns the same result, which is clearly not what we intended. To fix this, we first motivate our improvement by adding a test:

which as we expect fails:

**********************************************************************
File "matrices.py", line 5, in __main__.make_matrix
Failed example:
    make_matrix(4, 2)
Expected:
    [[0, 0], [0, 0], [0, 0], [0, 0]]
Got:
    [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
**********************************************************************
1 items had failures:
   1 of   2 in __main__.make_matrix
***Test Failed*** 1 failures.

This technique is called test-driven because code should only be written when there is a failing test to make pass. Motivated by the failing test, we can now produce a more general solution:

This solution appears to work, and we may think we are finished, but when we use the new function later we discover a bug:

We wanted to assign the element in the second row and the third column the value 7, instead, all elements in the third column are 7!

Upon reflection, we realize that in our current solution, each row is an alias of the other rows. This is definitely not what we intended, so we set about fixing the problem, first by writing a failing test:

With a failing test to fix, we are now driven to a better solution:

Using TDD has several benefits to our software development process. It:

• helps us think concretely about the problem we are trying solve before we attempt to solve it.
• encourages breaking down complex problems into smaller, simpler problems and working our way toward a solution of the larger problem step-by-step.
• assures that we have a well developed automated test suite for our software, facilitating later additions and improvements.

Strings and lists

Python has a command called list that takes a sequence type as an argument and creates a list out of its elements.

There is also a str command that takes any Python value as an argument and returns a string representation of it.

As we can see from the last example, str can't be used to join a list of characters together. To do this we could use the join function in the string module:

Two of the most useful functions in the string module involve lists of strings. The split function breaks a string into a list of words. By default, any number of whitespace characters is considered a word boundary:

An optional argument called a delimiter can be used to specify which characters to use as word boundaries. The following example uses the string ai as the delimiter:

Notice that the delimiter doesn't appear in the list.

string.join is the inverse of string.split. It takes two arguments: a list of strings and a separator which will be placed between each element in the list in the resultant string.

Exercises

1. Write a loop that traverses: and prints the length of each element. What happens if you send an integer to len? Change 1 to 'one' and run your solution again.
2. Open a file named ch09e02.py and with the following content: Add each of the following sets of doctests to the docstring at the top of the file and write Python code to make the doctests pass.

   #.

   #.

   #.

   #.

   Only add one set of doctests at a time. The next set of doctests should not be added until the previous set pass.

1. . What is the Python interpreter's response to the following?

The three arguments to the range function are start, stop, and step, respectively. In this example, start is greater than stop. What happens if start < stop and step < 0? Write a rule for the relationships among start, stop, and step.

#.

Draw a state diagram for a and b before and after the third line is executed.

1. What will be the output of the following program? Provide a detailed explanation of the results.
2. Open a file named ch09e06.py and use the same procedure as in exercise 2 to make the following doctests pass:

   #.

   #.

   #.

3. Write a function add_lists(a, b) that takes two lists of numbers of the same length, and returns a new list containing the sums of the corresponding elements of each. add_lists should pass the doctests above.
4. Write a function mult_lists(a, b) that takes two lists of numbers of the same length, and returns the sum of the products of the corresponding elements of each. Verify that mult_lists passes the doctests above.
5. Add the following two functions to the matrices.py module introduced in the section on test-driven development: Your new functions should pass the doctests. Note that the last doctest in each function assures that add_row and add_column are pure functions. ( hint: Python has a copy module with a function named deepcopy that could make your task easier here. We will talk more about deepcopy in chapter 13, but google python copy module if you would like to try it now.)
6. Write a function add_matrices(m1, m2) that adds m1 and m2 and returns a new matrix containing their sum. You can assume that m1 and m2 are the same size. You add two matrices by adding their corresponding values. Add your new function to matrices.py and be sure it passes the doctests above. The last two doctests confirm that add_matrices is a pure function.

#. Write a function scalar_mult(n, m) that multiplies a matrix, m, by a

scalar, n. Add your new function to matrices.py and be sure it passes the doctests above.

#.

Add your new functions to matrices.py and be sure it passes the doctests above.

#.

Describe the relationship between string.join(string.split(song)) and song. Are they the same for all strings? When would they be different?

#. Write a function replace(s, old, new) that replaces all occurrences of

old with new in a string s. Your solution should pass the doctests above. Hint: use string.split and string.join.