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.
Codebench#
Exercise 2: Debugging
and the Programming Problems
in this lab are available in
CodeBench under the Lab6 exercise set.
Make sure you SUBMIT your programs for these programming problems
before you close CodeBench. Ask your tutor for help if you are stuck in CodeBench.
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 formrow2[?] = ?
. (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 toptable
as a result of this assignment? - Correct the error in
row3
(Ne should be Ar) by executing a command of the formptable[?] = ?
. What happens torow3
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 expressionptable[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 theptable
variable, notrow2
orrow3
. - Correct the error in row 2 (Ar should be Ne) by executing a
command of the form
row2[?] = ?
. Does this also changeptable
? - Correct the error in row 3 (Ne should be Ar) by executing a
command of the form
ptable[?][?] = ?
. Does this changerow3
?
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 toptable1
? - Correct element “Ar” in
ptable2
to be “Ne”. Is the change propagated toptable1
and torow2
?
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 ofptable1
orrow2
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?)