Lab 6:

Lists (refresher), tuples. Mutable objects, references. Shallow vs deep copies.#

The purpose of this week’s lab is to:

Review Python’s built-in sequence types: lists and tuples.
Contrast a reference to an object with a copy of an object, in the context of lists.

Note: If you do not have time to finish all exercises (in particular, the programming problems) during the lab time, you can continue working on them later.

If you have any questions about or difficulties with any of the material covered in the course so far, ask your tutor for help during the lab.

Sequence type: lists#

Remember that:

list is a sequence type.
A list can contain elements of any type - including a mix of elements of different types in the same list.
List is a mutable type. (What does mutable mean? This is explained in Chapter 10 in Downey’s book.)

Exercise 0#

Operations on python’s built-in sequence types are summarised in this section of the python library reference. You may want to revisit Lab 5 to remind yourself of how indexing, slicing and operations on sequences work.

Because lists are mutable but strings are not, you can assign a new element to an index in the list, or a list to a slice of the list, but you cannot do this with strings. Try the following:

In [1]: a_str = "acd"

In [2]: a_str[1]
Out [2]: ...

In [3]: a_str[1] = 'b'

In [4]: a_str
Out [4]: ...

In [5]: a_list = [1,3,2,4]

In [6]: a_list[1] = 2

In [7]: a_list
Out [7]: ...

In [8]: a_list[2:3] = [5,7]

In [9]: a_list
Out [9]: ...

Mutable objects and references#

In python, every value computed by the interpreter is an object. An object in python has:

An identity: This is a number assigned by the python interpreter when an object is created. You can access this number using the id function. Examining the identity of an object is typically not useful in the programs you write, but it will sometimes help you to understand what is happening.
Some attributes: This is information about the object. An attribute that every object has is a type, which tells us (and the python interpreter) what kind of object it is. Other attributes tell us something about the “content” of the object (for example, if the object is of type int, that is, an integer, what integer it is).

When we assign a value to variable, the variable name is associated with a reference to the object; that is, essentially, the objects identity. Several variables can refer to the same objects.

A mutable object is one that can be modifed. This means that we can change the object’s attributes. The object’s identity remains unchanged.

Downey’s book describes mutable objects (specifically, lists) and aliasing (multiple names referring to the same object) in Chapter 10.

Exercise 1(a)#

The following code attempts to construct a table containing the first three rows of the periodic table. Run the following commands in the python shell:

In [1]: row1=["H","He"]
In [2]: row2=["Li","Be","B","C","N","O","F","Ar"]
In [3]: row3=["Na","Mg","Al","Si","P","S","Cl","Ne"]
In [4]: ptable=row1
In [5]: ptable.extend(row2)
In [6]: ptable.extend(row3)

What is the value of ptable now?
What is the value of row1 now? Is this what you expected?
Correct the error in row2 (Ar should be Ne) by executing a command of the form row2[?] = ?. (The question mark means it is for you to figure out what is the right index to change. You should not write a literal ?.) What happens to ptable as a result of this assignment?
Correct the error in row3 (Ne should be Ar) by executing a command of the form ptable[?] = ?. What happens to row3 as a result of this assignment?

Give the above a try yourself first.

After that, try stepping through and visualising the example using the on-line tool pythontutor.com here. We have already copied the code in and set the right settings for you in the link above. Just click the “Visualize Execution” button to start.
See if what is happening matches what you expected to happen.

To help explain what is happening, you can also use the id function to see the identities of the objects referenced by each of the variables:

In [7]: id(row1)
Out [7]: ...
In [8]: id(row2)
Out [8]: ...
In [9]: id(row3)
Out [9]: ...
In [10]: id(ptable)
Out [10]: ...

You should find that row1 and ptable both reference the same object (a list), but that the contents of row2 and row3 were copied into ptable.

Exercise 1(b)#

Now execute the following commands (make sure you redefine the rows):

In [1]: row1 = ["H","He"]
In [2]: row2 = ["Li","Be","B","C","N","O","F","Ar"]
In [3]: row3 = ["Na","Mg","Al","Si","P","S","Cl","Ne"]
In [4]: ptable = [row1]
In [5]: ptable.append(row2)
In [6]: ptable.append(row3)

What is the value of ptable now? How does this differ from what you had in Exercise 1(a)?
What is the value of row1 now? How does it differ from what you had in Exercise 1(a)?
To get the first element of the first row from ptable, you would use the expression ptable[0][0]. Write the expressions to get the sixth element from the second row (“O”) and the second element from the third row (“Mg”). Use only the ptable variable, not row2 or row3.
Correct the error in row 2 (Ar should be Ne) by executing a command of the form row2[?] = ?. Does this also change ptable?
Correct the error in row 3 (Ne should be Ar) by executing a command of the form ptable[?][?] = ?. Does this change row3?

Again, you can use the id function to see the identities of the objects involved (try both id(ptable) and id(ptable[0])). You should find that each element in ptable is a reference to one of the row lists.

Again, if you want to visualise what is going on, try pythontutor.com. Copy the code you want to test into the text box and click the “Visualize Execution” button. Remember to make sure you have selected “Python 3” in the menu above where you enter the code

Shallow and deep copies#

In Exercise 1(a) you assigned ptable the list referenced by row1 via the statement ptable = row1. Subsequent operations showed that ptable and row1 referenced the same object (list). How do we actually make a copy of a list?

Exercise 1(c)#

Execute the following commands:

In [1]: row2=['Li', 'Be', 'B', 'C', 'N', 'O', 'F', 'Ar']
In [2]: ptable1=["H","Xe",row2]
In [3]: ptable2=ptable1[:]

Is ptable1 a list, a list of lists or a mix of both? (Print it out!)
Correct element “Xe” in ptable2 to be “He”. Is the change propagated to ptable1?
Correct element “Ar” in ptable2 to be “Ne”. Is the change propagated to ptable1 and to row2?

You should find that after executing ptable2=ptable1[:] ptable2 is a copy of ptable1 (not having the same id) but the third element is a reference to row2. The effect of adding [:] to the ptable2=ptable1 assignment is to create a so-called shallow copy of ptable1.

Unclear? Visualize the code in pythontutor.com, or ask your tutor for help.

Exercise 1(d)#

Execute the following commands

In [1]: row2=['Li', 'Be', 'B', 'C', 'N', 'O', 'F', 'Ar']
In [2]: ptable1=["H","Xe",row2]
In [3]: import copy
In [4]: ptable2=copy.deepcopy(ptable1)

Now correct the “Ar” to “Ne” by assigning the right element of ptable2. Inspect to see whether the elements of ptable1 or row2 have changed. (You should find no changes.)

NOTE: Think carefully before using deepcopy: it is much slower and consumes more memory than shallow copy; it may also cause problems with circular references (such as list containing a reference to itself). Any problems with shared references can always be avoided by thinking more carefully about how you have structured your code.

Exercise 2: Debugging#

Just like strings, the list data type has several useful methods. For example, read help(list.append), help(list.insert) and help(list.extend) to see the documentation of some of the methods that modify lists. Modifying methods and operations for mutable sequence types (i.e., list) are summarised in this section of the python documentation.

Below are two attempts to write a function, make_list_of_lists, that creates a list of n lists of increasing ranges of integers. The first entry in the returned list should be an empty list, the second a list of length one, ending with the number 1, and so on. For example, make_list_of_lists(3) should return [ [], [1], [1, 2] ]. (Note that n must be a non-negative integer.) However, both functions are incorrect. Locate the error in each function and explain why it goes wrong.

Function 1#

def make_list_of_lists(n):
	the_list = []
	sublist = []
	while n > 0:
		the_list.append(sublist)
		sublist.append(len(sublist) + 1)
		n = n - 1
	return the_list

Function 2#

def make_list_of_lists(n):
	the_list = []
	sublist = []
	for i in range(n):
		the_list.extend(sublist)
		sublist = sublist.insert(len(sublist), i)
	return the_list

Sequence type: tuples#

Python has another built-in sequence type, called a tuple. Like a list, tuples can contain any type of value, including a mix of value types.
The difference between type list and type tuple is that tuples are immutable.

To create a tuple, you only need to write its elements separated by commas:

In [1]: aseq = 1,2,3,4

In [2]: type(aseq)
Out [2]: ...

It is common practice to write a tuple in parentheses, like this:

In [1]: aseq = (1,2,3,4)

In [2]: type(aseq)
Out [2]: ...

and the python interpreter will usually print tuples enclosed in parentheses. However, remember that it is the comma that creates the tuple, not the parentheses! To see this, try the following:

In [1]: x = (1)

In [2]: type(x)
Out [2]: ...

In [3]: x = 1,

In [4]: type(x)
Out [4]: ...

There is one exception: To create an empty tuple (a tuple with length zero), you have to put a comma between nothing and nothing! Typing x = , does not work. Instead, use an empty pair of parentheses to create an empty tuple, like this: x = ().

Exercise 3#

Retry the tests you did in Exercise 2 in Lab 5 with tuple values:

In [1]: aseq = (1,2,3,4)

In [2]: bseq = 1,3,2,4

In [3]: type(aseq)        # 1. what type of sequence is this?
Out [3]: ...
						  # 2 - 9 as before.

Also try assigning to an element and to a slice of the tuple, as in Exercise 0: this should give you an error, because the tuple type is immutable.

Programming problems#

Note: We don’t expect everyone to finish these problems during the lab time. You should continue working on them later.

Pop and slice#

The list method pop(position) removes the element in the given position from the list (read help(list.pop) or the on-line documentation).

(a) Write a function allbut(a_list, index), which takes as arguments a list and an index, and returns a new list with all elements of the argument list (in the order they were) except for the element at index. The argument list should not be modified by the function.

Example:

In [1]: my_list = [1,2,3,4]

In [2]: my_short_list = allbut(my_list, 2)

In [3]: print(my_short_list)
[1, 2, 4]

In [4]: print(my_list)
[1, 2, 3, 4]

(b) A slice expression, a_list[start:end], returns a new list with the elements from start to end - 1 of the list.

Write a function slice_in_place(a_list, start, end), which takes as arguments a list and two indices, and modifies the argument list so that it is equal to the result of the slice expression a_list[start:end]. The function should not return any value.

Example:

In [1]: my_list = [1, 2, 3, 4]

In [2]: slice_in_place(my_list, 1, 3)

In [3]: print(my_list)
[2, 3]

Advanced: Make your slice_in_place function work with both positive and negative indices (like slicing does).

List shuffle#

Sorting a list puts the elements in order; shuffling it puts them in (more or less) disorder. The python module random implements a function called shuffle which randomly shuffles a list. Here, we will look at a deterministic (non-random) shuffle of a list. A “perfect shuffle” (also known by many other names) cuts the list in two parts, as evenly sized as possible, then interleaves the elements of the two parts to form the shuffled list.

(a) Write a function perfect_shuffle(a_list) which takes as argument a list and returns the perfect shuffle of the list. The function should not modify the argument list.

Example:

In [1]: my_list = [1, 2, 3, 4, 5, 6]

In [2]: my_shuffled_list = perfect_shuffle(my_list)

In [3]: print(my_shuffled_list)
[1, 4, 2, 5, 3, 6]

In [4]: print(my_list)
[1, 2, 3, 4, 5, 6]

(b) Write a function perfect_shuffle_in_place(a_list) which takes as argument a list and performs the perfect shuffle on the list. The function should modify the list, and not return any value. After the function call, the argument list should have the same length and contain the same elements; only the order of them should change.

Example:

In [1]: my_list = [1, 2, 3, 4, 5, 6]

In [2]: perfect_shuffle_in_place(my_list)

In [3]: print(my_list)
[1, 4, 2, 5, 3, 6]

Advanced: Write a program that repeatedly shuffles a list using this function and counts how many shuffles are done before the list becomes equal to the original list.

Nested lists#

A list that contains lists is sometimes called nested. We define the nesting depth of a list as follows:

A list that does not contain any list has a nesting depth of zero
A list that contains lists has a nesting depth equal to the maximum nesting depth of the lists it contains, plus one.

Note that “a list that contains lists” can also contain values that are not lists.

For example, the nesting depth of [[1,2], [2,4]] is 1, while the nesting depth of [1, [2], [[3], [[4], 5]]] is 3.

Write a function that takes as argument a list and returns its nesting depth.

What does your function return when called with the list [[[]]]? (and is that what it should return?)

Search this site

Semester 1, 2024: Lab 6

Lab 6:

Lists (refresher), tuples. Mutable objects, references. Shallow vs deep copies.#

Sequence type: lists#

Exercise 0#

Mutable objects and references#

Exercise 1(a)#

Exercise 1(b)#

Shallow and deep copies#

Exercise 1(c)#

Exercise 1(d)#

Exercise 2: Debugging#

Function 1#

Function 2#

Sequence type: tuples#

Exercise 3#

Programming problems#

Pop and slice#

List shuffle#

Nested lists#