Bags inside bags: containers and copying

At ten in the morning, the teacher arrives at the center with a photo of a soaked towel. The kit was definitely cloned with copy(), they say, yet both classes' towels got wet.

Supervisor Do Miran turns a kit inside out. There are two outer bags. But inside the outer bags there are no items, only tags. "They bought new outer bags and nothing else. The tags inside still point to the same towel bag."

3-1. Inside a bag there are tags (10 min)

Containers such as lists, tuples, dict and set do not hold the objects themselves. They hold references to objects, in other words tags. Just as names were tags in Lesson 1, each slot of a list is a tag too.

That is why the same object can sit in several slots at once.

row = [0, 0]
pair = [row, row]
row.append(7)
print(pair)
# [[0, 0, 7], [0, 0, 7]]
print(pair[0] is pair[1])
# True

The place where this causes the most accidents is the two-dimensional list.

grid = [[0] * 3] * 3
grid[0][0] = 9
print(grid)
# [[9, 0, 0], [9, 0, 0], [9, 0, 0]]
print(grid[0] is grid[1] is grid[2])
# True

[0] * 3 builds one list. The outer * 3 does not copy that list three times; it puts in three tags that all point to the same list. One bag, three tags.

The inner [0] * 3, on the other hand, is fine. Every slot points to the same integer 0, but integers are immutable, so row[0] = 9 merely moves that slot's tag to 9. Sharing becomes a problem when the shared object is mutable.

The fix is a comprehension that builds a new list for every row.

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

3-2. Shallow copy: only the outer bag is new (10 min)

There are five common ways to copy a list. They all give the same result.

import copy
kit = [["water", "map"], ["snack"]]
copies = [kit[:], list(kit), kit.copy(), copy.copy(kit)]
print([c is kit for c in copies])
# [False, False, False, False]
print([c[0] is kit[0] for c in copies])
# [True, True, True, True]

This is a shallow copy. The outer bag is new, and the tags inside are moved over into it as they are. So changing the outer bag and changing an inner bag have different results.

a = kit[:]
a.append(["hat"])          # add a slot to the outer bag: the original is unchanged
print(len(kit), len(a))
# 2 3
a[0].append("towel")       # change an inner bag: visible in the original too
print(kit[0])
# ['water', 'map', 'towel']

dict works the same way. d.copy(), dict(d) and {**d} are all shallow copies.

rooms = {"class1": ["water"], "class2": ["map"]}
dup = rooms.copy()
dup["class3"] = []               # new key: not in the original
dup["class1"].append("tea")      # shared list: visible in the original too
print(rooms)
# {'class1': ['water', 'tea'], 'class2': ['map']}

Below, try =, a shallow copy and a deep copy on the same nested list. Line 4 changes an inner bag, and line 5 adds a slot to the outer bag.

3-3. Deep copy: new all the way down (9 min)

copy.deepcopy follows the bags inside the bag, and the bags inside those, and builds new ones for all of them.

import copy
kit = [["water", "map"], ["snack"]]
deep = copy.deepcopy(kit)
deep[0].append("rain")
print(kit[0], deep[0], deep[0] is kit[0])
# ['water', 'map'] ['water', 'map', 'rain'] False

A copy that follows everything to the bottom has two traps: meeting the same bag twice, and a bag that contains itself, so there is no bottom. deepcopy solves both with a ledger called memo. It records every object it has already copied as {id(original): copy}, and when it meets one again, it uses the copy from the ledger.

x = [1]
pair = [x, x]
p2 = copy.deepcopy(pair)
print(p2[0] is p2[1], p2[0] is x)
# True False

memo = {}
copy.deepcopy(pair, memo)
print(id(x) in memo)
# True

Two slots that were the same bag in the original are the same bag in the copy too. Even the sharing is copied faithfully.

A list that contains itself does not make it loop forever either. When you print such a list, Python abbreviates it as [...].

a = []
a.append(a)
print(a)
# [[...]]
b = copy.deepcopy(a)
print(b[0] is b, b is a)
# True False

• A user-defined class can decide how it is copied by defining __copy__ and __deepcopy__ methods. Knowing that they exist is enough for now.
• A deep copy walks the entire object graph, so it is slow and uses a lot of memory. Often it is better to rebuild only the levels you need.

3-4. Sealed bags are not copied (6 min)

Immutable objects never change, so there is no reason to make a copy of them. copy simply returns the original.

import copy
t = (1, 2)
print(copy.copy(t) is t, copy.deepcopy(t) is t)
# True True
s = "gate"
print(copy.deepcopy(s) is s)
# True

If a tuple contains a mutable object, though, the story changes. A shallow copy still returns the original, but a deep copy has to build a new list inside, so it builds a new tuple.

t2 = (1, [2])
print(copy.copy(t2) is t2)
# True
dt = copy.deepcopy(t2)
print(dt is t2, dt == t2, dt[1] is t2[1])
# False True False

The same goes for strings inside a deep-copied list. The list is new, but the "map" inside it is the same string object as in the original.

kit = [["map"], ["snack"]]
deep = copy.deepcopy(kit)
print(deep[0] is kit[0], deep[0][0] is kit[0][0])
# False True

Even a deep copy does not repack sealed bags. Something that cannot change is safe to share.

3-5. copy.replace(): a new object with a few parts changed (5 min)

When you want to "modify" an immutable object, you build a new object with a few parts changed. Since 3.13, copy.replace() does this in one uniform way. Objects such as dataclasses with frozen=True, namedtuple and datetime.date support it.

import copy
from dataclasses import dataclass
from collections import namedtuple

@dataclass(frozen=True)
class Ticket:
    gate: str
    seat: str

tk = Ticket("A1", "12C")
tk2 = copy.replace(tk, seat="14F")
print(tk, tk2)
# Ticket(gate='A1', seat='12C') Ticket(gate='A1', seat='14F')

Pass = namedtuple("Pass", "gate seat")
print(copy.replace(Pass("A1", "12C"), gate="B7"))
# Pass(gate='B7', seat='12C')

tk.seat = "1A"
# dataclasses.FrozenInstanceError: cannot assign to field 'seat'

The original tk stays as it is, and a new object appears that differs only in the changed field. Using it on an object that does not support it (a list, say) raises TypeError: replace() does not support list objects.

Case closed (10 min)

Let's look at the teacher's code again.

import copy
kit = [["towel", "notebook"], ["raincoat"]]
class1 = kit.copy()
class2 = kit.copy()
print(class1 is class2, class1[0] is class2[0])
# False True
class1[0][0] = "wet towel"
print(class2[0])
# ['wet towel', 'notebook']

The outer bags were different, but the tag in the first slot of each pointed to the same towel pouch. The water was spilled into that one and only pouch. There are two ways to fix it.

kit = [["towel", "notebook"], ["raincoat"]]
class1 = copy.deepcopy(kit)
class2 = copy.deepcopy(kit)
class1[0][0] = "wet towel"
print(class2[0], class1[0] is class2[0])
# ['towel', 'notebook'] False

def new_kit():
    return [["towel", "notebook"], ["raincoat"]]   # a new bag on every call
print(new_kit()[0] is new_kit()[0])
# False

Writing a function that builds the kit removes the original to copy from altogether. Every call packs everything from scratch, so there is nothing to share.

After the teacher leaves, Pin brings up an X-ray image of conveyor 13. The two ghost bags show up as if each were inside the other. The supervisor types one line on the screen.

a = []
b = [a]
a.append(b)
print(a)
# [[[...]]]

"Bags holding each other, huh. Maybe that's why they don't get cleared even without tags." She slips the image into a folder.

Exercises

1. If you run board[0].append("x") on board = [[]] * 2, what does board become? Fix it with a comprehension.
2. With d = {"a": [1]} and e = dict(d), predict whether e["a"].append(2) and e["b"] = [3] each show up in d.
3. With x = [1], y = [x, x], z = copy.deepcopy(y), what is z[0] is z[1]? Think about what would happen without memo, too.