Lab 2: Higher-Order Functions and Lambdas
Due at 11:59pm on 09/10/2015.
Starter Files
Download lab02.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.
- Questions 1 through 3 (What Would Python Print?) are designed to help introduce concepts and test your understanding.
- For the purpose of tracking participation, please complete at least questions 4, 5, and 6 in lab02.py. Submit using OK.
- Questions 8 through 11 are completely optional practice. Starter code for questions 10 and 11 is in lab02_extra.py. It is recommended that you complete these problems on your own time.
Note: For all WWPP questions, input Function
if you believe the answer is
<function...>
, Error
if it errors, and Nothing
if nothing happens.
Lambdas
Lambda
expressions are one-line functions that specify two things:
the parameters and the return value.
lambda <parameters>: <return value>
While both lambda
and def
statements are related to functions, there are some differences.
lambda | def | |
---|---|---|
Type | lambda is an expression |
def is a statement |
Description | Evaluating a lambda expression does not create or modify any variables.
Lambda expressions just create new function objects. |
Executing a def statement will create a new function object and bind it to a variable in the current environment. |
Example |
|
|
A lambda
expression by itself is not very interesting. As with any objects such as numbers, booleans, strings, we usually:
- assign lambda to variables (
foo = lambda x: x
) - pass them in to other functions (
bar(lambda x: x)
)
Question 1: WWPP: Lambda the Free
Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok -q lambda -u
Hint: Remember for all WWPP questions, input
Function
if you believe the answer is<function...>
,Error
if it errors, andNothing
if nothing happens.
>>> lambda x: x # Can we access this function?
______<function <lambda> at ...>
>>> a = lambda x: x
>>> a(5) # x is the parameter for the lambda function
______5
>>> b = lambda: 3
>>> b()
______3
>>> c = lambda x: lambda: print('123')
>>> c(88)
______<function <lambda> at ...>
>>> c(88)()
______123
>>> d = lambda f: f(4) # They can have functions as arguments as well.
>>> def square(x):
... return x * x
>>> d(square)
______16
>>> t = lambda f: lambda x: f(f(f(x)))
>>> s = lambda x: x + 1
>>> t(s)(0)
______3
>>> bar = lambda y: lambda x: pow(x, y)
>>> bar()(15)
______TypeError: <lambda>() missing 1 required positional argument: 'y'
>>> foo = lambda: 32
>>> foobar = lambda x, y: x // y
>>> a = lambda x: foobar(foo(), bar(4)(x))
>>> a(2)
______2
>>> b = lambda x, y: print('summer') # When is the body of this function run?
______# Nothing gets printed by the interpreter
>>> c = b(4, 'dog')
______summer
>>> print(c)
______None
Question 2: Lambda the Environment Diagram
Try drawing an environment diagram for the following code and predict what Python will output.
You can check your work with the Online Python Tutor, but try drawing it yourself first!
>>> a = lambda x: x * 2 + 1
>>> def b(b, x):
... return b(x + a(x))
>>> x = 3
>>> b(a, x)
______21
Higher Order Functions
A higher order function is a function that manipulates other functions by taking in functions as arguments, returning a function, or both. We will be exploring many applications of higher order functions.
Question 3: WWPP: Higher Order Functions
Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok -q hof -u
Hint: Remember for all WWPP questions, input
Function
if you believe the answer is<function...>
,Error
if it errors, andNothing
if nothing happens.
>>> def first(x):
... x += 8
... def second(y):
... print('second')
... return x + y
... print('first')
... return second
>>> f = first(15)
______first
>>> f
______<function ...>
>>> f(16)
______second
39
>>> def even(f):
... def odd(x):
... if x < 0:
... return f(-x)
... return f(x)
... return odd
>>> stevphen = lambda x: x
>>> stewart = even(stevphen)
>>> stewart
______<function ...>
>>> stewart(61)
______61
>>> stewart(-4)
______4
Question 4: This Question is so Derivative
Define a function make_derivative
that returns a function: the derivative of a
function f
. Assuming that f
is a single-variable mathematical function, its
derivative will also be a single-variable function. When called with a number
a
, the derivative will estimate the slope of f
at point (a, f(a))
.
Recall that the formula for finding the derivative of f
at point a
is:
where h
approaches 0. We will approximate the derivative by choosing a very
small value for h
. The closer h
is to 0, the better the estimate of the
derivative will be.
def make_derivative(f, h=1e-5):
"""Returns a function that approximates the derivative of f.
Recall that f'(a) = (f(a + h) - f(a)) / h as h approaches 0. We will
approximate the derivative by choosing a very small value for h.
>>> square = lambda x: x*x
>>> derivative = make_derivative(square)
>>> result = derivative(3)
>>> round(result, 3) # approximately 2*3
6.0
"""
"*** YOUR CODE HERE ***"
def derivative(x):
return (f(x + h) - f(x)) / h
return derivative
Use OK to test your code:
python3 ok -q make_derivative
Encryption and Decryption
Question 5: String Transformer
Using a lambda
expression, complete the following function. Your function
should only contain a return statement.
from operator import add, sub
def caesar_generator(num, op):
"""Returns a one-argument Caesar cipher function. The function should "rotate" a
letter by an integer amount 'num' using an operation 'op' (either add or
sub).
You may use the provided `letter_to_num` and `num_to_letter` functions,
which will map all lowercase letters a-z to 0-25 and all uppercase letters
A-Z to 26-51.
>>> letter_to_num('a')
0
>>> letter_to_num('c')
2
>>> num_to_letter(3)
'd'
>>> caesar2 = caesar_generator(2, add)
>>> caesar2('a')
'c'
>>> brutus3 = caesar_generator(3, sub)
>>> brutus3('d')
'a'
"""
"*** YOUR CODE HERE ***"
return ______
return lambda char: num_to_letter(op(letter_to_num(char), num))
Use OK to test your code:
python3 ok -q caesar_generator
Question 6: Encryption and Decryption Utilities
Complete the following two higher-order functions. Both functions will apply a
set of functions f1
, f2
, and f3
to a string, except the first encrypts
data and the second decrypts.
The provided
looper
function returns a function that will apply functionf
to a series of letters. For example, if f shifts a letter four times to the right, looper(f) will return a function that shifts all letters in a word, four times to the right. We have provided the code you need that useslooper
.
def make_encrypter(f1, f2, f3):
"""Generates an "encrypter" that applies a specific set of encryption
functions on the message
>>> caesar3 = caesar_generator(3, add)
>>> caesar2 = caesar_generator(2, add)
>>> encrypter = make_encrypter(caesar2, mirror_letter, caesar3)
>>> encrypter('abcd') # caesar2(mirror_letter(caesar3('a'))) -> 'y'
'yxwv'
"""
f1, f2, f3 = looper(f1), looper(f2), looper(f3)
"*** YOUR CODE HERE ***"
def encrypter(msg):
return f1(f2(f3(msg)))
return encrypter
def make_decrypter(f1, f2, f3):
"""Generates a "decrypter" function.
>>> brutus3 = caesar_generator(3, sub)
>>> brutus2 = caesar_generator(2, sub)
>>> decrypter = make_decrypter(brutus2, mirror_letter, brutus3)
>>> decrypter('yxwv') # brutus3(mirror_letter(brutus2('y'))) = 'a'
'abcd'
"""
f1, f2, f3 = looper(f1), looper(f2), looper(f3)
"*** YOUR CODE HERE ***"
def decrypter(msg):
return f3(f2(f1(msg)))
return decrypter
Use OK to test your code:
python3 ok -q make_encrypter
python3 ok -q make_decrypter
Question 7: Using our Encryption (Optional)
In this section, we will use our existing encryptors and decryptors to protect
the contents of shakespeare.txt
.
Use the make_encrypter
and make_decrypter
functions that you've just written
to fill in generator
in lab02_extra.py.
def generator():
"""Generates an encrypter and decrypter.
>>> e, d = generator()
>>> msg = 'text'
>>> encrypted = e(msg)
>>> encrypted != msg
True
>>> decrypted = d(encrypted)
>>> decrypted == msg
True
"""
"*** YOUR CODE HERE ***"
return None, None # Change this line
caesar2 = caesar_generator(2, add)
caesar3 = caesar_generator(3, add)
brutus2 = caesar_generator(2, sub)
brutus3 = caesar_generator(3, sub)
return make_encryptor(caesar2, mirror_letter, caesar3), \
make_decrypter(brutus2, mirror_letter, brutus3)
encryptor, decryptor = generator()
Then, run the following in your terminal
$ python3 lab02_extra.py encrypt --source shakespeare.txt --output shakespeare-encrypted.txt
To decrypt the encrypted text, run the following.
$ python3 lab02_extra.py decrypt --source shakespeare-encrypted.txt --output shakespeare-decrypted.txt
Submit your lab with python3 ok --submit
.
Coding Practice
It's ok if you don't finish these questions during lab. However, we strongly encourage you to try them out on your own time for extra practice.
Question 8: WWPP: Community
Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok -q community -u
>>> def troy():
... abed = 0
... while abed < 3:
... britta = lambda: abed
... print(abed)
... abed += 2
... annie = abed
... annie += 1
... abed = 6 # seasons and a movie
... return britta
>>> jeff = troy()
______0
2
>>> shirley = lambda: jeff
>>> pierce = shirley()
>>> pierce()
______6
Question 9: Lambda the Plentiful
Try drawing an environment diagram for the following code and predict what Python will output.
Note: This is a challenging problem! Work together with your neighbors and see if you can arrive at the correct answer.
You can check your work with the Online Python Tutor, but try drawing it yourself first!
>>> def go(bears):
... gob = 3
... print(gob)
... return lambda ears: bears(gob)
>>> gob = 4
>>> bears = go(lambda ears: gob)
______3
>>> bears(gob)
______4
Hint: What is the parent frame for a lambda function?
Note: The following questions are in lab02_extra.py.
Question 10: Count van Count
Consider the following implementations of count_factors
and count_primes
:
def count_factors(n):
"""Return the number of positive factors that n has."""
i, count = 1, 0
while i <= n:
if n % i == 0:
count += 1
i += 1
return count
def count_primes(n):
"""Return the number of prime numbers up to and including n."""
i, count = 1, 0
while i <= n:
if is_prime(i):
count += 1
i += 1
return count
def is_prime(n):
return count_factors(n) == 2 # only factors are 1 and n
The implementations look quite similar! Generalize this logic by writing a
function count_cond
, which takes in a two-argument predicate function cond(n,
i)
. count_cond
returns a one-argument function that counts all the numbers
from 1 to n
that satisfy cond
.
def count_cond(condition):
"""
>>> count_factors = count_cond(lambda n, i: n % i == 0)
>>> count_factors(2) # 1, 2
2
>>> count_factors(4) # 1, 2, 4
3
>>> count_factors(12) # 1, 2, 3, 4, 6, 12
6
>>> is_prime = lambda n, i: count_factors(i) == 2
>>> count_primes = count_cond(is_prime)
>>> count_primes(2) # 2
1
>>> count_primes(3) # 2, 3
2
>>> count_primes(4) # 2, 3
2
>>> count_primes(5) # 2, 3, 5
3
>>> count_primes(20) # 2, 3, 5, 7, 11, 13, 17, 19
8
"""
"*** YOUR CODE HERE ***"
def counter(n):
i, count = 1, 0
while i <= n:
if condition(n, i):
count += 1
i += 1
return count
return counter
Use OK to test your code:
python3 ok -q count_cond
Question 11: I Heard You Liked Functions...
Define a function cycle
that takes in three functions f1
, f2
,
f3
, as arguments. cycle
will return another function that should
take in an integer argument n
and return another function. That
final function should take in an argument x
and cycle through
applying f1
, f2
, and f3
to x
, depending on what n
was. Here's the what the final function should do to x
for a few
values of n
:
n = 0
, returnx
n = 1
, applyf1
tox
, or returnf1(x)
n = 2
, applyf1
tox
and thenf2
to the result of that, or returnf2(f1(x))
n = 3
, applyf1
tox
,f2
to the result of applyingf1
, and thenf3
to the result of applyingf2
, orf3(f2(f1(x)))
n = 4
, start the cycle again applyingf1
, thenf2
, thenf3
, thenf1
again, orf1(f3(f2(f1(x))))
- And so forth.
Hint: most of the work goes inside the most nested function.
def cycle(f1, f2, f3):
""" Returns a function that is itself a higher order function
>>> def add1(x):
... return x + 1
>>> def times2(x):
... return x * 2
>>> def add3(x):
... return x + 3
>>> my_cycle = cycle(add1, times2, add3)
>>> identity = my_cycle(0)
>>> identity(5)
5
>>> add_one_then_double = my_cycle(2)
>>> add_one_then_double(1)
4
>>> do_all_functions = my_cycle(3)
>>> do_all_functions(2)
9
>>> do_more_than_a_cycle = my_cycle(4)
>>> do_more_than_a_cycle(2)
10
>>> do_two_cycles = my_cycle(6)
>>> do_two_cycles(1)
19
"""
"*** YOUR CODE HERE ***"
def ret_fn(n):
def ret(x):
i = 0
while i < n:
if i % 3 == 0:
x = f1(x)
elif i % 3 == 1:
x = f2(x)
else:
x = f3(x)
i += 1
return x
return ret
return ret_fn
Use OK to test your code:
python3 ok -q cycle