Two names for one list
Say you keep a class's test scores in a list and want to try a change without losing the original, so that you can go back to it. The natural first attempt is to save the list under a second name before changing it:
scores = [70, 85, 90]
backup = scores
scores[0] = 0
print(backup)It prints [0, 85, 90]: the backup changed along with the scores. The line backup = scores did not copy the list. It bound the name backup to the same list scores is bound to, so the program has one list with two names. A second name for the same object is an alias, and a change made through one alias is seen through the other. To keep a separate list, copy it: backup = scores.copy().
This lesson is about what happens when a value changes while more than one name can reach it: in a function call, in a grid built out of rows, in a loop that changes what it is reading, and in a function that remembers something between calls.
The trouble only arises for values that can change in place. Such values are called mutable: a list, a dictionary and a set can all be changed after they are made. Numbers, strings and tuples are immutable, so an alias of one is harmless. s = s + "!" builds a new string and binds s to it, and another name for the old string still sees the old text.
| Type | Mutable | Changed in place by |
|---|---|---|
list | yes | a[0] = 5, a.append(5), a.sort() |
dict | yes | d[key] = value |
set | yes | s.add(x) |
| an object of a class you wrote | yes | p.x = 5 |
int, float, bool | no | nothing: x += 1 binds x to a new number |
str | no | nothing: s + "!" builds a new string |
tuple | no | nothing, though a list stored in a tuple can still change: t[0].append(5) |
That is also why a dictionary can use the tuple (2, 3) as a key and not the list [2, 3]. A dictionary finds an entry by a hash computed from its key, so a key that changed after it was stored would no longer be found.
Step through sharing and copying
The diagram steps through three short programs with two names, a and b. Each name is drawn as an arrow to a list in the Objects column.
In the first program b[0] = 99 changes the one list both arrows point at. In the second, a.copy() made a second list, and the change lands there.
In the third, b = [7, 8] builds a new list and moves the arrow from b to it, and a still points at [1, 2, 3]. Assigning to a name rebinds the name; assigning to an element, or calling a method such as append, changes the object.
Changing elements in a loop
The variable of a for loop is a name like any other, so the same rule applies to it. for x in a: binds x to each element in turn, and x += 1 rebinds x to a new number without touching the list. To change the elements, assign to a[i].
a = [1, 2, 3]
for x in a:
x += 1
print(a)
for i in range(len(a)):
a[i] += 1
print(a)Identity and equality
Once two names can share a list, there are two different questions to ask about them: do they hold equal values, and are they the same object? The first is equality, asked with ==, and the second is identity, asked with is.
a = [1, 2, 3]
b = [1, 2, 3]
c = a
print(a == b, a is b, a is c)
c.append(4)
print(a, b)a is b is False, because the two [1, 2, 3] expressions built two lists. c.append(4) grows the one list a and c share, and b keeps its three elements.
Deeper read: adding to a list in place or building a new one
b = b + [3] builds a new list and rebinds b to it, so an alias of the old list does not see the 3. b += [3] adds 3 to the list b already points at, the way b.append(3) does, so every alias sees it.
Passing a list to a function
A function call makes aliases too. When Python calls bump(nums), it binds the parameter v to the object the argument evaluated to, as v = nums would. No list is copied, so whatever the function does to the list, the caller sees afterwards. Rebinding v inside the function, as in v = [0, 0], leaves the caller's list alone.
The diagram steps through three versions of a function that adds 10 to the first element.
Step through a call that changes a list
In the first program v reaches the caller's list, so nums becomes [11, 2]. In the second the caller passes nums.copy(), so nums still starts with 1. The third keeps the change visible at the call: more = bumped(nums) names the new list, and nums keeps its old value unless the caller writes nums = bumped(nums). Python's sorting comes in both designs: a.sort() changes the list and returns None, and sorted(a) returns a new list.
Copying time
Copying takes time: v.copy() writes all elements. Passing a list to a function copies nothing, but a copy inside a loop adds up. Say a program reads numbers and answers queries, copying the list for each one:
On the Apple M5 Pro laptop this lesson was checked on, Python 3.14 took about 17 seconds for those copies, about 0.17 milliseconds each, while a judge usually allows a second or two. Copy a list only when a function must change it and the caller still needs the original.
def total(v):
s = 0
for x in v:
s += x
return s
nums = [5, 1, 4]
print(total(nums))Python details
total(nums) passes the list itself, so total reads it without a copy. total(nums.copy()) prints the same 10 after copying all elements first.
Deeper read: a default argument that holds a list
A call that leaves out an argument can share a list as well. Python evaluates a default value once, when def runs, and every call that leaves the argument out gets that same object, so every such call shares one list:
def add(x, seen=[]):
seen.append(x)
return seen
print(add(1))
print(add(2))add(2) prints [1, 2]: the 1 from the first call is still in the shared list. The usual fix makes None the default and builds the list inside the body, which runs at every call. This is also why a data class needs field(default_factory=list) for a list field: it makes a new list for each object.
def add(x, seen=None):
if seen is None:
seen = []
seen.append(x)
return seenValues in memory
Passing a list copies nothing because of what a Python name holds. Memory is a long row of numbered bytes, and every object sits somewhere in it; the number of the byte where it starts is its address. In the standard Python, CPython, a name holds the address of its object: that is the arrow in the diagrams. b = a copies the address, not the list, and a call does the same when it binds a parameter, so passing a list of a million numbers costs no more than passing one number.
id(x) gives a number that identifies the object x is bound to; in CPython that number is the address. Two names have the same id exactly when is says they are one object, so id lets you check what the diagrams draw.
Writing through a reference and a pointer
x = [5]
r = x
print(id(r) == id(x))
r[0] = 7
print(x)Changing r[0] changes x, because r and x hold the same address, as their equal id values show. Python also gives memory back for you: once no name refers to an object, Python reclaims its bytes, which is what happened to the copy in the second program of the call diagram.
Building a grid of separate rows
Grids are a common place to meet aliasing. A grid is a list of rows, and each row is a list. Multiplying a list by a number repeats its elements, so with n, m = 3, 2, [[0] * m] * n repeats one reference to the row [0, 0] three times. The result is a list holding three references to the same row.
n, m = 3, 2
grid = [[0] * m] * n
grid[0][0] = 1
print(grid)
good = [[0] * m for _ in range(n)]
good[0][0] = 1
print(good)Setting grid[0][0] to 1 set the first element of every row, because the three rows are one list. The inner [0] * m is safe, because integers cannot change in place. The fix, [[0] * m for _ in range(n)], evaluates [0] * m once per row.
Lights Out is practice for building a grid and changing single cells of it: three rows of three lights, each switched on and off by the presses.
A 3 by 3 grid of lights starts with every light on. Pressing a light switches it and each light directly above, below, left and right of it: a light that is on goes off, and one that is off comes on. The input says how many times each light was pressed. Print the final grid, with 1 for a light that is on and 0 for a light that is off.
The input is three lines of three integers; the number in row and column is how many times that light was pressed. The output is three lines of three characters with no spaces.
Constraints
- Each count is between 0 and 100
Sample 1 · Input
1 0 0 0 0 0 0 0 1
Output
001 010 100
Sample 2 · Input
1 0 1 8 8 8 2 0 3
Output
010 011 100
Practical Computing builds a triangle row by row, each number the sum of the two above it, so each new row is a new list computed from the one before.
Shallow and deep copies
scores.copy() in the first part copied a list of numbers. A grid has two levels, and grid.copy() copies only the outer one: it makes a new list whose elements are the same rows as before. This is a shallow copy: the top level is new and everything below it is shared. A deep copy copies every level, so it shares nothing that can change with the original.
grid = [[1, 2], [3, 4]]
shallow = grid.copy()
deep = [row.copy() for row in grid]
shallow[0][0] = 9
print(grid)
deep[1][1] = 0
print(grid)Changing shallow[0][0] changed grid too, because row 0 of both is the same list. Changing deep[1][1] left grid as it was. For a grid of numbers, copying each row is enough; for data nested more deeply, copy.deepcopy(x) from the copy module copies every level.
Changing a list while reading it
Some updates are meant to happen to every element at the same moment. Four people sit in a row of seats, A, B, C and D, and everyone moves one seat to the right at once: the person in the last seat leaves, and the first seat is left empty, shown as a dot. The obvious loop copies each seat from the one on its left. The second half of the listing reads from a copy instead:
seats = ['A', 'B', 'C', 'D']
for i in range(1, 4):
seats[i] = seats[i - 1]
seats[0] = '.'
print(seats)
seats = ['A', 'B', 'C', 'D']
old = seats.copy()
for i in range(1, 4):
seats[i] = old[i - 1]
seats[0] = '.'
print(seats)The first loop prints ['.', 'A', 'A', 'A']. It set seat 1 to A, and when it reached seat 2 it read seat 1, which by then held A instead of B. A loop that writes into the list it is reading sees its own changes, so A was copied into every seat. In the second half, old holds the seats as they were before the move; the loop reads only from old and writes only to seats, and every person moves exactly one place.
Walking from the right end, seat 3 first, would also work here, because each seat is then read before it is overwritten. A copy works for any update. The next problem needs one, because no order of the loop is safe there.
children stand in a queue, each a boy (B) or a girl (G). Every second, each boy standing directly in front of a girl swaps places with her, and all these swaps happen at the same moment. Given the queue at the start, print it after seconds.
The first line holds and , and the second line the queue as a string of B and G, front first.
Constraints
Sample 1 · Input
5 1 BGGBG
Output
GBGGB
Sample 2 · Input
5 2 BGGBG
Output
GGBGB
Sample 3 · Input
4 1 GGGB
Output
GGGB
Swapping every BG pair in one pass over the queue falls into the same trap. On BGGBG, positions 1 and 2 (counting from 1) swap first, and the queue becomes GBGBG. Positions 2 and 3 now hold the boy just moved and another girl, so they swap too, and one boy moves two places in one second. Walking from the other end fails on BBGG instead. So each second the program copies the queue into old, reads only from old and writes only to the queue.
Reading from a copy and writing to the queue
n, t = map(int, input().split())
q = list(input())
for second in range(t):
old = q.copy()
for i in range(n - 1):
if old[i] == 'B' and old[i + 1] == 'G':
q[i] = 'G'
q[i + 1] = 'B'
print(''.join(q))Python details
Python strings are immutable, so list(input()) turns the line into a list of one-letter strings that the loop can change, and ''.join(q) turns it back.
old = q would make an alias instead: old would see every swap the loop makes, and the program would print GGBGB again. The copy needs q.copy().
Coloring Matrix is practice for the same idea on a grid. A quarter turn moves every cell at once, so build the turned grid as a new list: a = [[a[n - 1 - j][i] for j in range(n)] for i in range(n)] works out the whole right side from the old grid before rebinding a.
You are given two by grids and of 0s and 1s. Rotating turns it a quarter turn clockwise: every cell is replaced at the same moment, the cell in row and column taking the value that was in row and column . Can you rotate zero or more times so that every cell holding 1 in also holds 1 in ? Print Yes or No.
The first line holds , the next lines the rows of , and the lines after them the rows of .
Constraints
- Every value is 0 or 1
Sample 1 · Input
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
Output
Yes
Sample 2 · Input
2 0 0 0 0 1 1 1 1
Output
Yes
Sample 3 · Input
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
Output
No
Removing elements while looping over them
Removing elements from the list a loop is walking goes wrong the same way. Each removal moves the next element into the removed one's place, and the loop steps past it. On rows = [1, 1, 2], the loop for r in rows: if r == 1: rows.remove(r) leaves [1, 2].
Grid Compression is practice for this: it asks you to delete every row and column with no #, so a loop that removes rows as it finds them skips rows. Decide first which rows and columns stay, then build a new grid from them.
A dictionary or a set catches this mistake and a list does not: changing the size of a dictionary while a loop walks it stops the program with RuntimeError: dictionary changed size during iteration.
Functions that keep local state
So far a change that showed up somewhere else has been a bug to avoid. This part puts the same mechanism to work. At a deli counter each customer takes the next ticket from a roll: 100, then 101, then 102. A program that hands out tickets has to remember the next number between one ticket and the next.
With the functions you have so far, the program keeps the next number in a variable of its own and passes it to take, which returns the ticket and the number after it. A shop with two counters, one starting at 100 and the other at 500, needs one such variable per counter:
Two counters with the numbers passed by hand
def take(next_number):
return next_number, next_number + 1
a_next = 100
b_next = 500
ticket, a_next = take(a_next)
print(ticket)
ticket, b_next = take(b_next)
print(ticket)
ticket, a_next = take(a_next)
print(ticket)Python details
take returns two values, and ticket, a_next = ... binds one name to each.
It works, but every line that takes a ticket has to know which variable belongs to which counter and has to store the new number. Leaving out the store once, as in ticket, _ = take(a_next), gives the next customer at that counter the same ticket again.
What we want is a take that needs no arguments and gives a new number on every call. Most functions you have written so far are pure functions: their result depends only on their arguments, so the same arguments always give the same result. A ticketer cannot be pure. It needs local state: data that belongs to the function, survives from one call to the next, and cannot be reached by the rest of the program.
You have already seen where such data can live. The test returned by multiple_of(3) still knew d after multiple_of had returned, because Python keeps the frame of multiple_of as the new function's parent. A ticketer works the same way: make_ticketer(100) binds next_number to 100 in its own frame, defines take inside it and returns take. The difference is that take changes next_number instead of only reading it.
Changing it takes one new line. An assignment inside a function normally binds the name in the function's own frame. The line nonlocal next_number says the name belongs to an enclosing frame, so next_number += 1 changes the binding in the frame of make_ticketer.
Step through a ticketer
Step through the first program and watch frame f1. It stays after make_ticketer returns, because the function bound to a has f1 as its parent, and each call of a() changes the number in f1. b has a frame of its own, f2, so the program prints 100, 500 and then 101 with no variables to pass around.
Each ticketer keeps its own state, and the rest of the program reaches it only by calling the ticketer. The classes of the next lesson are built on this idea.
Deeper read: other ways to keep state in a function
Python decides which frame a name belongs to before the function runs, by looking for assignments to the name anywhere in the body. Because take assigns to next_number, Python treats it as a name of take's own frame, unless a nonlocal line says otherwise. Without that line, next_number += 1 finds no value there yet and stops with UnboundLocalError.
Another way, the one Composing Programs uses, avoids nonlocal by keeping the number inside a list. take changes state[0] and never assigns to the name state, so Python looks state up in the parent frame as usual.
def make_ticketer(next_number):
state = [next_number]
def take():
state[0] += 1
return state[0] - 1
return take
take = make_ticketer(100)
print(take(), take())Replacing a call by its value
Local state makes a program harder to reason about. With pure functions, any call can be replaced by the value it returns without changing what the program does: square(3) is 9, so square(3) + square(3) means the same as 9 + 9. Computer scientists call an expression with this property referentially transparent. A ticketer breaks it:
def square(x):
return x * x
def make_ticketer(next_number):
def take():
nonlocal next_number
next_number += 1
return next_number - 1
return take
print(square(3) + square(3), 9 + 9)
take = make_ticketer(100)
print(take() + take(), 100 + 100)Two calls of take add up to , not 200: the second call, written exactly like the first, returned 101, because the first call changed the state the two calls share. Once a function changes state, a call can no longer be replaced by its value, and to know what a line does you have to know what ran before it.
Identity matters again, too. In the diagram's program "two ticketers, both at 100", a and b are both made by make_ticketer(100), yet they are two ticketers: a() and b() both return 100. In "b = a: one ticketer, two names", b = a gives one ticketer two names, and b() returns 101 because a() already took 100. Two ticketers that hold the same number now are still different ticketers, because their numbers will move apart.
Common mistakes
Building a Python grid with
[[0] * m] * n.- Where it breaks
grid[0][0] = 1changes every row, because all the rows are one list.- The fix
- Build a new row for each index:
[[0] * m for _ in range(n)].
Updating a list in place when every element should change at the same moment.
- Where it breaks
- Moving everyone one seat right with
seats[i] = seats[i - 1]turnsA B C Dinto. A A A, because the loop reads seats it has already changed. - The fix
- Copy the list into
oldfirst, read only fromoldand write only to the list.
Copying a Python grid with
grid.copy()and then changing a cell of the copy.- Where it breaks
shallow[0][0] = 9changesgridtoo, because the rows are shared.- The fix
- Copy each row:
[row.copy() for row in grid], orcopy.deepcopy(grid)for data nested more deeply.
Leaving out
nonlocalin an inner Python function that assigns to a name of the function around it.- Where it breaks
- The first call of
take()stops withUnboundLocalError. - The fix
- Put
nonlocal next_numberat the top oftake, or keep the number in a list and changestate[0].
Declaring a C++ parameter as
vector<int> vin a function meant to change the caller's vector.- Where it breaks
- After
bump(nums)withvoid bump(vector<int> v) { v[0] += 10; },nums[0]is still 1, because the function changed a copy. - The fix
- Declare the parameter as a reference,
vector<int>& v, or return the changed vector.
Recall In the opening program, how do you save a backup of `scores` that stays the same when `scores` changes?
backup = scores.copy(). backup = scores only gives the one list a second name, so a change through scores shows through backup.
Recall A function adds 10 to the first element of the list it is given. When does the caller see the change?
Whenever the caller passes its own list: the parameter is bound to that list, so the change lands in it. Passing nums.copy() keeps the caller's list unchanged.
Recall A ticketer starts at 5. What do two calls of its `take` add up to, and why is it not 10?
11. The first call returns 5 and moves the number to 6, so the second call returns 6.
Key terms
| Term | Meaning |
|---|---|
| alias | A second name for the same object. |
| mutable | Can be changed in place after it is made. |
| immutable | Cannot be changed after it is made. |
| equality | Whether two values are the same: == in both languages. |
| identity | Whether two names refer to one object. |
| reference (C++) | Another name for an existing variable, declared with & after the type: vector<int>& b = a;. |
| pass by value | A C++ parameter like vector<int> v that receives a copy of the argument. |
| pass by reference | A C++ parameter like vector<int>& v that names the caller's variable. |
| address | The position of a value in memory; in C++, &x gives the address of x. |
| pointer | A C++ variable whose value is an address: int* p = &x;, with *p the variable it points at. |
| shallow copy | A copy of the top level only, sharing everything below it: grid.copy(). |
| deep copy | A copy of every level, sharing nothing that can change: copy.deepcopy(grid). |
| pure function | A function whose result depends only on its arguments. |
| local state | Data a function keeps from one call to the next. |
| referentially transparent | An expression that can be replaced by its value without changing what the program does. |
