# 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):
...         if x == 'new':
...             nonlocal n
...             n = n + 1
...         else:
...             return x + n
>>> h(5)
______
>>> 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
"""
``````

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
"""
``````

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):
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

• Has a finite length
• Supports element selection (through zero-based indexing)

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'
"""
``````

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`:

• `map(fn, seq)`: applies a function `fn` onto every element in the given sequence `seq`.
• `filter(pred, seq)`: keeps elements in the sequence `seq` only if those elements satisfy the predicate function `pred` (that is, for an element `x`, keep it only if `pred(x)` is True).
• `reduce(combiner, seq)`: combines all elements in the sequence `seq` with the `combiner` function (which must take two arguments). Note: `reduce` must be imported from the module `functools`

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]
"""

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]
"""

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
"""
``````

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
"""
``````

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)
"""
``````

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

• Break the input tuple into equally-sized halves
• Recursively sort both halves
• Merge the sorted halves.

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,)
"""