Lab 05 - Higher Order Functions
Due by 11:59pm on 2023-07-06.
Starter Files
Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab.
Topics
Lambdas
A lambda expression evaluates to a function, called a lambda function. For example, lambda y: x + y is a lambda expression, and can be read as “a function that takes in one parameter y and returns x + y.”
A lambda expression by itself evaluates to a function but does not bind it to a name, as opposed to defining a function where the name is immediately bound to a function object.
However, we can bind a lambda function to a name by doing the following:
square = lambda x: x * xThis works exactly that same as
def square(x):
return x * xUnlike def statements, lambda expressions can be used as an operator or an operand to a call expression. This is because they are simply a one-line expressions that evaluate to a function. In the example below, (lambda y: y + 5) is the operator and 4 is the operand.
>>> (lambda y: y + 5)(4)
9
>>> (lambda f, x: f(x))(lambda y: y + 1, 10)
11Higher Order Functions
A higher order function (HOF) is a function that manipulates other functions by taking in functions as arguments, returning a function, or both. For example, the function compose below takes in two functions as arguments and returns a function that is the composition of the two arguments.
def composer(func1, func2):
"""Return a function f, such that f(x) = func1(func2(x)).
>>> square_then_half = composer(lambda x: x // 2, lambda x: x**2)
>>> square_then_half(4)
8
"""
def f(x):
return func1(func2(x))
return fHOFs are powerful abstraction tools that allow us to express certain general patterns as named concepts in our programs.
HOFs and Environment Diagrams
An environment diagram keeps track of all the variables that have been defined and the values they are bound to. Since values are not necessarily only integers and strings but can be functions, environment diagrams are useful as they can model more complex programs that utilize higher order functions.
Notice the following:
-
Lambdas are represented similarly to functions in environment diagrams, but since they lack instrinsic names, the lambda symbol (λ) is used instead.
-
The parent of any function (including lambdas) is always the frame in which the function is defined. It is useful to include the parent in environment diagrams in order to find variables that are not defined in the current frame. In the previous example, when we call add_two (which is really the lambda function), we need to know what x is in order to compute x + y. Since x is not in the frame f2, we look at the frame’s parent, which is f1. There, we find x is bound to 2.
-
As illustrated above, higher order functions that return a function have their return value represented with a pointer to the function object.
Required Questions
Q1: Print Cond
Write a function that takes in a number n and returns a function that can take in a single parameter cond. When we pass in some condition function cond into this returned function, it will print out numbers from 1 to n where calling cond on that number returns True.
def print_cond(n):
"""Returns a function which takes one parameter cond and prints
out all integers 1..i..n where calling cond(i) returns True.
>>> def is_even(x):
... # Even numbers have remainder 0 when divided by 2.
... return x % 2 == 0
>>> print_cond(5)(is_even)
2
4
"""
# Write your code hereNote: TA's should demonstrate this problem
Q2: Print N
Write a function print_n that can take in an integer n and returns a repeatable print function that can print the next n parameters. After the nth parameter, it just prints “done”.
def print_n(n):
"""
>>> f = print_n(2)
>>> f = f("hi")
hi
>>> f = f("hello")
hello
>>> f = f("bye")
done
>>> g = print_n(1)
>>> g("first")("second")("third")
first
done
done
<function inner_print>
"""
def inner_print(x):
if ________________________
print("done")
else:
print(x)
return ____________________
return ________________________Ignore the
<function> inner_print>line. This only happens when you are calling the function within the python interpreter, and even then that line may look slightly different.
Q3: 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.
>>> count_factors(6)
4 # 1, 2, 3, 6
>>> count_factors(4)
3 # 1, 2, 4
"""
i = 1
count = 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.
>>> count_primes(6)
3 # 2, 3, 5
>>> count_primes(13)
6 # 2, 3, 5, 7, 11, 13
"""
i = 1
count = 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 nThe implementations look quite similar! Write a function which counts the numbers from 1 to n that meet any given condition. This function, count_cond, takes in a two-argument predicate function condition(n, i) as an argument. count_cond then returns a one-argument function that takes in n. The function counts all the numbers from 1 to n that satisfy condition when called (see examples in the docstring below). Your function should look similar to count_primes and count_factors given above.
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, where
the first argument for Condition is N and the second argument is the
number from 1 to N.
>>> 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
"""
# Write your code hereSubmit
If you attend the lab, you don't have to submit anything.
If you don't attend the lab, you will have to submit working code. Submit the lab05.py file on Canvas to Gradescope in the window on the assignment page.
Extra Practice
Q4: WWPD Cake
Give this WWPD a try!
>>> def cake(): # Make sure you know when these print statements are executed!
... print('beets')
... def pie():
... print('sweets')
... return 'cake'
... return pie
>>> chocolate = cake()>>> chocolate>>> chocolate()
(line 1)?
(line 2)?>>> more_chocolate, more_cake = chocolate(), cake # double assignment!>>> more_chocolate>>> def snake(x, y): # Keep track of things on paper if you get lost.
... if cake == more_cake:
... return chocolate
... else:
... return x + y
>>> snake(10, 20)>>> snake(10, 20)()
(line 1)?
(line 2)?>>> cake = 'cake' # reassignment!
>>> snake(10, 20)Q5: Make Repeater
Implement the function make_repeater so that make_repeater(func, n)(x) returns func(func(...func(x)...)), where func is applied n times. That is, make_repeater(func, n) returns another function that can then be applied to another argument.
For example, make_repeater(square, 3)(42) evaluates to square(square(square(42))).
def make_repeater(func, n):
"""Return the function that computes the nth application of func.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
5
"""
# Write your code here