Lab 7: Mutability

Table of Contents

Deadline

By the end of this lab, you should have submitted the lab07 assignment using the command submit lab07.

This lab is due by 11:59pm on 7/18/2014.

Here is a lab07.py starter file for this lab.

Mutability

Question 1

What does Python print? Think about these before typing it into an interpreter!

>>> lst = [1, 2, 3, 4, 5, 6]
>>> lst[4] = 1
>>> lst
______
>>> lst[2:4] = [9, 8]
>>> lst
______
>>> lst[3] = ['hi', 'bye']
>>> lst
______
>>> lst[3:] = ['andrew', 'rohin']
>>> lst
______
>>> lst[1:3] = [2, 3, 4, 5, 6, 7, 8]
>>> lst
______
>>> lst == lst[:]
______
>>> lst is lst[:]
______
>>> a = lst[:]
>>> a[0] = 'oogly'
>>> lst
______
>>> lst = [1, 2, 3, 4]
>>> b = ['foo', 'bar']
>>> lst[0] = b
>>> lst
______
>>> b[1] = 'ply'
>>> lst
______
>>> b = ['farply', 'garply']
>>> lst
______
>>> lst[0] = lst
>>> lst
______
>>> lst[0][0][0][0][0]
______

List Methods

Python has a list class that contains many useful methods. Using the builtin dir() function will show you all of them, like so:

dir(list)

Some of the most common methods include append(), extend(), and pop().

>>> l = [3, 5, 6]
>>> l.append(10) # adds an element to the end
>>> l
[3, 5, 6, 10]
>>> l.extend([-1, -6]) # concatenates another list to the end
>>> l
[3, 5, 6, 10, -1, -6]
>>> l.pop() # removes and returns the last element
-6
>>> l
[3, 5, 6, 10, -1]
>>> l.pop(2) # removes and returns the element at the index given
6
>>> l
[3, 5, 10, -1]
>>> l.insert(2, 42)
>>>l
[3, 5, 42, 10, -1]

Try to solve the following list problems with mutation. This means that each function should mutate the original list. In other words:

>>> original_list = [5, -1, 29, 0]
>>> function(original_list) # doesn't return anything
>>> original_list
# mutated list here

Prioritize solving these problems with iteration, but for extra practice, also solve them using recursion. Remember: these functions should NOT return anything. This is to emphasize that these functions should utilize mutability.

Question 2

Write a function that reverses the given list.

def reverse(lst):
    """Reverses lst using mutation.
    >>> original_list = [5, -1, 29, 0]
    >>> reverse(original_list)
    >>> original_list
    [0, 29, -1, 5]
    """
    "*** YOUR CODE HERE ***"
# Iterative
def reverse(lst):
    """Reverses lst using mutation.
    >>> original_list = [5, -1, 29, 0]
    >>> reverse(original_list)
    >>> original_list
    [0, 29, -1, 5]
    """
    "*** YOUR CODE HERE ***"
    midpoint = len(lst) // 2
    last = len(lst) - 1
    for i in range(midpoint):
        lst[i], lst[last - i] = lst[last - i], lst[i]

# Recursive1
def reverse(lst):
    """Reverses lst using mutation.
    >>> original_list = [5, -1, 29, 0]
    >>> reverse(original_list)
    >>> original_list
    [0, 29, -1, 5]
    >>>original_list2 = [6, 8, 0, -1, -3]
    >>>reverse(original_list2)
    >>>original_list2
    [-3, -1, 0, 8, 6]
    """
    if len(lst) > 1:
        temp = lst.pop()
        reverse(lst)
        lst.insert(0, temp)

# Recursive2
def reverse(lst):
    """Reverses lst using mutation.
    >>> original_list = [5, -1, 29, 0]
    >>> reverse(original_list)
    >>> original_list
    [0, 29, -1, 5]
    """
    midpoint = len(lst) // 2
    last = len(lst) - 1
    def helper(i):
        if i == midpoint:
            return
        lst[i], lst[last - i] = lst[last - i], lst[i]
        helper(i + 1)
    helper(0)

Question 3

Write a function that maps a function on the given list.

def map(fn, lst):
    """Maps fn onto lst using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> map(lambda x: x * x, original_list)
    >>> original_list
    [25, 1, 4, 0]
    """
    "*** YOUR CODE HERE ***"
# Iterative
def map(fn, lst):
    """Maps fn onto lst using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> map(lambda x: x * x, original_list)
    >>> original_list
    [25, 1, 4, 0]
    """
    "*** YOUR CODE HERE ***"
    for i in range(len(lst)):
        lst[i] = fn(lst[i])

# Recursive
def map(fn, lst):
    """Maps fn onto lst using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> map(lambda x: x * x, original_list)
    >>> original_list
    [25, 1, 4, 0]
    """
    if lst: # True when lst != []
        temp = lst.pop(0)
        map(fn, lst)
        lst.insert(0, fn(temp))

Question 4: (Optional, for extra practice)

Write a function that filters a list, only keeping elements that satisfy the predicate.

def filter(pred, lst):
    """Filters lst with pred using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    >>> original_list2 = ['cool', 'nice', 'rad']
    >>> filter(lambda x: len(x) == 4, original_list2)
    >>> original_list2
    ['cool', 'nice']
    """
    "*** YOUR CODE HERE ***"
# Iterative
def filter(pred, lst):
    """Filters lst with pred using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    >>> original_list2 = ['cool', 'nice', 'rad']
    >>> filter(lambda x: len(x) == 4, original_list2)
    >>> original_list2
    ['cool', 'nice']
    """
    "*** YOUR CODE HERE ***"
    i = len(lst) - 1
    while i >= 0:
        if not pred(lst[i]):
            lst.pop(i)
        i -= 1

# Recursive
def filter(pred, lst):
    """Filters lst with pred using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    """
    "*** YOUR CODE HERE ***"
    if lst: 
        temp = lst.pop(0)
        filter(pred, lst)
        if pred(temp):
            lst.insert(0, temp)

Dictionaries

First, let's talk about dictionaries. Dictionaries are a simple, unordered set of key-value pairs. To create a dictionary, use the following syntax:

>>> webster = {'Shawn': 'pineapple', 'Kim': 'blueberry'}

The curly braces denote the key-value pairs in your dictionary. Each key-value pair is separated by a coma, and for each pair the key appears to the left of the colon and the value appears to the right of the colon. You can retrieve values from your dictionary by 'indexing' using the key:

>>> webster['Shawn']
'pineapple'
>>> webster['Kim']
'blueberry'

You can modify an entry for an existing key in the dictionary using the following syntax. Adding a new key follows identical syntax!

>>> webster['Shawn'] = 'strawberry'
>>> webster['Shawn']
'strawberry'
>>> webster['Carlton'] = 'donut' # new entry!
>>> webster['Carlton']
'donut

You can also check for membership of keys!

>>> 'Shawn' in webster
True

Question 5

Implement the function counter which takes in a string of words, and returns a dictionary where each key is a word in the message, and each value is the number of times that word is present in the original string.

def counter(message):
    """ Returns a dictionary of each word in message mapped 
    to the number of times it appears in the input string.
    >>> x = counter("to be or not to be")
    >>> x["to"]
    2
    >>> x["be"]
    2
    >>> x["not"]
    1
    >>> y = counter("run forrest run")
    >>> y["run"]
    2
    >>> y["forrest"]
    1
    """
    word_list = message.split()
    "*** YOUR CODE HERE ***"
        result_dict = {}
        for word in word_list:
            if word in result_dict:
                result_dict[word] += 1
            else:
                result_dict[word] = 1
        return result_dict

Adding in Nonlocal

Question 6

Now we will be making our own glookup, which keeps track of one's current grade out of the assignments completed so far (you can use this to keep track of your points throughout the rest of the semester!)

glookup takes in the following dictionary of assignment names mapped to their total point values:

cs61a = {
        "Homework": 2,
        "Lab": 1,
        "Exam": 50,
        "Final": 80,
        "PJ1": 20,
        "PJ2": 15,
        "PJ3": 25,
        "PJ4": 30,
        "Extra credit": 0
         }

glookup then returns a function which takes in an assignment keyword and the points earned on that particular assignment. It returns the current grade percentage out of what assignments have been entered so far.

Make sure you read the doctests and understand them fully before you start writing code.

def make_glookup(class_assignments):
    """ Returns a function which calculates and returns 
    the current grade out of what assignments have 
    been entered so far.

    >>> student1 = make_glookup(cs61a) #cs61a is the above dictionary
    >>> student1("Homework", 1.5)
    0.75
    >>> student1("Lab", 1)
    0.8333333333333334
    >>> student("PJ1", 18)
    0.8913043478260869
    """
def make_glookup(class_assignments):
    current_points = 0
    current_total = 0
    def glookup(key_word, points):
        nonlocal current_points, current_total
        current_total += class_assignments[key_word]
        current_points += points
        return current_points / current_total
    return glookup

Question 7: (Optional, for extra practice)

Now that we've learned about lists and the nonlocal keyword, lets try seeing what they look like in environment diagrams!

Try drawing environment diagrams for the following examples and predicting what Python will output:

>>> wolf = [1, 2, 3]
>>> def dog(lst):
...     def animal(ele):
...         ele = [ele] + lst
...         return [ele] + [beast[0]]
...     beast = [2, 3, animal]
...     return beast
>>> x = dog(wolf)[2](4)
>>> x
______
>>> x = 18
>>> def it(i):
...     i = x
...     def shifty(getting):
...         nonlocal i
...         i = getting + x
...         def shiftier(y):
...             nonlocal getting
...             getting = y*i
...             return i
...         return shiftier
...     return shifty
>>> shift = it('is')(x)(4)
>>> shift
______
>>> def piper(chapman):
...     chapman.append('state')
...     def alex(vause):
...         nonlocal chapman
...         chapman += [vause[1]]
...         return chapman
...     return alex
>>> orange = piper(['litchfield', 'new york'])(['federal', 'prison'])
>>> orange
______