Lab 2: Lambdas and Higher-Order Functions

Due at 11:59pm on Friday, 09/08/2017.

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 - 4 must be completed in order to receive credit for this lab. Starter code for questions 3 and 4 is in lab02.py.
  • Questions 5 and 6 (Environment Diagrams) are optional. It is recommended that you work on these should you finish the required section early.
  • Questions 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.

Lambdas

Lambda expressions are one-line functions that specify two things: the parameters and the return value.

lambda <parameters>: <return value>

While both lambda and def statements are related to functions, there are some differences.

lambda def
Type lambda is an expression def is a statement
Description Evaluating a lambda expression does not create or modify any variables. Lambda expressions just create new function objects without changing the current environment. Executing a def statement will create a new function object and bind it to a variable in the current environment.
Example
lambda x: x * x
           
def square(x):
    return x * x

A lambda expression by itself is not very interesting. As with any values such as numbers, Booleans, and strings, we usually:

  • assign lambdas to variables (foo = lambda x: x)
  • pass them in to other functions (bar(lambda x: x))

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.

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

Hint: Remember for all WWPD questions, input Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

>>> lambda x: x
______
<function <lambda> at ...>
>>> a = lambda x: x >>> a(5) # x is the parameter for the lambda function
______
5
>>> b = lambda: 3 >>> b()
______
3
>>> c = lambda x: lambda: print('123') >>> c(88)
______
<function <lambda> at ...>
>>> c(88)()
______
123
>>> d = lambda f: f(4) # They can have functions as arguments as well. >>> def square(x): ... return x * x >>> d(square)
______
16
>>> t = lambda f: lambda x: f(f(f(x)))
>>> s = lambda x: x + 1
>>> t(s)(0)
______
3
>>> bar = lambda y: lambda x: pow(x, y) >>> bar()(15)
______
TypeError: <lambda>() missing 1 required positional argument: 'y'
>>> foo = lambda: 32 >>> foobar = lambda x, y: x // y >>> a = lambda x: foobar(foo(), bar(4)(x)) >>> a(2)
______
2
>>> b = lambda x, y: print('summer')
______
# Nothing gets printed by the interpreter
>>> c = b(4, 'dog')
______
summer
>>> print(c)
______
None
>>> a = lambda b: b * 2
______
# Nothing gets printed by the interpreter
>>> a
______
Function
>>> a(a(a(2)))
______
16
>>> a(a(a()))
______
TypeError: <lambda>() missing 1 required positional argument: 'b'
>>> def d(): ... print(None) ... print('whoo') >>> b = d()
______
None whoo
>>> b
______
# Nothing gets printed by the interpreter
>>> x, y, z = 1, 2, 3
>>> a = lambda b: x + y + z
>>> x += y
>>> y -= z
>>> a('b')
______
5
>>> z = 3
>>> e = lambda x: lambda y: lambda: x + y + z
>>> e(0)(1)()
______
4

Q2: WWPD: Higher Order Functions

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q hof -u

Hint: Remember for all WWPD questions, input 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
>>> stevphen = lambda x: x
>>> stewart = even(stevphen)
>>> stewart
______
<function ...>
>>> stewart(61)
______
61
>>> stewart(-4)
______
4
>>> def cake():
...    print('beets')
...    def pie():
...        print('sweets')
...        return 'cake'
...    return pie
>>> a = cake()
______
beets
>>> a
______
Function
>>> a()
______
sweets 'cake'
>>> x, b = a(), cake
______
sweets
>>> def snake(x): ... if cake == b: ... x += 3 ... return lambda y: y + x ... else: ... return y - x >>> snake(24)(23)
______
50
>>> cake = 2 >>> snake(26)
______
Error
>>> y = 50 >>> snake(26)
______
24

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

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

Optional Questions

Environment Diagrams

Q5: 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

Q6: 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:

  1. 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?
  2. In frame f2, what name is the frame labeled with (add_ten or λ)? Which frame is the parent of f2?
  3. What value is the variable result bound to in the Global frame?

You can try out the environment diagram at tutor.cs61a.org.

  1. The intrinsic name of the function object that add_ten points to is λ (specifically, the lambda whose parameter is k). The parent frame of this lambda is f1.
  2. f2 is labeled with the name λ the parent frame of f2 is f1, since that is where λ is defined.
  3. The variable result is bound to 19.

More Coding Practice

Note: The following questions are in lab02_extra.py.

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, return x
  • n = 1, apply f1 to x, or return f1(x)
  • n = 2, apply f1 to x and then f2 to the result of that, or return f2(f1(x))
  • n = 3, apply f1 to x, f2 to the result of applying f1, and then f3 to the result of applying f2, or f3(f2(f1(x)))
  • n = 4, start the cycle again applying f1, then f2, then f3, then f1 again, or f1(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