Lists

0. Learning objectives

Create lists to hold a bunch of ordered values
Perform operations on lists, such as slicing, multiplication, concatenation and appending
Recognize and implement map/reduce/filter patterns
Build lists using a single line of code with list comprehensions

1. Lists

So far, the only variable that we can iterate on is a string. Another useful type of variable is a list, which is an ordered collection of things. I know the word "things" sounds vague, but it's true: lists can store anything! The important thing to remember is that the items in a list are ordered.

We can write out a list as a comma-separated set of values with square brackets ([]) around them. For example, try typing x = [1, 3, 8, 15] in the Brython. Now type type(x). Python should tell you that x is of type list (you can get the same result by checking directly the list without assigning it first to a variable: type([1, 3, 8, 15])).

Many of the operations we performed on strings are available for lists as well. You can retrieve the number of items in the list using the len function. Try typing len(x) - you should see 4. Just like strings, we can index items in a list. Again, these indices start at index 0 and go up until the length of the list minus one. For our current list, this will be len(x) - 1, which is 3. So x[3] = 15. You can also perform slicing operations, and index backwards (i.e. x[-1] will give you 15) again, just like we saw with strings. Try the following in Brython x[1:3] (and hit enter). You should see a new list [3, 8] obtained by slicing x.

Also, just like strings, we can concatenate and repeat lists. For example [2, 3] * 2 will give you a new list [2, 3, 2, 3]. You might be tempted to think that it will multiply each element of the list by the value 2 but it does NOT! One of the reasons is that, as we will see in a little bit, lists can contain a mix of elements of different types and it might be that, for some of them, the * operator performs different operations. Also [2, 3] + [3, 4] will concatenate two lists: it will create a new list in which the elements of the second list are appended to the end of the first list (following the relative ordering in the two lists). Typing this will create a new list: [2, 3, 3, 4]. Once again, it does not add the two lists item-wise, even if they have the same length.

The operations above, do not change the original lists, even if they are placed in variables. So, if x = [2, 3] and y = [3, 4], evaluating x + y will give you [2, 3, 3, 4]] but not change either x or y. So, what if I want to add one element to one of my lists? Let's say I want to add 5 to y. You might again be tempted to try y + 5 (or [3, 4] + 5)! You will get a TypeError telling you that you cannot concatenate an int to a list, but only lists to lists. One thing that you could do, is to create a list of a single element [5]. This is totally legitimate! You can then use the + operator to concatenate the two lists: y + [5]. Again though, this will not modify the value or y. To do that you have to re-assign the variable: y = y + [5].

Another option to add one element to a list, is to use .append() method (documentation). This is a function which "appends" a new item to the end of the list. For example, if x = [1, 2], then x.append(3) will append the item 3 to the end of the list x, thus changing x to the longer list [1, 2, 3] (try it out!).

There are several useful methods that come with the list type. If you are curious about functions you can use on lists, try typing dir(list) to see all the available functions. Some of the most useful ones are: append, insert, pop, remove, reverse and sort. You can find detail information about each one of them by using the help function. In this case, you have to specify an actual list or a variable that was assigned a list (e.g., help([1, 2].sort) or help(x.sort) if x is a list). Also, unfortunately, you cannot do that in Brython since it is a lightweight version of Python designed to run in the browser. Looking at the description of each function using help(), or the this documentation, will give you important information about the behavior of each method. For example, if you take a look at sort it will highlight the fact that the function it is going to perform and IN PLACE sorting which means that it will modify your original list and change it to a sorted list! Some of the methods will modify your original list, some will not. It is on you, as developer, to understand the behavior of the different methods and use the one that perform the task you are interested in.

1.0. Modifying items in a list: intro to mutability

Unlike strings, we can assign values to a list by indexing. You might have not tried this but, if you try to change a character inside a string using indexing, you will get an error. For example, if you have a string s = 'hello' and you want to change the e into an a, it would seem logical to try to assign a different character to the location of the e: s[1] = 'a'. If you try that (do it!), you will get a TypeError informing you that 'str' object does not support item assignment. In Python lingo, this means that strings are immutable, they cannot be changed. You can re-assign a different string to the same variable s, but you cannot change a character in an existing string using indexing.

The good news is that lists are mutable and you can indeed change what it is stored at each location. For example, if you created a list using x = [2, 3, 5, 35] and you type x[2] = 10, you are re-assigning the value of the list x at index 2 to be equal to 10 and your x list is now [2, 3, 10, 35]. You can even replace it with an item of a different type, for example, a string: x[2] = 'hello'. Wait, what? Yes! The items of a list can be anything.

1.1. What can I store in a list?

As a matter of fact, you can use anything as items of a list! (You can even have nothing! An empty list: el = [] - another way to create an empty list is to call list(): el = list()). You can have a list of integers, or floats, or strings, or even a list that mixes these different types. Or even a list of lists. Or even a list of lists of lists of lists. A list within a list is called a nested list. Try creating the following list: y = ['dog', 4, [1, 2, 4, 8, 16]]. How would you access the value 16 in the variable y?

solution

This list that holds [1, 2, 4, 8, 16] is stored in y[2]. So, if we index the list with y[2], we get back the list we are interested in, then we can access the 16 by indexing once again using y[2][4]. Try it out!

1.2. Looping through items in a list

To start, the in keyword works on lists just like it does on strings. It returns True if an item is somewhere "in" the list (and False otherwise). For example 5in[0, 1, 1, 2, 3, 5, 8, 13] is True since 5 is in the list (of Fibonacci numbers).

So, we can use the in keyword in conjunction with the for keyword to iterate through items in a list, just as we did with strings. See the examples below for more practice.

2. Intermission: map/filter/reduce patterns

The last example shows one of the recurring computational patterns that are very common when we are dealing with sequence of items (not just lists):

map: applies an operation (which could be a function) to all the items in a sequence. For example, doubling all the items in the list in the script above is an example of mapping.
filter: selects items from a sequence based on some criteria and create a new sequence with them. For example, create a list with only the even items in another list of numbers, or only the string that starts with the character 'o' from another list of strings, are examples of filtering.
reduce: combines the items in a sequence together and summarizes (reduces) them to a single item. For example, adding all the numbers in a number list or combining somehow (e.g., concatenating) all strings in a sting list, are examples of reducing.

Take a look at the following examples:

A couple of things to notice:

Functions can have lists as parameters. Actually you can pass pretty much anything you want as parameter to a function, as long as the function handles it appropriately for its type (e.g., you might not want to try to append to a float inside your function).
In the doubling items example, we are creating a new list instead of doing something like

The reason is that this latter example will actually modify your original list, the one you called your function with, and return it to you as well. It is totally fine, if that is what you want to do (also, the return statement above is not really necessary) but if you want to preserve the original list, you will need to create a new one in the function. In CS, functions like the in the first doubling example, are called pure functions because they only communicate with the calling program through parameters (which they do not modify) and return values. We will discuss this further when we introduce more data structures.

3. List comprehensions

Let's say we want to create a list with the values 0 through n - 1, and the value of n might be determined at some point in your script? How would you do this automatically? In other words, let's assume that after some computation, your script determines that n has the value of 10. We cannot write out [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] because we don't know that while we are writing our script. So we need to do this in terms of the general number n. We could start off by creating an empty list: x = [] (putting nothing inside of square brackets gives an empty list). Then we can loop from 0 to 9 and keep appending the current number to this list:

Since this is an extremely common situation, Python provides a nice and clean way to do this that combines the creation of the empty string, the looping and the appending (and also filtering) in a single line syntax: list comprehension.

List comprehension is what in Computer Science we call "syntactic sugar": it does exactly the same job as what we wrote before but with a different or more concise syntax (often, but not necessarily, preferred by humans). The basic structure for writing a list comprehension is:

L = [transform iteration filter] in other words L = [expression for variable in iterable if condition ]

where L is the list we are creating, variable is our iterator, the variable that iterates through some iterable (e.g., a string, a list or the result of range). This variable can be used in the expression, which will be evaluated for each item in the iterable to produce the corresponding item our new list L. The condition is optional, but it allows you to "filter out" items that you don't want to store in your new list L. Here are several examples on how you can use list comprehension:

Now that we have looked at iteration, list manipulation, and list comprehension, let's look at many different approaches to solve a simple filtering problem: given a list of word, "end up" with a list with only the words that do not contain the character 'a':