Lab 5: Mutable Lists, Dictionaries, and Nonlocal
Due at 11:59pm on 02/24/2017.
Starter Files
Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Submission
By the end of this lab, you should have submitted the lab with
python3 ok --submit
. You may submit more than once before the
deadline; only the final submission will be graded.
- To receive credit for this lab, you must complete Questions 1-5 in lab05.py and submit through OK.
- Questions 6-9 are extra practice. They can also be found in the lab05_extra.py file. It is recommended that you complete these problems on your own time.
List Mutation
Question 1: Map
Write a function that maps a function on the given list. Be sure to mutate the original list.
This function should NOT return anything. This is to emphasize that this function should utilize mutability.
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 solution
for i in range(len(lst)):
lst[i] = fn(lst[i])
# Recursive solution
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))
Use OK to test your code:
python3 ok -q map
Question 2: Over 9000
Define over_nine_thousand
, which takes a list and modifies that list by
adding 9000 to each element.
def over_nine_thousand(original_list):
"""
>>> original_list = [1, 2, 3, 4, 5]
>>> over_nine_thousand(original_list)
>>> original_list
[9001, 9002, 9003, 9004, 9005]
"""
"*** YOUR CODE HERE ***"
index = 0
while index < len(original_list):
original_list[index] += 9000
index += 1
# Alternate solution using map
def over_nine_thousand(original_list):
"""
>>> original_list = [1, 2, 3, 4, 5]
>>> over_nine_thousand(original_list)
>>> original_list
[9001, 9002, 9003, 9004, 9005]
"""
map(lambda x: x + 9000, original_list)
Use OK to test your code:
python3 ok -q over_nine_thousand
Dictionaries
Dictionaries are unordered sets of key-value pairs. Keys can only be immutable types (strings, numbers, tuples), but their corresponding value can be anything! To create a dictionary, use the following syntax:
>>> singers = { 'Adele': 'Hello', 1975: 'Chocolate', 'The Weeknd': ['The Hills', 'Earned It'] }
The curly braces denote the key-value pairs in your dictionary. Each key-value pair is separated by a comma. For each pair, the key appears to the left of the colon and the value appears to the right of the colon. Note keys/values do not all have to be the same type, as you can see we have strings, integers and lists! Each key only appears once in a dictionary. You can retrieve values from your dictionary by "indexing" using the key:
>>> singers[1975]
'Chocolate'
>>> songs = singers['The Weeknd']
>>> songs[0]
'The Hills'
You can add an entry or update an entry for an existing key in the dictionary using the following syntax.
Note they are identical syntax, so be careful! You might end updating (and overwriting an old value) even if you intended to add, and vice versa.
>>> singers['Adele'] = 'Rolling in the Deep'
>>> singers['Adele']
'Rolling in the Deep'
>>> singers['Kanye West'] = 'Real Friends' # New entry!
>>> singers['Kanye West']
'Real Friends'
You can also check for membership of keys!
>>> 'Adele' in singers
True
Finally, here are some useful dictionary functions:
dict.keys()
will return a sequence of keys.>>> list(singers.keys()) # We use list() to turn the sequence into a list [1975, 'The Weeknd', 'Adele']
dict.values()
will return a sequence of values.>>> list(singers.values()) ['Chocolate', ['The Hills', 'Earned It'], 'Hello']
dict.items()
will return a sequences of keys-value pairs.>>> list(singers.items()) [(1975, 'Chocolate'), ('The Weeknd', ['The Hills', 'Earned It']), ('Adele', 'Hello')]
Question 3: WWPD: Dictionaries
What would Python display? Type it in the intepreter if you're stuck!
python3 ok -q dicts -u
>>> pokemon = {'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['pikachu']
______25
>>> len(pokemon)
______3
>>> pokemon['jolteon'] = 135
>>> pokemon['ditto'] = 25
>>> len(pokemon)
______5
>>> sorted(list(pokemon.keys())) # Alphabetically sorted list of pokemon's keys
______['ditto', 'dragonair', 'jolteon', 'mew', 'pikachu']
>>> 'mewtwo' in pokemon
______False
>>> pokemon['ditto'] = pokemon['jolteon']
>>> sorted(list(pokemon.keys())) # Alphabetically sorted list of pokemon's keys
______['ditto', 'dragonair', 'jolteon', 'mew', 'pikachu']
>>> pokemon['ditto']
______135
>>> letters = {'a': 1, 'b': 2, 'c': 3}
>>> 'a' in letters
______True
>>> 2 in letters
______False
>>> food = {'bulgogi': 10, 'falafel': 4, 'ceviche': 7}
>>> food['ultimate'] = food['bulgogi'] + food['ceviche']
>>> food['ultimate']
______17
>>> len(food)
______4
>>> food['ultimate'] += food['falafel']
>>> food['ultimate']
______21
>>> sorted(list(food.keys())) # Alphabetically sorted list of food's keys
______['bulgogi', 'ceviche', 'falafel', 'ultimate']
>>> food['bulgogi'] = food['falafel']
>>> len(food)
______4
>>> 'gogi' in food
______False
Question 4: Replace All
Given a dictionary d
, replace all occurrences of x
as a value (not a key) with y
.
Hint: To loop through the keys of a dictionary use
for key in d:
.
def replace_all(d, x, y):
"""Replace all occurrences of x as a value (not a key) in d with y.
>>> d = {3: '3', 'foo': 2, 'bar': 3, 'garply': 3, 'xyzzy': 99}
>>> replace_all(d, 3, 'poof')
>>> d == {3: '3', 'foo': 2, 'bar': 'poof', 'garply': 'poof', 'xyzzy': 99}
True
"""
"*** YOUR CODE HERE ***"
for key in d:
if d[key] == x:
d[key] = y
Use OK to test your code:
python3 ok -q replace_all
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
Running this function's doctests, we find that it causes the following error:
UnboundLocalError: local variable 'count' referenced before assignment
Why does this happen? When we execute an assignment statement, remember that we are either creating a new binding in our current frame or we are updating an old one in the current frame. For example, the line count = ...
in counter
, is creating the local variable count
inside counter
's frame. This assignment statement tells Python to expect a variable called count inside counter
's frame, so Python will not look in parent frames for this variable. 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! Note we cannot use nonlocal
to modify variables in the global 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
The line nonlocal count
tells Python that count
will not be local to this frame, so it will look for it in parent frames. Now we can update count
without running into problems.
Question 5: Count calls
When testing software, it can be useful to count the number of times
that a function is called. Define a higher-order function
count_calls
that returns two functions:
- A counted version of the input function
f
that counts the number of times it has been called, but otherwise behaves identically to the original function, and - A function of zero arguments that returns the number of times that the counted function has been called.
Your implementation should not include any lists or dictionaries.
Hint: Remember that you can use the
*args
keyword to define an arbitrary number of parameters for a function.
def count_calls(f):
"""A function that returns a version of f that counts calls to f and can
report that count to how_many_calls.
The returned function responds to a special string argument,
'how many calls?'
to return the number of calls.
>>> from operator import add
>>> counted_add, add_count = count_calls(add)
>>> add_count()
0
>>> counted_add(1, 2)
3
>>> add_count()
1
>>> add(3, 4) # Doesn't count
7
>>> add_count()
1
>>> counted_add(5, 6)
11
>>> add_count()
2
"""
"*** YOUR CODE HERE ***"
calls = 0
def counted(*args):
nonlocal calls
calls = calls + 1
return f(*args)
return counted, lambda: calls
Use OK to test your code:
python3 ok -q count_calls
Extra Questions
Questions in this section are also not required for submission. We encourage you to try them out on your own time for extra practice. -- they can be found in the the lab05_extra.py file. It is recommended that you complete these problems on your own time.
Python's 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]
Question 6: Filter
Write a function that filters a list, only keeping elements that satisfy the predicate. Be sure to mutate the original list.
This function should NOT return anything. This is to emphasize that this function should utilize mutability.
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 ***"
i = len(lst) - 1
while i >= 0:
if not pred(lst[i]):
lst.pop(i)
i -= 1
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]
"""
if lst:
temp = lst.pop(0)
filter(pred, lst)
if pred(temp):
lst.insert(0, temp)
Use OK to test your code:
python3 ok -q filter
Question 7: Reverse
Write a function that reverses the given list. Be sure to mutate the original list.
This function should NOT return anything. This is to emphasize that this function should utilize mutability.
def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
>>> odd_list = [42, 72, -8]
>>> reverse(odd_list)
>>> odd_list
[-8, 72, 42]
"""
"*** YOUR CODE HERE ***"
# iterative solution
midpoint = len(lst) // 2
last = len(lst) - 1
for i in range(midpoint):
lst[i], lst[last - i] = lst[last - i], lst[i]
# Recursive solution
def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
>>> odd_list = [42, 72, -8]
>>> reverse(odd_list)
>>> odd_list
[-8, 72, 42]
"""
if len(lst) > 1:
temp = lst.pop()
reverse(lst)
lst.insert(0, temp)
# Alternative recursive solution
def reverse(lst):
"""Reverses lst using mutation.
>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
>>> odd_list = [42, 72, -8]
>>> reverse(odd_list)
>>> odd_list
[-8, 72, 42]
"""
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)
Use OK to test your code:
python3 ok -q reverse
Question 8: Counter
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() # .split() returns a list of the words in the string. Try printing it!
"*** 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
Use OK to test your code:
python3 ok -q counter
Question 9: Next Fibonacci
Write a function make_fib
that returns a function that returns the
next Fibonacci number each time it is called. (The Fibonacci sequence begins with 0
and then 1, after which each element is the sum of the preceding two.)
Use a nonlocal
statement!
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
>>> fib2 = make_fib()
>>> fib() + sum([fib2() for _ in range(5)])
12
"""
"*** YOUR CODE HERE ***"
cur, next = 0, 1
def fib():
nonlocal cur, next
result = cur
cur, next = next, cur + next
return result
return fib
Use OK to test your code:
python3 ok -q make_fib