3.5. Mutable and Immutable Sequences

We have seen that in many ways lists and strings are similar, but there is a major distinction between these containers. In this section, we introduce the idea for mutable and immutable sequences and reconsider lists, strings and tuples in this light.

3.5.1. Strings and Tuples are Immutable

One final thing that makes strings different from lists is that you are not allowed to modify the individual characters in the collection. It is tempting to use the [] operator on the left side of an assignment, with the intention of changing a character in a string. For example, in the following code, we would like to change the first letter of greeting.

In [1]: greeting = "Hello, world!"

In [2]: greeting[0] = 'J'            # ERROR!
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-fe47087f0508> in <module>()
----> 1 greeting[0] = 'J'            # ERROR!

TypeError: 'str' object does not support item assignment

In [3]: greeting
Out[3]: 'Hello, world!'

Instead of producing the output Jello, world!, this code produces the runtime error TypeError: 'str' object does not support item assignment.

Strings are immutable, which means you cannot change an existing string. The best you can do is create a new string that is a variation on the original.

In [4]: greeting = "Hello, world!"

In [5]: newGreeting = 'J' + greeting[1:]

In [6]: newGreeting
Out[6]: 'Jello, world!'

In [7]: greeting            # same as it was
Out[7]: 'Hello, world!'

The solution here is to concatenate a new first letter onto a slice of greeting. This operation has no effect on the original string.

Unlike lists, however, tuples are immutable. As with strings, if we try to use item assignment to modify one of the elements of the tuple, we get an error.

In [8]: julia[0] = 'X'
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-8-4a62bf349745> in <module>()
----> 1 julia[0] = 'X'

NameError: name 'julia' is not defined

Of course, even if we can’t modify the elements of a tuple, we can make a variable reference a new tuple holding different information. To construct the new tuple, it is convenient that we can slice parts of the old tuple and join up the bits to make the new tuple. So julia has a new recent film, and we might want to change her tuple. We can easily slice off the parts we want and concatenate them with the new tuple.

In [9]: julia = ("Julia", "Roberts", 1967, "Duplicity", 2009, "Actress", "Atlanta, Georgia")

In [10]: julia[2]
Out[10]: 1967

In [11]: julia[2:6]
Out[11]: (1967, 'Duplicity', 2009, 'Actress')

In [12]: len(julia)
Out[12]: 7

In [13]: julia = julia[:3] + ("Eat Pray Love", 2010) + julia[5:]

In [14]: julia
Out[14]: 
('Julia',
 'Roberts',
 1967,
 'Eat Pray Love',
 2010,
 'Actress',
 'Atlanta, Georgia')

Check your understanding

    rec-5-22: What is printed by the following statements:

    s = "Ball"
s[0] = "C"
print(s)
  • (A) Ball
  • Assignment is not allowed with strings.
  • (B) Call
  • Assignment is not allowed with strings.
  • (C) Error
  • Yes, strings are immutable.

3.5.2. Lists are Mutable

Unlike strings and tuples, lists are mutable. This means we can change an item in a list by accessing it directly as part of the assignment statement. Using the indexing operator (square brackets) on the left side of an assignment, we can update one of the list items.

In [15]: fruit = ["banana", "apple", "cherry"]

In [16]: fruit
Out[16]: ['banana', 'apple', 'cherry']

In [17]: fruit[0] = "pear"

In [18]: fruit[-1] = "orange"

In [19]: fruit
Out[19]: ['pear', 'apple', 'orange']

An assignment to an element of a list is called item assignment. Item assignment does not work for strings or tuples, as they are both immutable.

Here is the same example in codelens so that you can step through the statements and see the changes to the list elements.

(item_assign)

By combining assignment with the slice operator we can update several elements at once.

In [20]: alist = ['a', 'b', 'c', 'd', 'e', 'f']

In [21]: alist[1:3] = ['x', 'y']

In [22]: alist
Out[22]: ['a', 'x', 'y', 'd', 'e', 'f']

We can also remove elements from a list by assigning the empty list to them.

In [23]: alist = ['a', 'b', 'c', 'd', 'e', 'f']

In [24]: alist[1:3] = []

In [25]: alist
Out[25]: ['a', 'd', 'e', 'f']

We can even insert elements into a list by squeezing them into an empty slice at the desired location.

In [26]: alist = ['a', 'd', 'f']

In [27]: alist[1:1] = ['b', 'c']

In [28]: alist
Out[28]: ['a', 'b', 'c', 'd', 'f']

In [29]: alist[4:4] = ['e']

In [30]: alist
Out[30]: ['a', 'b', 'c', 'd', 'e', 'f']

Check your understanding

    rec-5-23: What is printed by the following statements?

    alist = [4, 2, 8, 6, 5]
alist[2] = True
print(alist)
  • (A) [4, 2, True, 8, 6, 5]
  • Item assignment does not insert the new item into the list.
  • (B) [4, 2, True, 6, 5]
  • Yes, the value True is placed in the list at index 2. It replaces 8.
  • (C) Error, it is illegal to assign
  • Item assignment is allowed with lists. Lists are mutable.

3.5.3. Immutable and Persistent Data Structures with pyrsistent

The act of mutating a data structure is common in both imperative and object oriented programming and can be lead to very efficient algorithms in terms of memory usage.

As noted before, this textbook focuses on functional programming, which tends to avoid mutation as much as possible. Instead, in functional programs data structures passing through functions are transformed into new data structures in the same way that the slice operator returns a new list or string.

Unfortunately, this can be inefficient unless we use specialized data structures that have been designed with this in mind. Consequently, many modern functional programming languages such as Clojure use data structures that are immutable and persistent. A persistent data structure is designed in such a way that it can be transformed efficiently through operations such as assignment with indexing and slicing.

In Python, the pyrsistent module provides a number of efficient persistent data structures that work well when using the functional programming paradigm.

You can install this module from inside IPython using the following !pip command.

In [1]: !pip install pyrsistent
Collecting pyrsistent
  Downloading pyrsistent-0.12.0.tar.gz (91kB)
    100% |████████████████████████████████| 92kB 570kB/s
Requirement already satisfied (use --upgrade to upgrade): six in /Users/tiverson/.pyenv/versions/3.5.2/envs/runestone/lib/python3.5/site-packages (from pyrsistent)
Installing collected packages: pyrsistent
  Running setup.py install for pyrsistent ... done
Successfully installed pyrsistent-0.12.0

Note

You only need to install a module once in a given python enviroment. After the initial installation, the module will continue to remain avaiable.

The pvector function from the pyrsistent module is an immutable persistent version of a list. First, we illustrate the immutability of the pvector. We are allowed to access the value of fruit at index 0, but now assign a new value at this index.

In [31]: from pyrsistent import pvector

In [32]: fruit = pvector(["banana", "apple", "cherry"])

In [33]: fruit[0]
Out[33]: 'banana'

In [34]: fruit[0] = "pear"
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-34-13775da5cf96> in <module>()
----> 1 fruit[0] = "pear"

TypeError: 'pvectorc.PVector' object does not support item assignment

Slicing a pvector results in the output we would expect based on our experience slicing Python lists.

In [35]: fruit[:3]
Out[35]: pvector(['banana', 'apple', 'cherry'])

In [36]: fruit[1:]
Out[36]: pvector(['apple', 'cherry'])

The pvector class provides a method called set that allows us to (efficiently) construct a new pvector with a new value assigned to a specific instance.

Recall that the is operator can be used to decide whether or not two variables reference the same value in memory. Below we verify that new_fruit is indeed a new pvector, different than the original fruit.

In [37]: fruit is new_fruit
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-37-93ffc14bbb73> in <module>()
----> 1 fruit is new_fruit

NameError: name 'new_fruit' is not defined

Slicing a pvector is more efficient than slicing a Python list. This is due to the fact that slicing and set are designed to share common data instead of copying all the data. This results in a performance gain when slicing pvectors.

In [38]: L = list(range(10^15))

In [39]: %timeit L[:]
The slowest run took 6.96 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 152 ns per loop

In [40]: V = pvector(range(10^15))

In [41]: %timeit V[:]
The slowest run took 14.11 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 71.4 ns per loop

Other efficient features of the pvector include using append to add to the end of the vector.

In [42]: fruit2 = fruit.append("watermelon")

In [43]: fruit  # The original fruit
Out[43]: pvector(['banana', 'apple', 'cherry'])

In [44]: fruit2
Out[44]: pvector(['banana', 'apple', 'cherry', 'watermelon'])

In [45]: fruit is fruit2  # Not the same vector
Out[45]: False

When writing programs in the functional style, consider using persistent and immutable data structures. We will explore other data structures from this module in later sections on associative data structures and recursion.

Note

This workspace is provided for your convenience. You can use this activecode window to try out anything you like.

    rec-5-24: What does it mean for a data structure to be mutable?
  • (A) Data can be changed without making a new copy of a data structure.
  • (B) Data cannot be changed without making a new copy of a data structure.
    rec-5-25: Are python lists mutable or immutable?
  • (A) Mutable
  • Lists elements can be changed in place.
  • (B) Immutable
  • Lists elements can be changed in place.
    rec-5-26: Are python strings mutable or immutable?
  • (A) Mutable
  • You cannot change the characters in a string.
  • (B) Immutable
  • You cannot change the characters in a string.
    rec-5-27: Are python tuples mutable or immutable?
  • (A) Mutable
  • You cannot change the data in a tuple.
  • (B) Immutable
  • You cannot change the data in a tuple.
    rec-5-28: Are python pvectors from the pyrsistent module mutable or immutable?
  • (A) Mutable
  • You cannot change the data in a pvector.
  • (B) Immutable
  • You cannot change the data in a pvector.
Next Section - 3.6. References to Sequences