Lab 2: Higher-Order Functions, Lambdas and Recursion

Due at 11:59pm on 02/05/2016.

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.

  • Questions 1 through 3 (What Would Python Print?) are designed to help introduce concepts and test your understanding.
  • For submission, please complete at least questions 3, 5, 7, 8, and 9 in lab02.py. Submit using OK.
  • Questions 10 through 13 are completely optional practice. Starter code for questions 10 through 13 is in lab02_extra.py. It is recommended that you complete these problems on your own time.

Note: For all WWPP questions, input Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing happens.

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. 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 objects such as numbers, booleans, strings, we usually:

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

Question 1: WWPP: Lambda the Free

Use OK to test your knowledge with the following "What Would Python Print?" questions:

python3 ok -q lambda -u

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

>>> lambda x: x # Can we access this function?

______
<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') # When is the body of this function run?

______
# Nothing gets printed by the interpreter

>>> c = b(4, 'dog')

______
summer

>>> print(c)

______
None

Question 2: Lambda the Environment Diagram

Try drawing an environment diagram for the following code and predict what Python will output.

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

Question 3: 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 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
    >>> x = lambda_curry2(add)
    >>> y = x(3)
    >>> y(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

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.

Question 4: WWPP: Higher Order Functions

Use OK to test your knowledge with the following "What Would Python Print?" questions:

python3 ok -q hof -u

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

>>> def first(x):
...     x += 8
...     def second(y):
...         print('second')
...         return x + y
...     print('first')
...     return second
>>> f = first(15)

______
first

>>> f

______
<function ...>

>>> f(16)

______
second
39
>>> 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

Question 5: Adder Function

Write a function that takes in two functions, f1 and f2, and returns another function that takes in a single argument x. The returned function should compute f1(x) + f2(x). You can assume both f1 and f2 take in one argument, and their result can be added together.

def adder(f1, f2):
    """
    Return a function that takes in a single variable x, and returns
    f1(x) + f2(x). You can assume the result of f1(x) and f2(x) can be
    added together, and they both take in one argument.

    >>> identity = lambda x: x       # returns input
    >>> square = lambda x: x**2
    >>> a1 = adder(identity, square) # x + x^2
    >>> a1(4)
    20
    >>> a2 = adder(a1, identity)     # (x + x^2) + x
    >>> a2(4)
    24
    >>> a2(5)
    35
    >>> a3 = adder(a1, a2)           # (x + x^2) + (x + x^2 + x)
    >>> a3(4)
    44
    """

    "*** YOUR CODE HERE ***"

    "*** YOUR CODE HERE ***"
    return lambda x: f1(x) + f2(x)

Use OK to test your code:

python3 ok -q adder

Recursion

A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have three important components:

  1. Base case(s), the simplest possible form of the problem you're trying to solve.
  2. Recursive case(s), where the function calls itself with a simpler argument as part of the computation.
  3. Using the recursive calls to solve the full problem.

Let's look at the canonical example, factorial:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

We know by its definition that 0! is 1. So we choose n = 0 as our base case. The recursive step also follows from the definition of factorial, i.e. n! = n * (n-1)!.

The next few questions in lab will have you writing recursive functions. Here are some general tips:

  • Consider how you can solve the current problem using the solution to a simpler version of the problem. Remember to trust the recursion: assume that your solution to the simpler problem works correctly without worrying about how.
  • Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recursive solutions fail).
  • It may help to write the iterative version first.

Debugging Marathon

Question 6: Common Misconception

Find the bug in the following recursive function.

def factorial(n):
    """Return n * (n - 1) * (n - 2) * ... * 1.

    >>> factorial(5)
    120
    """
    if n == 0:
        return 1
    else:
        n * factorial(n-1)

You can unlock this question by:

python3 ok -q factorial_ok -u

The result of the recursive calls is not returned.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Question 7: Common Misconception

Find the bug with this recursive function.

def skip_mul(n):
    """Return the product of n * (n - 2) * (n - 4) * ...

    >>> skip_mul(5) # 5 * 3 * 1
    15
    >>> skip_mul(8) # 8 * 6 * 4 * 2  * 0
    0
    """
    if n == 0:
        return 0
    else:
        return n * skip_mul(n - 2)

You can unlock this question by:

python3 ok -q skip_mul_ok -u

Once you unlock the question, fix the code in lab02.py, and run:

python3 ok -q skip_mul

Consider what happens when we choose an odd number for n. skip_mul(3) will return 3 * skip_mul(1). skip_mul(1) will return 1 * skip_mul(-1). You may see the problem now. Since we are decreasing n by two at a time, we've completed missed our base case of n == 0, and we will end up recursing indefinitely. We need to add another base case to make sure this doesn't happen.

def skip_mul(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return n * skip_mul(n - 2)

Question 8: Common Misconception

Find the bugs with the following recursive functions.

def count_up(n):
    """Print out all numbers up to and including n in ascending order.

    >>> count_up(5)
    1
    2
    3
    4
    5
    """
    i = 1
    if i == n:
        return
    print(i)
    i += 1
    count_up(n-1)

def count_up(n):
    """Print out all numbers up to and including n in ascending order.

    >>> count_up(5)
    1
    2
    3
    4
    5
    """
    i = 1
    if i > n:
        return
    print(i)
    i += 1
    count_up(n)

You can unlock this question by:

python3 ok -q count_up_ok -u

Once you unlock the question, finish the function in lab02.py, and run:

python3 ok -q count_up

Hint: You need a helper function to make the recursive calls with.

def count_up(n):
    """Print out all numbers up to and including n in ascending order.

    >>> count_up(5)
    1
    2
    3
    4
    5
    """
    def counter(i):

        "*** YOUR CODE HERE ***"

        if i <= n:
            print(i)
            counter(i + 1)
    counter(1)

Question 9: GCD

The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 B.C., realized that the greatest common divisor of a and b is one of the following:

  • the smaller value if it evenly divides the larger value, OR
  • the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value

In other words, if a is greater than b and a is not divisible by b, then

gcd(a, b) == gcd(b, a % b)

Write the gcd function recursively using Euclid's algorithm.

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """

    "*** YOUR CODE HERE ***"

    a, b = max(a, b), min(a, b)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

# Iterative solution, if you're curious
def gcd_iter(a, b):
    """Returns the greatest common divisor of a and b, using iteration.

    >>> gcd_iter(34, 19)
    1
    >>> gcd_iter(39, 91)
    13
    >>> gcd_iter(20, 30)
    10
    >>> gcd_iter(40, 40)
    40
    """
    if a < b:
        return gcd_iter(b, a)
    while a > b and not a % b == 0:
        a, b = b, a % b
    return b

Use OK to test your code:

python3 ok -q gcd

Coding Practice

It's ok if you don't finish these questions during lab. However, we strongly encourage you to try them out on your own time for extra practice.

Note: The following questions are in lab02_extra.py.

Question 10: Hailstone

For the hailstone function from homework 1, you pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Write a recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

def hailstone(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """

    "*** YOUR CODE HERE ***"

    print(n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + hailstone(n // 2)
    else:
        return 1 + hailstone(3 * n + 1)

Use OK to test your code:

python3 ok -q hailstone

Question 11: 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):
    """
    >>> 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

Question 12: 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 the 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

Question 13: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.)

grid

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """

    "*** YOUR CODE HERE ***"

    if m == 1 or n == 1:
        return 1
    return paths(m - 1, n) + paths(m, n - 1)

Use OK to test your code:

python3 ok -q paths