Mutation and repeated references

Mutation and repeated references

Mutation and rebinding

Problem. A cart item is a tuple: item = ("pen", [2]). Tuples are immutable, so how could item show a different price list later?

New words

  • mutable: the object's value can update in place
  • immutable: the object's value cannot update

The following table lists the common types of each kind.

Mutable Immutable
list, dict, set int, float, str, tuple

A method such as append updates a mutable object in place. A method such as "ab".upper() returns a new string and leaves the original alone. Rebinding updates no object. It moves a name.

Augmented assignment shows the difference. For a list, += updates the list in place. The expression prices + [1] builds a new list, and the assignment rebinds prices to it.

prices = [5, 8]
backup = prices
prices += [3]
print(backup)
prices = prices + [1]
print(backup)
print(prices)
[5, 8, 3]
[5, 8, 3]
[5, 8, 3, 1]

The following trace table shows the code above, one row per line.

prices backup prices is backup
[5, 8]
[5, 8] [5, 8] True
[5, 8, 3] [5, 8, 3] True
[5, 8, 3, 1] [5, 8, 3] False

Now the tuple. It holds two references, one to "pen" and one to a list. The tuple cannot swap either reference for another. The list it points to can still update.

item = ("pen", [2])
item[1].append(3)
print(item)
item[0] = "ink"
('pen', [2, 3])
TypeError: 'tuple' object does not support item assignment

So an immutable container that holds a mutable object shows a new value when that object updates. The container stays immutable, because its references stay fixed.

hash(item) raises TypeError: unhashable type: 'list'. A hash value must stay constant, and this tuple's value can update.

Recall. For pair = ([], []), which of pair[0] = [2] and pair[0].append(2) raises a TypeError?

Repeated references

Problem. The shop has three shelves with three slots each, and every slot starts at 0. How could we build this grid so that updating one shelf leaves the other shelves alone?

Repeating a list with * repeats its references. The items themselves are never copied. Let's try it.

shelves = [[0] * 3] * 3
shelves[0][0] = 9
print(shelves)
print(shelves[0] is shelves[1])
[[9, 0, 0], [9, 0, 0], [9, 0, 0]]
True

The following trace table shows the code above.

shelves[0] shelves[1] shelves[0] is shelves[1]
[0, 0, 0] [0, 0, 0] True
[9, 0, 0] [9, 0, 0] True

The outer list holds three references to one inner list. To build three inner lists, use a comprehension.

shelves = [[0] * 3 for _ in range(3)]
shelves[0][0] = 9
print(shelves)
[[9, 0, 0], [0, 0, 0], [0, 0, 0]]

The inner [0] * 3 is safe, because the repeated item is the integer 0, and an integer cannot update. Repetition is a problem only when the repeated item is mutable.

The same rule explains copies. list(prices) builds a new outer list that holds the same item references. This is a shallow copy. A change to a mutable item shows through both lists.

Recall. After table = [[]] * 2 and table[0].append("a"), what does table show, and is table[0] is table[1] True?

Sources

  • The Python Language Reference, Data model, Objects, values and types: https://docs.python.org/3.12/reference/datamodel.html
  • The Python Language Reference, Augmented assignment statements: https://docs.python.org/3.12/reference/simple_stmts.html
  • The Python Standard Library, Common Sequence Operations: https://docs.python.org/3.12/library/stdtypes.html

Cards

Which of list, str, dict and tuple are mutable?

Reveal

list and dict. The types str and tuple are immutable.

What does this code print?

a = [1]
b = a
a += [2]
a = a + [3]
print(b, a)
Reveal

[1, 2] [1, 2, 3]. The += line updated the shared list in place, so b saw the 2. The a + [3] line built a new list, and the assignment rebound a to it.

What does this code print?

t = ("a", [])
t[1].append(1)
print(t)
Reveal

('a', [1]). The tuple still holds the same two references. The list that one reference points to was updated.

What error does t[0] = "b" raise for t = ("a", []), and why?

Reveal

TypeError: 'tuple' object does not support item assignment. A tuple cannot swap one of its references for another.

What does hash(("a", [])) raise, and why?

Reveal

TypeError: unhashable type: 'list'. A hash value must stay constant, and this tuple's value can change through the list it holds.

What does grid show after these lines?

grid = [[0] * 2] * 2
grid[1][1] = 5
Reveal

[[0, 5], [0, 5]]. Repetition with * repeats references, so the outer list holds two references to one inner list.

Write one line that builds two rows of [0, 0] so that updating one row leaves the other alone.

Reveal

grid = [[0] * 2 for _ in range(2)]. The comprehension builds a new inner list on each pass.

Why is [0] * 3 safe to update, while [[0]] * 3 causes shared updates?

Reveal

The repeated item in [0] * 3 is the integer 0, and an integer cannot update. The repeated item in [[0]] * 3 is one list, and an update to it shows in every slot.

What do cp and cp[0] is orig[0] show after these lines?

orig = [[1], [2]]
cp = list(orig)
orig[0].append(9)
Reveal

cp shows [[1, 9], [2]], and cp[0] is orig[0] is True. The call list(orig) is a shallow copy: a new outer list that holds the same item references.