Think Python for CS114 20 List operations 22 The in operator

Chapter 21 Aliasing

If a refers to an object and you assign b = a, then both variables refer to the same object. To check whether two variables refer to the same object, you can use the is operator:

⬇

>>> a = [1, 2, 3]

>>> b = a

>>> b is a

True

The state diagram looks like Figure 21.1.

The association of a variable with an object is called a reference. In this example, there are two references to the same object.

An object with more than one reference has more than one name, so we say that the object is aliased.

If the aliased object is mutable, changes made with one alias affect the other:

⬇

>>> b[0] = 42

>>> a

[42, 2, 3]

Although this behavior can be useful, it is error-prone. In general, it is safer to avoid aliasing when you are working with mutable objects.

For immutable objects like strings, aliasing is not as much of a problem. In this example:

⬇

a = 'banana'

b = 'banana'

It almost never makes a difference whether a and b refer to the same string or not.

21.1 List arguments

When you pass a list to a function, the function gets a reference to the list. If the function modifies the list, the caller sees the change. For example, delete_head removes the first element from a list:

⬇

def delete_head(t: list[any]) -> None:

t.pop(0)

Here’s how it is used:

⬇

>>> letters = ['a', 'b', 'c']

>>> delete_head(letters)

>>> letters

['b', 'c']

The parameter t and the variable letters are aliases for the same object. The stack diagram looks like Figure 21.2.

Since the list is shared by two frames, I drew it between them.

It is important to distinguish between operations that modify lists and operations that create new lists. For example, the append method modifies a list, but the + operator creates a new list.

Here’s an example using append:

⬇

>>> t1 = [1, 2]

>>> t2 = t1.append(3)

>>> t1

[1, 2, 3]

>>> t2

None

The return value from append is None.

Here’s an example using the + operator:

⬇

>>> t3 = t1 + [4]

>>> t1

[1, 2, 3]

>>> t3

[1, 2, 3, 4]

The result of the operator is a new list, and the original list is unchanged.

This difference is important when you write functions that are supposed to modify lists. For example, this function does not delete the head of a list:

⬇

def bad_delete_head(t: list[any]) -> None:

t = t[1:] # WRONG!

The slice operator creates a new list and the assignment makes t refer to it, but that doesn’t affect the caller.

⬇

>>> t4 = [1, 2, 3]

>>> bad_delete_head(t4)

>>> t4

[1, 2, 3]

At the beginning of bad_delete_head, t and t4 refer to the same list. At the end, t refers to a new list, but t4 still refers to the original, unmodified list.

An alternative is to write a function that creates and returns a new list. For example, tail returns all but the first element of a list:

⬇

def tail(t: list[any]) -> list[any]:

return t[1:]

This function leaves the original list unmodified. Here’s how it is used:

⬇

>>> letters = ['a', 'b', 'c']

>>> rest = tail(letters)

>>> rest

['b', 'c']

21.2 Debugging

Careless use of lists (and other mutable objects) can lead to long hours of debugging. Here are some common pitfalls and ways to avoid them:

1.

Most list methods modify the argument and return None. This is the opposite of the string methods, which return a new string and leave the original alone.

If you are used to writing string code like this:

⬇

word = word.strip()

It is tempting to write list code like this:

⬇

t = t.sort() # WRONG!

Because sort returns None, the next operation you perform with t is likely to fail.

Before using list methods and operators, you should read the documentation carefully and then test them in interactive mode.
2.

Make copies to avoid aliasing.

If you want to use a method like sort that modifies the argument, but you need to keep the original list as well, you can make a copy.

⬇

>>> t = [3, 1, 2]

>>> t2 = t[:]

>>> t2.sort()

>>> t

[3, 1, 2]

>>> t2

[1, 2, 3]

In this example you could also use the built-in function sorted, which returns a new, sorted list and leaves the original alone.

⬇

>>> t2 = sorted(t)

>>> t

[3, 1, 2]

>>> t2

[1, 2, 3]

21.3 Glossary

list:: A sequence of values.
element:: One of the values in a list (or other sequence), also called items.
nested list:: A list that is an element of another list.
accumulator:: A variable used in a loop to add up or accumulate a result.
augmented assignment:: A statement that updates the value of a variable using an operator like +=.
reduce:: A processing pattern that traverses a sequence and accumulates the elements into a single result.
map:: A processing pattern that traverses a sequence and performs an operation on each element.
object:: Something a variable can refer to. An object has a type and a value.
equivalent:: Having the same value.
identical:: Being the same object (which implies equivalence).
reference:: The association between a variable and its value.
aliasing:: A circumstance where two or more variables refer to the same object.
delimiter:: A character or string used to indicate where a string should be split.

21.4 Exercises

Exercise 21.1.

Write a function called nested_sum that takes a list of lists of integers and adds up the elements from all of the nested lists. For example:

⬇

>>> t = [[1, 2], [3], [4, 5, 6]]

>>> nested_sum(t)

Exercise 21.2.

Write a function called cumsum that takes a list of numbers and returns the cumulative sum; that is, a new list where the $i$ th element is the sum of the first $i+1$ elements from the original list. For example:

⬇

>>> t = [1, 2, 3]

>>> cumsum(t)

[1, 3, 6]

Exercise 21.3.

Write a function called middle that takes a list and returns a new list that contains all but the first and last elements. For example:

⬇

>>> t = [1, 2, 3, 4]

>>> middle(t)

[2, 3]

Exercise 21.4.

Write a function called chop that takes a list, modifies it by removing the first and last elements, and returns None. For example:

⬇

>>> t = [1, 2, 3, 4]

>>> chop(t)

>>> t

[2, 3]

Exercise 21.5.

Write a function called is_sorted that takes a list as a parameter and returns True if the list is sorted in ascending order and False otherwise. For example:

⬇

>>> is_sorted([1, 2, 2])

True

>>> is_sorted(['b', 'a'])

False

Exercise 21.6.

Two words are anagrams if you can rearrange the letters from one to spell the other. Write a function called is_anagram that takes two strings and returns True if they are anagrams.

Exercise 21.7.

Write a function called has_duplicates that takes a list and returns True if there is any element that appears more than once. It should not modify the original list.

Exercise 21.8.

This exercise pertains to the so-called Birthday Paradox, which you can read about at http://en.wikipedia.org/wiki/Birthday_paradox.

If there are 23 students in your class, what are the chances that two of them have the same birthday? You can estimate this probability by generating random samples of 23 birthdays and checking for matches. Hint: you can generate random birthdays with the randint function in the random module.

Exercise 21.9.

Write a function that reads the file words.txt and builds a list with one element per word. Write two versions of this function, one using the append method and the other using the idiom t = t + [x]. Which one takes longer to run? Why?

Exercise 21.10.

To check whether a word is in the word list, you could use the in operator, but it would be slow because it searches through the words in order.

Because the words are in alphabetical order, we can speed things up with a bisection search (also known as binary search), which is similar to what you do when you look a word up in the dictionary (the book, not the data structure). You start in the middle and check to see whether the word you are looking for comes before the word in the middle of the list. If so, you search the first half of the list the same way. Otherwise you search the second half.

Either way, you cut the remaining search space in half. If the word list has 113,809 words, it will take about 17 steps to find the word or conclude that it’s not there.

Write a function called in_bisect that takes a sorted list and a target value and returns True if the word is in the list and False if it’s not.

Or you could read the documentation of the bisect module and use that!

Exercise 21.11.

Two words are a “reverse pair” if each is the reverse of the other. Write a program that finds all the reverse pairs in the word list.

Exercise 21.12.

Two words “interlock” if taking alternating letters from each forms a new word. For example, “shoe” and “cold” interlock to form “schooled”. Credit: This exercise is inspired by an example at http://puzzlers.org.

1.

Write a program that finds all pairs of words that interlock. Hint: don’t enumerate all pairs!
2.

Can you find any words that are three-way interlocked; that is, every third letter forms a word, starting from the first, second or third?