Lab 2: Lambdas and HigherOrder Functions
Due at 11:59pm on 06/28/2016.
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, 2, 3, and 4 must be completed in order to receive credit for this lab. Starter code for questions 3 and 4 is in lab02.py.
 Question 5 (What Would Python Display?) is optional. It is recommended that you work on this should you finish the required section early, or if you are struggling with the required questions.
 Questions 6, 7, 8, and 9 (Coding) are optional. It is recommended that you complete these problems on your own time. Starter code for questions 7, 8, and 9 is in lab02_extra.py.
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Lambdas
Lambda expressions are oneline 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 values. 
Executing a def statement will create a new function value and bind it to a variable in the current environment. 
Example 


A lambda
expression by itself is not very interesting. As with any values
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)
)
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.
Required Questions
What Would Python Display?
Question 1: WWPD: Lambda the Free
Use OK to test your knowledge with the following "What Would Python Display?" questions:
python3 ok q lambda u
Hint: Remember for all WWPD questions, input
Function
if you believe the answer is<function...>
,Error
if it errors, andNothing
if nothing is displayed.
>>> lambda x: x
______<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
>>> a = lambda b: b * 2
______# Nothing gets printed by the interpreter
>>> a
______Function
>>> a(a(a(2)))
______16
>>> a(a(a()))
______TypeError: <lambda>() missing 1 required positional argument: 'b'
>>> def d():
... print(None)
... print('whoo')
>>> b = d()
______None
whoo
>>> b
______# Nothing gets printed by the interpreter
>>> x, y, z = 1, 2, 3
>>> a = lambda b: x + y + z
>>> x += y
>>> y = z
>>> a('b')
______5
>>> z = 3
>>> e = lambda x: lambda y: lambda: x + y + z
>>> e(0)(1)()
______4
Question 2: WWPD: Higher Order Functions
Use OK to test your knowledge with the following "What Would Python Display?" questions:
python3 ok q hof u
Hint: Remember for all WWPD questions, input
Function
if you believe the answer is<function...>
,Error
if it errors, andNothing
if nothing is displayed.
>>> 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
>>> def cake():
... print('beets')
... def pie():
... print('sweets')
... return 'cake'
... return pie
>>> a = cake()
______beets
>>> a
______Function
>>> a()
______sweets
'cake'
>>> x, b = a(), cake
______sweets
>>> def snake(x):
... if cake == b:
... x += 3
... return lambda y: y + x
... else:
... return y  x
>>> snake(24)(23)
______50
>>> cake = 2
>>> snake(26)
______Error
>>> y = 50
>>> snake(26)
______24
Coding Practice
Question 3: Lambdas and Currying
We can transform multipleargument functions into a chain of singleargument, higher order functions by taking advantage of lambda expressions. This is useful when dealing with functions that take only singleargument functions. We will see some examples of these later on.
Write a function lambda_curry2
that will curry any two argument
function using lambdas. See the doctest if you're not sure what this
means.
def lambda_curry2(func):
"""
Returns a Curried version of a twoargument function FUNC.
>>> from operator import add
>>> curried_add = lambda_curry2(add)
>>> add_three = curried_add(3)
>>> add_three(5)
8
"""
"*** YOUR CODE HERE ***"
return ______
return lambda arg1: lambda arg2: func(arg1, arg2)
Use OK to test your code:
python3 ok q lambda_curry2
Question 4: Composite Identity Function
Write a function that takes in two singleargument functions, f
and g
, and
returns another function that has a single parameter x
. The returned
function should return True
if f(g(x))
is equal to g(f(x))
. You can
assume the output of g(x)
is a valid input for f
and vice versa.
You may use the compose1
function from lecture, redefined below.
def compose1(f, g):
"""Return the composition function which given x, computes f(g(x)).
>>> add_one = lambda x: x + 1 # adds one to x
>>> square = lambda x: x**2
>>> a1 = compose1(square, add_one) # (x + 1)^2
>>> a1(4)
25
>>> mul_three = lambda x: x * 3 # multiplies 3 to x
>>> a2 = compose1(mul_three, a1) # ((x + 1)^2) * 3
>>> a2(4)
75
>>> a2(5)
108
"""
return lambda x: f(g(x))
def composite_identity(f, g):
"""
Return a function with one parameter x that returns True if f(g(x)) is
equal to g(f(x)). You can assume the result of g(x) is a valid input for f
and vice versa.
>>> add_one = lambda x: x + 1 # adds one to x
>>> square = lambda x: x**2
>>> b1 = composite_identity(square, add_one)
>>> b1(0) # (0 + 1)^2 == 0^2 + 1
True
>>> b1(4) # (4 + 1)^2 != 4^2 + 1
False
"""
"*** YOUR CODE HERE ***"
def identity(x):
return compose1(f, g)(x) == compose1(g, f)(x)
return identity
return lambda x: f(g(x)) == g(f(x))
Use OK to test your code:
python3 ok q composite_identity
Optional Questions
What Would Python Display?
Question 5: 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
Environment Diagrams
Question 6: Make Adder
Draw the environment diagram for the following code:
n = 9
def make_adder(n):
return lambda k: k + n
add_ten = make_adder(n+1)
result = add_ten(n)
There are 3 frames total (including the Global frame). In addition, consider the following questions:
 In the Global frame, the name
add_ten
points to a function value. What is the intrinsic name of that function value, and what frame is its parent?  In frame
f2
, what name is the frame labeled with (add_ten
or λ)? Which frame is the parent off2
?  What value is the variable
result
bound to in the Global frame?
You can try out the environment diagram at tutor.cs61a.org.
 The intrinsic name of the function object that
add_ten
points to is λ (specifically, the lambda whose parameter isk
). The parent frame of this lambda isf1
. f2
is labeled with the name λ the parent frame off2
isf1
, since that is where λ is defined. The variable
result
is bound to 19.
Coding Practice
Note: The following questions are in lab02_extra.py.
Question 7: Foldl
Write a function that takes in a list s
, a function f
, and an initial value
start
. This function will fold s
starting at the beginning. If s
is [1,
2, 3, 4, 5]
then the function f
is applied as follows:
f(f(f(f(f(start, 1), 2), 3), 4), 5)
You may assume that the function f
takes in two parameters.
from operator import add, sub, mul
def foldl(s, f, start):
"""Return the result of applying the function F to the initial value START
and the first element in S, and repeatedly applying F to this result and
the next element in S until we reach the end of the list.
>>> s = [3, 2, 1]
>>> foldl(s, sub, 0) # sub(sub(sub(0, 3), 2), 1)
6
>>> foldl(s, add, 0) # add(add(add(0, 3), 2), 1)
6
>>> foldl(s, mul, 1) # mul(mul(mul(1, 3), 2), 1)
6
>>> foldl([], sub, 100) # return start if s is empty
100
"""
"*** YOUR CODE HERE ***"
total = start
for number in s:
total = f(total, number)
return total
Use OK to test your code:
python3 ok q foldl
Question 8: 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 twoargument predicate function condition(n,
i)
. count_cond
returns a oneargument function that counts all the numbers
from 1 to n
that satisfy condition
.
def count_cond(condition):
"""Returns a function with one parameter N that counts all the numbers from
1 to N that satisfy the twoargument predicate function 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 9: 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 higherorder 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 switch(i):
return [f1, f2, f3][i % 3]
def make_cycle(n):
def apply_n_times(x):
for i in range(n):
x = switch(i)(x)
return x
return apply_n_times
return make_cycle
Use OK to test your code:
python3 ok q cycle