Lab 11 - Higher Order Functions
Due by 11:59pm on 2024-02-15.
Starter Files
Download lab11.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: WWPD: Cake
Give this WWPD a try!
If you ever unsure or stuck on what Python will display, run the code yourself in the Python interpreter or Pytutor and see what Python displays!
Note: When you try to print a function without ever calling it, Python will display its memory location in your device among other things.
>>> 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()
_____
_____
>>> more_chocolate, more_cake = chocolate(), cake # double assignment!
_____
>>> more_chocolate
_____Q2: Filter
Note: TA's should demonstrate how to solve this problem.
Implement a function filter that take in a list of integers lst and a function cond.
filter will return a list where the only elements in it are the elements in lst where
cond returned True for that element (i.e. cond(elem) is True). cond will be and should be a one argument function
that either returns True or False. (You will not be implementing a cond function.)
def filter(lst, cond):
"""Returns a list where each element is an element where `cond(elem)` returns `True`.
>>> nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> is_even = lambda x : x % 2 == 0 # Even numbers have remainder 0 when divided by 2.
>>> filter(nums, is_even)
[2, 4, 6, 8, 10]
"""
"*** YOUR CODE HERE ***"python3 -m doctest lab11.pyQ3: Print Cond
Write a function that takes in a number n and returns a function that can take in a
single parameter cond. cond will be a one argument function. 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
"""
"*** YOUR CODE HERE ***"Hint: To return a function that takes in a single parameter, first define a function within the body of
print_condthat takes in a single parameter. Now return that function within the body ofprint_condand implement that function.
Test your code:
python3 -m pytest test_lab11.py::test_print_cond_1python3 -m pytest test_lab11.py::test_print_cond_2Q4: 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
"""
"*** YOUR CODE HERE ***"Test your code:
python3 -m pytest test_lab11.py::test_count_cond_1python3 -m pytest test_lab11.py::test_count_cond_2Q5: 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.
Hint: What if within the function body of
inner_print, you returnprint_n(n-1)? Then, you can treatnas some sort of counter variable that keeps track of the amount of times the function has left to print.
Test your code:
python3 -m pytest test_lab11.py::test_print_n_1python3 -m pytest test_lab11.py::test_print_n_2Submit
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 lab11.py file on Canvas to Gradescope in the window on the assignment page.
Extra Practice
Q6: WWPD: Cake and Snake
Give this WWPD a try! Continue where you left off in Q1!
>>> 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()
_____
_____
>>> 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)()
_____
>>> cake = 'cake' # reassignment!
>>> snake(10, 20)
_____Q7: 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
"""
"*** YOUR CODE HERE ***"