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