Starter Files
Lab Format
As in Hog Phase 1, we will be using the op
autograder again (and for all future assignments)! You will be able to get realtime feedback and work through your mistakes this way.
Review + Some extras
In Lecture 04, we learned about higherorder functions (HOF)! These are useful for many things such as generalization and recursion.
1. Designing functions
All functions’ parent frame is the one it was defined in.
def
statement
Review: in Python, functions can be defined using the def
statement as following:
def foo(paramater): #Function signature: "def" keyword, function name, parameters <function body> #Function body: code you want to execute return <expression> #Return statement: returns value
Lambda expressions
In the lecture, we learned about a new type of function: lambda expressions!
Just like a def
function, a lambda function takes in parameters and returns some value.
Unlike a def
function, a lambda function is much more limited in that they can only return a single expression (no other statements). Also, lambda functions do not have names bound to them, unlike a def
function.
This means that lambda functions are generally much more limited in what they can do. Typically, lambda functions are used as inputs to HOFs (will elaborate on this later), when they are only needed for a short period of time, or when the function can be defined as a single expression.
Here are some examples:
>>> square = lambda x: x * x #x is the parameter, x * x is returned >>> square(3) 9 #3 * 3 = 9 >>> add_xy = lambda x, y: x + y #x, y are the parameters, x + y is returned >>> add_xy(2, 4) 2 #2 + (4) = 2
Describing a function
The following terms can be used to describe any function:
 Domain: The set of possible inputs a function may take as arguments
 Range: The set of possible output values a function may return
 Behavior: The relationship between input and output
Here is an example using a function defined with def
:
def square(x): #Takes in any real numbers (domain) return x * x #Outputs the square, which is nonnegative and real (range)
 Domain: all real numbers
 Range: nonnegative real numbers
 Behavior: the output is the square of the input
Here is an example using a lambda function:
double = lambda x: x * 2 #Takes in any real numbers (domain) #Outputs the double of the input, which is also real (range)
 Domain: all real numbers
 Range: real numbers
 Behavior: the output is the double of the input
2. Higherorder function
Functions are firstclass, which means they can be manipulated as values.
This leads to the definition of higherorder function: a function that takes in a function as an input, or outputs a function.
HOF examples:
Example 1: An example from Hog Phase 1!
#Example 1: An example from Hog Phase 1! def make_fair_dice(sides): #The higherorder function """Return a die that returns 1 to SIDES with equal chance.""" assert type(sides) == int and sides >= 1, 'Illegal value for sides' def dice(): #Note that the parent frame of dice() is make_fair_dice() return randint(1,sides) return dice #The higherorder function make_fair_dice() returns dice() four_sided = make_fair_dice(4) #four_sided() is also a function because make_fair_dice() returned a function
In this example, make_fair_dice()
is the HOF because it returns a function in line 7. Thus, four_sided = make_fair_dice(4)
(line 9) is an assignment statement that evaluates the call expression make_fair_dice(4)
, which returns a function, then binds it tofour_sided
. Now that four_sided
is function, it can be called with the call expression four_sided()
!
Environment diagram for make_fair_dice()
Currying examples:
We can use higherorder functions to convert a function that takes multiple arguments into a chain of functions that each take a single argument. More specifically, given a function
https://composingprograms.com/pages/16higherorderfunctions.html#curryingf(x, y)
, we can define a functiong
such thatg(x)(y)
is equivalent tof(x, y)
. Here,g
is a higherorder function that takes in a single argumentx
and returns another function that takes in a single argumenty
. This transformation is called currying.
Example 2: curried adder (an example using lambdas)
#Example 2: curried adder (an example using lambdas) hof_adder = lambda x: lambda y: x + y #hof_adder() is a HOF because it returns a function adder_2 = hof_adder(2) #hof_adder() outputs a function value, so adder_2 gets binded to the lambda function that adds 2 to whatever is inputted into it adder_2(3) #Will output 3 + 2 = 1 adder_2(4) #Will output 4 + 2 = 6
In this example, hof_adder
is the HOF because it returns a lambda function. Thus, adder_2
gets binded to the adder function returned by hof_adder(2)
. Because adder_2()
is a function, it can be called on as shown in lines 4 and 5.
In this example, currying allows us to create adder functions without needing to create a specific function for each addition we wish to compute.
Environment diagram for hofadder
Example 3: curried pow (an example using def
)
def curried_pow(x): def h(y): return pow(x, y) #Abstraction! (assume pow() works as intended) return h curried_pow(2)(3) #Will output 2 ** 3 = 8
In this example, curried_pow()
is the HOF because it returns a function (h
). Thus, the call expression curried_pow(2)
returns a function that can be called on, which is why curried_pow(2)(3)
will output 2³ = 8.
In this example, currying allows us to create pow functions without needing to create a specific function for each power we wish to compute.
Environment diagram for curry_pow()
Example 4: double currying and uncurrying (advanced)
def curry2(f): """Return a curried version of the given twoargument function.""" def g(x): def h(y): return f(x, y) return h return g def uncurry2(g): """Return a twoargument version of the given curried function.""" def f(x, y): return g(x)(y) return f
The
https://composingprograms.com/pages/16higherorderfunctions.html#curryingcurry2
function takes in a twoargument functionf
and returns a singleargument functionf
. Wheng
is applied to an argumentx
, it returns a singleargument functionh
. Whenh
is applied toy
, it callsf(x, y)
. Thus,curry2(f)(x)(y)
is equivalent tof(x, y)
. Theuncurry2
function reverses the currying transformation, so thatuncurry2(curry2(f))
is equivalent tof
.
3. Generalization
Generalization is a useful technique using HOF where you find common structures to allow for shared interpretation.
Example from the slide:
identity = lambda k: k cube = lambda k: pow(k, 3) def summation(n, term): """ Sum the first n terms of a sequence from 1 >>> summation(5, identity) 15 >>> summation(5, cube) 225 """ total, k = 0, 1 while k <= n: total, k = total + term(k), k + 1 return total
summation()
is a HOF because it takes in a function—term
.
This example demonstrations generalization because it can compute the summation of any sequence. This is achieved by having the parameter term
. term
determines what the nᵗʰ is before adding it to the total.
4. Function composition
Function composition is the action of taking multiple simple functions and combining them into a more complex one.
It’s just like in math where we can take f(x) and g(x) to form f(g(x)) or g(f(x))!
But, in programming, something like f(g(x)) would just be a nested call expression. In order to save the composite function to create h(x), it would require making a third function.
Simple example first:
>>> def f(x): ... return 2*x ... >>> def g(x): ... return x**2 ... >>> f(g(2)) # Nested call expression 8 >>> g(f(2)) 16 >>> def compose(func1, func2): ... def h(x): # h(x) isn't executed yet! ... return func1(func2(x)) ... return h ... >>> h = compose(f,g) # compose(f, g) evaluates to the composite function >>> h(2) # same as f(g(2)) 8 >>> h = compose(g, f) # returns g(f(x)) >>> h(2) # same as g(f(2)) 16
Doing the Assignment
Do the actual coding in the lab04.py
file with Atom! I’m only describing what the problems are below.
What Would Python Display? (WWPD) problems:
As mentioned previously, we will be using the op
autograder again. For these problems, type in what Python would display after “?” .
If a question will result in an error, put in the string “Error”.
If a question will result in None, put in None.
If a question will result in no output, put in “Nothing”.
If a question will result in a function, put in the string “Function”.
To distinguish between printed logs and outputted strings, add single quotes around your string anwers:
>>> def returns1(): ... return '1' ... >>> print(1) 1 >>> returns1() '1'
Q1: WWPD: Lambda the Free
Use Op to test your knowledge with the following “What Would Python Display?” questions:
python3 op q 1 u
For all WWPD questions, type Function
if you believe the answer is <function...>
, Error
if it errors, and Nothing
if nothing is displayed.
>>> lambda x: x # A lambda expression with one parameter x ______ >>> a = lambda x: x # Assigning the lambda function to the name a >>> a(5) ______ >>> (lambda: 3)() # Using a lambda expression as an operator in a call exp. ______ >>> b = lambda x: lambda: x # Lambdas can return other lambdas! >>> c = b(88) >>> c ______ >>> c() ______ >>> d = lambda f: f(4) # They can have functions as arguments as well. >>> def square(x): ... return x * x >>> d(square) ______
>>> z = 3 >>> e = lambda x: lambda y: lambda: x + y + z >>> e(0)(1)() ______ >>> f = lambda z: x + z >>> f(3) ______
>>> 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? ______ >>> higher_order_lambda(g)(2) ______ >>> call_thrice = lambda f: lambda x: f(f(f(x))) >>> call_thrice(lambda y: y + 1)(0) ______ >>> print_lambda = lambda z: print(z) # When is the return expression of a lambda expression executed? >>> print_lambda ______ >>> one_thousand = print_lambda(1000) ______ >>> one_thousand ______
Q2: WWPD: Higher Order Functions
Use Op to test your knowledge with the following “What Would Python Display?” questions:
python3 op q 2 u
For all WWPD questions, type Function
if you believe the answer is <function...>
, Error
if it errors, and Nothing
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 ______ >>> stewart(61) ______ >>> stewart(4) ______
>>> def cake(): ... print('beets') ... def pie(): ... print('sweets') ... return 'cake' ... return pie >>> chocolate = cake() ______ >>> chocolate ______ >>> chocolate() ______ >>> more_chocolate, more_cake = chocolate(), cake ______ >>> more_chocolate ______ >>> def snake(x, y): ... if cake == more_cake: ... return lambda: x + y ... else: ... return x + y >>> snake(10, 20) ______ >>> snake(10, 20)() ______ >>> cake = 'cake' >>> snake(10, 20) ______
Coding Practice
Free Response Questions (FRQs)
Q1 HoF Adder
Drawing the environmental diagram
Once you’re done with coding, draw an enviornmental diagram for when your def statement is executed and hof_adder(1)(2)
is executed.
Once you’re done drawing, put your def statement and hof_adder(1)(2)
into Python Tutor, visualize execution, and mark down what you got wrong. Submit a photo of that. Example of what you want to put into Python Tutor:
def _(): """ Write a function named hof_adder which takes in one integer argument x and returns a function named adder that takes in one integer argument y. The returned function adder returns x+y. For this question, you'll have to draw an environmental diagram as well. Read the post for instructions on how to do it. >>> adder_2 = hof_adder(2) >>> adder_2(3) 1 >>> adder_2(4) 6 >>> adder_3 = hof_adder(3) >>> adder_3(4) 7 """ # Your code goes here
Q2 Curried Pow
Drawing the environmental diagram
For this question, basically do the same thing as the question above. Draw an environmental diagram of your def statement being executed and curried_pow(1)(2)
being executed.
Once you’re done, compare your result to what Python Tutor shows, and mark down anything you got wrong. Submit an image of that too.
def _(): """ Write a function named curried_pow which takes in one intege argument x and returns a lambda function that takes in one integer argument y. The returned lambda function returns x to the power of y. The autograder will check if you've used lambda or not! Don't use a def statement. For this question, you'll also draw an environmental diagram to submit. Look in the post for more instructions. >>> curried_pow(2)(3) 8 >>> curried_pow(2)(4) 16 >>> curried_pow(1)(100) 1 >>> curried_pow(0)(100) 0 >>> curried_pow(1234)(0) 1 """
You’re done! Upload your screenshot here!
Screenshot for coding & WWPD part’s completion
Upload files






Screenshot for FRQ1 Env Diagram Drawing:
Screenshot for FRQ2 Env Diagram Drawing:
If you encounter any issues, please contact Leo, Eugene, or John through Wechat. Thanks!