Lab 2: Lambda Expressions and Higher-Order Functions
Due at 11:59pm on Friday, 02/02/2018.
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.
Check that you have successfully submitted your code on
okpy.org.
- Questions 1-3 must be completed in order to receive credit for this lab. Starter code for question 3 is in lab02.py.
- Questions 4 and 5 (Environment Diagrams) are optional, but highly recommended. Try to work on at least one of these if you finish the required section early.
- Questions 6, 7, and 8 are also optional. It is recommended that you complete these problems on your own time. Starter code for the questions are 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.
Lambda Expressions
Lambda expressions are one-line functions that specify two things: the parameters and the return expression.
lambda <parameters>: <return expression>
While both lambda
and def
create function objects, there are some notable
differences. lambda
expressions work like other expressions; much like a
mathematical expression just evaluates to a number and does not alter the current
environment, a lambda
expression evaluates to a function without
changing the current environment. Let's take a closer look.
lambda | def | |
---|---|---|
Type | Expression that evaluates to a value | Statement that alters the environment |
Effect on the environment | Evaluating a lambda expression does not create or
modify any variables. |
Executing a def statement both creates a new function
object and binds it to a name in the current environment. |
Usage | Because a lambda expression doesn't bind the created
function object to any name, it must be used within a statement or a call
expression to actually do something interesting in the program. See the
examples below. |
After executing a def statement, the created function is
ready to use. You can refer to it with the name given in the
def statement header. |
Example |
|
|
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.
Functions as arguments
In Python, function objects are values that can be passed around. We know that one
way to create functions is by using a def
statement:
def square(x):
return x * x
The above statement created a function object with the intrinsic name square
as
well as binded it to the name square
in the current environment. Now let's try
passing it as an argument.
First, let's write a function that takes in another function as an argument:
def scale(f, x, k):
""" Returns the result of f(x) scaled by k. """
return k * f(x)
We can now call scale
on square
and some other arguments:
>>> scale(square, 3, 2) # Double square(3)
18
>>> scale(square, 2, 5) # 5 times 2 squared
20
Note that in the body of the call to scale
, the function object with the intrinsic
name square
is bound to the parameter f
. Then, we call square
in the body of
scale
by calling f(x)
.
As we saw in the above section on lambda expressions, we can also pass lambda
functions into call expressions!
>>> scale(lambda x: x + 10, 5, 2)
30
In the frame for this call expression, the name f
is bound to the function created
by the lambda expression lambda x: x + 10
.
Functions that return functions
Because functions are values, you can also return them in other functions! Here's an example:
def multiply_by(m):
def multiply(n):
return n * m
return multiply
In this particular case, we defined the function multiply
within the body of multiply_by
and then returned it. Let's see it in action:
>>> multiply_by(3)
<function multiply_by.<locals>.multiply at ...>
>>> multiply(4)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'multiply' is not defined
A call to multiply_by
returns a function, as expected. However, calling multiply
errors, even though that's the name we gave the inner function. This is because the
name multiply
only exists within the frame where we evaluate the body of
multiply_by
.
So how do we actually use the inner function? Here are two ways:
>>> times_three = multiply_by(3) # Assign the result of the call expression to a name
>>> times_three(5) # Call the inner function with its new name
15
>>> multiply_by(3)(10) # Chain together two call expressions
30
The point is, because multiply_by
returns a function, you can use its return value
just like you would use any other function!
Here's what multiply_by
would look like if we wrote it with a lambda expression:
def multiply_by(m):
return lambda n: n * m
As you can see, lambda expressions make writing higher order functions much cleaner.
Environment Diagrams
Environment diagrams are one of the best learning tools for understanding lambda
expressions and higher order functions because you're able to keep track of all
the different names, function objects, and arguments to functions. We highly
recommend drawing environment diagrams or using Python tutor
if you get stuck doing the WWPD problems below. Here are the rules as a refresher.
def Statements
- Draw the function object with its intrinsic name, formal parameters, and parent frame. A function's parent frame is the frame in which the function was defined.
- Write the intrinsic name of the function in the current frame and bind it to the newly created function object.
Call expressions
- Evaluate the operator, whose value should be a function.
- Evaluate the operands left to right.
- Open a new frame. Label it with the sequential frame number, the intrinsic name of the function, and its parent.
- Bind the formal parameters of the function to the arguments whose values you found in step 2.
- Execute the body of the function in the new environment.
Assignment Statements
- Evaluate the expression on the right hand side of the
=
sign. - Write the name found on the left hand side of the
=
sign in the current frame and bind the value obtained in step 1 to this name.
Required Questions
What Would Python Display?
Q1: WWPD: Lambda the Free
Use Ok to test your knowledge with the following "What Would Python Display?" questions:
python3 ok -q lambda -u
For all WWPD questions, type
Function
if you believe the answer is<function...>
, >Error
if it errors, andNothing
if nothing is displayed.
>>> lambda x: x # A lambda expression with one parameter x
______<function <lambda> at ...>
>>> a = lambda x: x # Assigning the lambda function to the name a
>>> a(5)
______5
>>> (lambda: 3)() # Using a lambda expression as an operator in a call exp.
______3
>>> b = lambda x: lambda: x # Lambdas can return other lambdas!
>>> c = b(88)
>>> c
______<function <lambda> at ...
>>> c()
______88
>>> d = lambda f: f(4) # They can have functions as arguments as well.
>>> def square(x):
... return x * x
>>> d(square)
______16
>>> z = 3
>>> e = lambda x: lambda y: lambda: x + y + z
>>> e(0)(1)()
______4
>>> f = lambda z: x + z
>>> f(3)
______NameError: name 'x' is not defined
>>> higher_order_lambda = lambda f: lambda x: f(x)
>>> g = lambda x: x * x
>>> higher_order_lambda(2)(g) # Which argument belongs to which function call?
______Error
>>> higher_order_lambda(g)(2)
______4
>>> call_thrice = lambda f: lambda x: f(f(f(x)))
>>> call_thrice(lambda y: y + 1)(0)
______3
>>> print_lambda = lambda z: print(z) # When is the return expression of a lambda expression executed?
>>> print_lambda
______Function
>>> one_thousand = print_lambda(1000)
______1000
>>> one_thousand
______# print_lambda returned None, so nothing gets displayed
Q2: WWPD: Higher Order Functions
Use Ok to test your knowledge with the following "What Would Python Display?" questions:
python3 ok -q hof -u
For all WWPD questions, type
Function
if you believe the answer is<function...>
, >Error
if it errors, andNothing
if nothing is displayed.
>>> def even(f):
... def odd(x):
... if x < 0:
... return f(-x)
... return f(x)
... return odd
>>> steven = lambda x: x
>>> stewart = even(steven)
>>> stewart
______<function ...>
>>> stewart(61)
______61
>>> stewart(-4)
______4
>>> def cake():
... print('beets')
... def pie():
... print('sweets')
... return 'cake'
... return pie
>>> chocolate = cake()
______beets
>>> chocolate
______Function
>>> chocolate()
______sweets
'cake'
>>> more_chocolate, more_cake = chocolate(), cake
______sweets
>>> more_chocolate
______'cake'
>>> def snake(x, y):
... if cake == more_cake:
... return lambda y: x + y
... else:
... return x + y
>>> snake(10, 20)
______Function
>>> snake(10, 20)(30)
______40
>>> cake = 'cake'
>>> snake(10, 20)
______30
Coding Practice
Q3: Lambdas and Currying
We can transform multiple-argument functions into a chain of single-argument, higher order functions by taking advantage of lambda expressions. This is useful when dealing with functions that take only single-argument 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 or refer to the
textbook
if you're not sure what this means.
def lambda_curry2(func):
"""
Returns a Curried version of a two-argument 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
Optional Questions
Environment Diagram Practice
Q4: Lambda the Environment Diagram
Try drawing an environment diagram for the following code and predict what Python will output.
You do not need to submit or unlock this question through Ok. Instead, 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
Q5: 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 object. What is the intrinsic name of that function object, 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.
More Coding Practice
Note: The following questions are in lab02_extra.py.
Q6: Composite Identity Function
Write a function that takes in two single-argument 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 defined 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
# Alternative solution
return lambda x: f(g(x)) == g(f(x))
Use Ok to test your code:
python3 ok -q composite_identity
Q7: 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 condition(n,
i)
. count_cond
returns a one-argument 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 two-argument 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
Q8: 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 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