Lab 12 - Higher Order Functions

Due by 11:59pm on 2024-02-15.

Starter Files

Download lab12.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 * x

This works exactly that same as

def square(x):
    return x * x

Unlike 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)
11

Higher 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 f

HOFs 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 lab12.py

Q3: 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_cond that takes in a single parameter. Now return that function within the body of print_cond and implement that function.

Test your code:

python3 -m pytest test_lab12.py::test_print_cond_1
python3 -m pytest test_lab12.py::test_print_cond_2

Q4: 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 n

The 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_lab12.py::test_count_cond_1
python3 -m pytest test_lab12.py::test_count_cond_2

Q5: 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 return print_n(n-1)? Then, you can treat n as 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_lab12.py::test_print_n_1
python3 -m pytest test_lab12.py::test_print_n_2

Submit

Submit the lab12.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 ***"

© 2024 Brigham Young University, All Rights Reserved