Lab 4: Mutation

Due at 11:59pm on 10/23/2016.

Starter Files

Download lab04.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab using ok. You may submit more than once before the deadline; only the final submission will be graded.

To receive credit for this lab, you must complete all questions and submit through OK.

What is mutability?

A mutable data structure is any data structure that can be changed after it is created. You've already dealt with two mutable data structures: lists and dictionaries.

>>> x = [1, 2, 3]
>>> x[0] = 4
>>> x
[4, 2, 3]   # x changed!
>>> d = {'name': Garrett, 'age': 21, 'major': 'EECS'}
>>> d['major'] = 'MCB'
>>> d
{'name': Garrett, 'age': 21, 'major': 'MCB'}  # Garrett is an MCB major now!

Unlike lists or dictionaries, tuples are immutable data structures. This means that once they are created, they can't be changed. For example, try this:

>>> x = (1, 2, 3)
>>> x[0] = 4

This will cause TypeError complaining that tuples don't "support item assignment." In other words, you can't change the elements in a tuple because tuples are immutable. Once a tuple is created, it can't be changed!

Tricky List Mutation

Question 1: The Mutation Mystery

You just got a new job as the official code detective of UC Berkeley. You just got your first assignment on the job! There have been 3 reported cases of unusual list behavior from students who are writing python code for CS88. You're no python expert yet, but you've been studying up on the details of how python works. You're ready to investigate this mystery!


Case #1

The first case was brought to you by Alice Listmaker. Alice created two identical lists, x and y. She then wanted to modify only y. However, she was surprised to see that x had been modified too! Use the command below to see what happened.

 python ok -q case1 -u --local

Hmm... what could have gone wrong here? Here are some clues that will help you figure this out:

  1. This environment diagram
  2. Slicing, such as x[:], creates a new list.
  3. The list function, list(x), creates a new list.

You think you have found a fix using slicing and the list function. Use the command below to confirm that you have solved the mystery!

 python ok -q case1-solved -u --local

Case #2

The second report of unusual list behavior came from Alice's cousin, Bob Listmaker. Unlike Alice, Bob knew about slicing and the list function. However, he was still a victim of mutation. Let's take a look at what happened to Bob's lists using the command below.

 python ok -q case2 -u --local

Here are some clues as to what caused this error:

  1. Slicing and the list function do create new lists, but do not deep copy the values.
  2. This environment diagram
  3. This article on shallow vs. deep copy

You have figured out that Bob needs to perform a deep copy on his lists. You decide to write a deep_copy function for Bob to use. Fill in the body of the function in lab06.py. Do NOT use the copy module shown in the article, you need to write your own function! Test your code using the following command.

 python ok -q deep_copy --local

Case #3

After solving those first two cases, you're ready to tackle the final challenge. This case was brought to you by Eve (she doesn't have a list-related last name, sorry). Eve knew that she was not properly deep copying her lists. However, she could not figure out why this only caused problems some of the time. Let's investigate further.

 python ok -q case3 -u --local

Your final clues:

  1. This environment diagram
  2. Lists contain pointers to other lists.
  3. There are no pointers to strings or numbers, the values are stored directly.

Once you have solved this last case, write out an explanation for the unusual behavior in Eve'e code in case3_explanation in lab06.py.

Congratulations, you have solved the mutation mystery!


Additional unusual list behavior

  1. Adding elements to a list using + creates a new list.
  2. Adding elements to a list using += does not create a new list.
  3. Adding elements to a list using .append() does not create a new list.

Take a look at this environment diagram to see an example of this. Pay close attention to the difference between using + and += in the example with y and z.

Counting Words

You'll be implementing a word count function in three different ways (using three different combinations of data structures). Keep in mind which data structures are mutable and which are not! Your code will be run on the words in shakespeare.txt as a test.

Question 2: Word Count (Dictionary)

First we'll implement the word count function with a dictionary. word_count_dictionary should return a dictionary that maps words to counts (i.e. entries in the dictionary should look like {word: count}).

def word_count_dictionary(word_list):
    """ Returns a dictionary of each word in message mapped
    to the number of times it appears in the input list of words.

    >>> d = word_count_dictionary(shakespeare_list)
    >>> d["the"]
    51
    >>> d["but"]
    12
    >>> d["thy"]
    5
    """

    "*** YOUR CODE HERE ***"

    d = {}
    for word in word_list:
        if word in d:
            d[word] += 1
        else:
            d[word] = 1
    return d

Use OK to test your code:

python ok -q word_count_dictionary --local

Question 3: Word Count (List of Lists)

Next try implementing the word count function with a list of lists. word_count_list should return a list of lists that looks something like [[word1, count1], [word2, count2], ...].

def word_count_list(word_list):
    """ Returns a list of lists where each inner list is equal to
    [word, count].

    >>> lists = word_count_list(shakespeare_list)
    >>> lists[0]
    ['the', 51]
    >>> lists[183]
    ['but', 12]
    >>> lists[78]
    ['thy', 5]
    """

    "*** YOUR CODE HERE ***"

    lists = []
    for word in word_list:
        for lst in lists:
            if lst[0] == word:
                lst[1] += 1
                break
        else:
            lists += [[word, 1]]
    return lists

Use OK to test your code:

python ok -q word_count_list --local

Question 4: Word Count (List of Tuples)

Finally, let's try implementing the word count function with a list of tuples. word_count_tuple should return a list of tuples of the form [(word1, count1), (word2, count2), ...]. Keep in mind that, unlike lists, tuples are immutable!

def word_count_tuple(word_list):
    """ Returns a list of tuples where each tuple is equal to
    (word, count).

    >>> tuples = word_count_tuple(shakespeare_list)
    >>> tuples[0]
    ('the', 51)
    >>> tuples[183]
    ('but', 12)
    >>> tuples[78]
    ('thy', 5)
    """

    "*** YOUR CODE HERE ***"

    tuples = []
    for word in word_list:
        for i in range(len(tuples)):
            if tuples[i][0] == word:
                tuples[i] = (word, tuples[i][1] + 1)
                break
        else:
            tuples += [(word, 1)]
    return tuples

Use OK to test your code:

python ok -q word_count_tuple --local

Question 5: get_word_count

You've now implemented word count in three different ways! However, there's a small issue. Notice that when we tested your code for word_count_list and word_count_tuple we access values by index. This is dangerous! It assumes the order of words in the list is always the same (think about why this isn't true). To fix this problem, implement get_word_count, which will allow us to get the count of a word without indexing (similar to how we retrieve values from a dictionary).

def get_word_count(lists, word):
    """ Given a list of tuples or lists (such as those returned by
    word_count_tuple and word_count_list), returns the count of a word.

    >>> lists = word_count_list(shakespeare_list)
    >>> get_word_count(lists, "the")
    51
    >>> tuples = word_count_tuple(shakespeare_list)
    >>> get_word_count(tuples, "the")
    51
    """

    "*** YOUR CODE HERE ***"

    for elem in lists:
        if elem[0] == word:
            return elem[1]

Use OK to test your code:

python ok -q get_word_count --local

Question 6: Mutant function

You have seen how careful mutation of a data structure within an abstraction can be an essential part of constructing an object oriented abstraction. You probably also discovered that the control structure was more complicated that when working in a purely functional style. Because modifications are made to objects, there is a need to break out of loops and such when the appropriate actions are taken. At times the judicious use of mutating functions can provide a clean solution. We have given you a start at this with a version of word_count_list that uses an internal mutating add_word function to make the necessary update to the list of [word, count] entries. The outer loop is now very simple. Your task, CS88 detective, is to write the rest of the add_word function. You will need to use nonlocal. You will see that you do not need the complicated for ... else sorts of concepts that you probably used in word_count_list. The add_word function can simply return when it has completed its task. (Calling add_word a function is a bit of a misnomer, but a common one. It isn't a function in the mathematical sense because it has no result value and its behavior depends on its history (i.e., lists), not just its input (word). It is defined with a def and from a programming point of view it is a function''.

import string

def word_count_fun(word_list):
    """ Returns a list of lists where each inner list is equal to
    [word, count].

    >>> word_count_fun(["one", "two", "two"])
    [['one', 1], ['two', 2]]
    """
    lists = []
    def add_word(word):

        "*** YOUR CODE HERE ***"

        nonlocal lists
        for lst in lists:
            if lst[0] == word:
                lst[1] += 1
                return
        lists += [[word, 1]]
        return 
    for word in word_list:
        add_word(word)
    return lists

You may wonder why we use the loop to apply add_word to every word in word_list. Why didn't we just map(add_word, word_list)? You might give this a try. It comes back to add_word not being purely functional and not having a result. The map tries to compute results lazily and so you have to push it to get the work done.

Use OK to test your code:

python ok -q word_count_fun --local