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

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

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

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]
"""
"*** 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!'
```

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

- 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,)
"""
"*** YOUR CODE HERE***"
```