CS 61A Lab 5

Mutable Data and Sequence Processing

We've provided a starter file with skeleton code for the exercises in the lab. You can get it at the following link:

Nonlocal

Consider the following function:

def make_counter():
    """Makes a counter function.

    >>> counter = make_counter()
    >>> counter()
    1
    >>> counter()
    2
    """
    count = 0
    def counter():
        count = count + 1
        return count
    return counter

Try running this function's doctests. You'll find that it causes the following error:

UnboundLocalError: local variable 'count' referenced before assignment

Why does this happen? Normally, when we create variables (like count = ... in counter), we create the variable in the local frame. Thus count is marked as a local variable in the counter function. However, notice that we tried to compute count + 1 before the local variable was created! That's why we get the UnboundLocalError.

To avoid this problem, we introduce the nonlocal keyword. It allows us to update a variable in a parent frame. Consider this improved example:

 def make_counter():
    """Makes a counter function.

    >>> counter = make_counter()
    >>> counter()
    1
    >>> counter()
    2
    """
    count = 0
    def counter():
        nonlocal count
        count = count + 1
        return count
    return counter

Notice the nonlocal count. This declares the count variable as a nonlocal variable, so now we can update count.

Problem 1: Predict what Python will display when the following lines are typed into the interpreter:

>>> def make_funny_adder(n):
...     def adder(x):
...         if x == 'new':
...             nonlocal n
...             n = n + 1
...         else:
...             return x + n
...     return adder
>>> h = make_funny_adder(3)
>>> h(5)
______
>>> j = make_funny_adder(7)
>>> j(5)
______
>>> h('new')
>>> h(5)
______

Problem 2: Write a function make_fib that returns a function that reurns the next Fibonacci number each time it is called.

def make_fib():
    """Returns a function that returns the next Fibonacci number
    every time it is called.

    >>> fib = make_fib()
    >>> fib()
    0
    >>> fib()
    1
    >>> fib()
    1
    >>> fib()
    2
    >>> fib()
    3
    """
    "*** YOUR CODE HERE ***"

Problems 3: Recall make_test_dice from the Hog project. make_test_dice takes in a sequence of numbers and returns a zero-argument function. This zero-argument function will cycle through the list, returning one element from the list every time. Implement make_test_dice.

def make_test_dice(seq):
    """Makes deterministic dice.

    >>> dice = make_test_dice([2, 6, 1])
    >>> dice()
    2
    >>> dice()
    6
    >>> dice()
    1
    >>> dice()
    2
    >>> other = make_test_dice([1])
    >>> other()
    1
    >>> dice()
    6
    """
    "*** YOUR CODE HERE ***"

Problem 4: Recall the make_withdraw function from lecture:

def make_withdraw(balance):
    """Return a withdraw function with a starting balance."""
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

Write a new function make_bank, which should also return another function. This new function should be able to withdraw and deposit money. See the doctests for behavior:

def make_bank(balance):
    """Returns a bank function with a starting balance. Supports
    withdrawals and depositis.

    >>> bank = make_bank(100)
    >>> bank('withdraw', 40)    # 100 - 4
    60
    >>> bank('deposit', 20)     # 60 + 20
    80
    >>> bank('withdraw', 90)    # 80 - 90; not enough money
    'Insufficient funds'
    """
    def bank(message, amount):
        "*** YOUR CODE HERE ***"
    return bank

Sequence Processing

The sequence abstraction is a fundamental concept in Python and many other programming languages. In Python, a sequence is defined to be any object that

Some examples of sequences in Python include tuples, lists, and strings:

>>> x = (1, 2, 3)
>>> len(x)
3
>>> x[0]
1
>>> s = 'hello world!'
>>> len(s)
12
>>> s[0]
'h'

We can also iterate over sequences with for loops:

>>> x = (1, 2, 3)
>>> for item in x:
...     print(item)
1
2
3
>>> s = 'to eat'
>>> for letter in s:
...     print(letter)
t
o

e
a
t

Some Python sequences also support other features, like slicing and membership testing:

>>> L = [1, 2, 3, 4]
>>> L[1:3]
[2, 3]
>>> s = 'cs 61a'
>>> '61' in s
True

Problem 5: Implement max_char, a function that takes a sentence (as a string) and returns the character that appears the most number of times in the sentence. If there is a tie, return the character that appears first.

Hint: strings have a count method that can count the number of occurrences of a given substring. For example, 'hi there'.count('h') will evaluate to 2.

def max_char(sentence):
    """Returns the character that appears the most number of times
    in sentence (a string).

    >>> max_char('see spot run')
    's'
    >>> max_char('mississippi')
    'i'
    """
    "*** YOUR CODE HERE ***"

Problem 6: Implement max_word, a function that takes a sentence (as a string) and returns the word (in lower case) that appears the most number of times in the sentence. If there is a tie, return the character that appears first. You can assume there's no punctuation.

Your function should ignore capitalization. For example, 'text' is the same English word as 'Text', but in Python, 'text' != 'Text'. Luckily, string objects have a lower() method that might help. For example, 'TExt'.lower() == 'text'.

In addition, strings also have a method called split(). This will split a given string on whitespace. For example, 'hello world'.split() == ['hello', 'world'].

def max_word(sentence):
    """Returns the word that occurs the most number of times in
    sentence (a string).

    >>> max_word('To be or not to be')
    'to'
    """

Map, filter, and reduce

Python has many powerful tools for sequence processing. Three of the most common are map, filter, and reduce:

Note that map and filter return map objects and filter objects, respectively. You can cast the results as lists. Some examples:

>>> map(lambda x: x*x, [1, 2, 3])
<map object at ...>
>>> list(map(lambda x: x*x, [1, 2, 3]))
[1, 4, 9]

>>> filter(lambda x: x % 2 == 0, (1, 2, 3, 4))
<filter object at ...>
>>> list(filter(lambda x: x % 2 == 0, (1, 2, 3, 4)))
[2, 4]

>>> from functools import reduce
>>> reduce(lambda x, y: x + y, [1, 2, 3, 4])  # 1 + 2 + 3 + 4
10

Problem 7: as an exercise, implement three functions map, filter, and reduce to behave like their built-in counterparts. For map and filter, you can return the results as Python lists.

def map(fn, seq):
    """Applies fn onto each element in seq and returns a list.

    >>> map(lambda x: x*x, [1, 2, 3])
    [1, 4, 9]
    """
    "*** YOUR CODE HERE ***"

def filter(pred, seq):
    """Keeps elements in seq only if they satisfy pred.

    >>> filter(lambda x: x % 2 == 0, [1, 2, 3, 4])
    [2, 4]
    """
    "*** YOUR CODE HERE ***"

def reduce(combiner, seq):
    """Combines elements in seq using combiner.

    >>> reduce(lambda x, y: x + y, [1, 2, 3, 4])
    10
    >>> reduce(lambda x, y: x * y, (1, 2, 3))
    6
    >>> reduce(lambda x, y: x * y, [4])
    4
    """
    "*** YOUR CODE HERE ***"

Problem 8: Fill in the blanks for the following lines so that each expression evaluates to the expected output:

>>> list(map(_______, [1, 3, -1, -4, 2]))
[1, 1, -1, -1, 1]
>>> list(filter(______, [1, 7, 14, 21, 28, 35, 42]))
[1, 14, 28, 42]
>>> reduce(_______, 'hello')
'olleh'
>>> reduce(______, map(______, 'nnnnn')) + ' batman!'
'nanananana batman!'

Extra Questions

Problem 9: Implement a function deep_len that takes in a (possibly) nested tuple and calculates its length. For example, the expression deep_len((1, (2, 3), 4)) would evaluate to 4, as opposed to 3 (as the built-in len would report). The tuples can have an arbitrary amount of nesting.

Hint: the built-in type function can tell you the type of an object. For example,

>>> x = (1, 2, 3)
>>> type(x) == tuple
True

You can choose to use iteration or not, but either way, you will most likely use some sort of recursion.

def deep_len(tup):
    """Calculates the length of a possibly nested tuple.

    >>> deep_len((1, 2, 3, 4))  # normal tuple
    4
    >>> deep_len((1, (2, 3), 4))
    4
    >>> deep_len((1, (2, (3, (4,)))))
    4
    >>> deep_len((1, (), 2))  # empty  # nested tuples don't count
    2
    """
    "*** YOUR CODE HERE ***"

Problem 10: Implement a function merge, which takes two sorted tuples and returns a tuple that contains all elements in both tuples (including duplicates) in sorted order. The sequences do not have to have the same length.

Hint: Try doing this recursively.

def merge(seq1, seq2):
    """Merges all elements (including duplicates) of seq1 and seq2
    in sorted order.

    >>> merge((1, 3, 5), (2, 4))
    (1, 2, 3, 4, 5)
    >>> merge((), (1, 2, 3))
    (1, 2, 3)
    """
    "*** YOUR CODE HERE ***"

Problem 11: Mergesort is a type of sorting algorithm. It follows a naturally recursive procedure:

Using your merge function from the previous question, implement mergesort.

Challenge: Implement mergesort iteratively, without using recursion.

def mergesort(seq):
    """Mergesort algorithm.

    >>> mergesort((4, 2, 5, 2, 1))
    (1, 2, 2, 4, 5)
    >>> mergesort(())     # sorting an empty list
    ()
    >>> mergesort((1,))   # sorting a one-element list
    (1,)
    """
    "*** YOUR CODE HERE***"