Lab 2: Higher-Order Functions and Lambdas

Due at 11:59pm on 09/10/2015.

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 the purpose of tracking participation, please complete at least questions 4, 5, and 6 in lab02.py. Submit using OK.
Questions 8 through 11 are completely optional practice. Starter code for questions 10 and 11 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

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 3: 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 4: This Question is so Derivative

Define a function make_derivative that returns a function: the derivative of a function f. Assuming that f is a single-variable mathematical function, its derivative will also be a single-variable function. When called with a number a, the derivative will estimate the slope of f at point (a, f(a)).

Recall that the formula for finding the derivative of f at point a is:

Derivative

where h approaches 0. We will approximate the derivative by choosing a very small value for h. The closer h is to 0, the better the estimate of the derivative will be.

def make_derivative(f, h=1e-5):
    """Returns a function that approximates the derivative of f.

    Recall that f'(a) = (f(a + h) - f(a)) / h as h approaches 0. We will
    approximate the derivative by choosing a very small value for h.

    >>> square = lambda x: x*x
    >>> derivative = make_derivative(square)
    >>> result = derivative(3)
    >>> round(result, 3) # approximately 2*3
    6.0
    """
    "*** YOUR CODE HERE ***"
    def derivative(x):
        return (f(x + h) - f(x)) / h
    return derivative

Use OK to test your code:

python3 ok -q make_derivative

Encryption and Decryption

Question 5: String Transformer

Using a lambda expression, complete the following function. Your function should only contain a return statement.

from operator import add, sub

def caesar_generator(num, op):
    """Returns a one-argument Caesar cipher function. The function should "rotate" a
    letter by an integer amount 'num' using an operation 'op' (either add or
    sub).

    You may use the provided `letter_to_num` and `num_to_letter` functions,
    which will map all lowercase letters a-z to 0-25 and all uppercase letters
    A-Z to 26-51.

    >>> letter_to_num('a')
    0
    >>> letter_to_num('c')
    2
    >>> num_to_letter(3)
    'd'

    >>> caesar2 = caesar_generator(2, add)
    >>> caesar2('a')
    'c'
    >>> brutus3 = caesar_generator(3, sub)
    >>> brutus3('d')
    'a'
    """
    "*** YOUR CODE HERE ***"
    return ______
    return lambda char: num_to_letter(op(letter_to_num(char), num))

Use OK to test your code:

python3 ok -q caesar_generator

Question 6: Encryption and Decryption Utilities

Complete the following two higher-order functions. Both functions will apply a set of functions f1, f2, and f3 to a string, except the first encrypts data and the second decrypts.

The provided looper function returns a function that will apply function f to a series of letters. For example, if f shifts a letter four times to the right, looper(f) will return a function that shifts all letters in a word, four times to the right. We have provided the code you need that uses looper.

def make_encrypter(f1, f2, f3):
    """Generates an "encrypter" that applies a specific set of encryption
    functions on the message

    >>> caesar3 = caesar_generator(3, add)
    >>> caesar2 = caesar_generator(2, add)
    >>> encrypter = make_encrypter(caesar2, mirror_letter, caesar3)
    >>> encrypter('abcd') # caesar2(mirror_letter(caesar3('a'))) -> 'y'
    'yxwv'
    """
    f1, f2, f3 = looper(f1), looper(f2), looper(f3)
    "*** YOUR CODE HERE ***"
    def encrypter(msg):
        return f1(f2(f3(msg)))
    return encrypter
def make_decrypter(f1, f2, f3):
    """Generates a "decrypter" function.

    >>> brutus3 = caesar_generator(3, sub)
    >>> brutus2 = caesar_generator(2, sub)
    >>> decrypter = make_decrypter(brutus2, mirror_letter, brutus3)
    >>> decrypter('yxwv') # brutus3(mirror_letter(brutus2('y'))) = 'a'
    'abcd'
    """
    f1, f2, f3 = looper(f1), looper(f2), looper(f3)
    "*** YOUR CODE HERE ***"
    def decrypter(msg):
        return f3(f2(f1(msg)))
    return decrypter

Use OK to test your code:

python3 ok -q make_encrypter
python3 ok -q make_decrypter

Question 7: Using our Encryption (Optional)

In this section, we will use our existing encryptors and decryptors to protect the contents of shakespeare.txt.

Use the make_encrypter and make_decrypter functions that you've just written to fill in generator in lab02_extra.py.

def generator():
    """Generates an encrypter and decrypter.

    >>> e, d = generator()
    >>> msg = 'text'
    >>> encrypted = e(msg)
    >>> encrypted != msg
    True
    >>> decrypted = d(encrypted)
    >>> decrypted == msg
    True
    """
    "*** YOUR CODE HERE ***"
    return None, None # Change this line
    caesar2 = caesar_generator(2, add)
    caesar3 = caesar_generator(3, add)
    brutus2 = caesar_generator(2, sub)
    brutus3 = caesar_generator(3, sub)
    return make_encryptor(caesar2, mirror_letter, caesar3), \
        make_decrypter(brutus2, mirror_letter, brutus3)
encryptor, decryptor = generator()

Then, run the following in your terminal

$ python3 lab02_extra.py encrypt --source shakespeare.txt --output shakespeare-encrypted.txt

To decrypt the encrypted text, run the following.

$ python3 lab02_extra.py decrypt --source shakespeare-encrypted.txt --output shakespeare-decrypted.txt

Submit your lab with python3 ok --submit.

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.

Question 8: WWPP: Community

Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok -q community -u

>>> def troy():
...     abed = 0
...     while abed < 3:
...         britta = lambda: abed
...         print(abed)
...         abed += 2
...     annie = abed
...     annie += 1
...     abed = 6 # seasons and a movie
...     return britta
>>> jeff = troy()
______
0
2
>>> shirley = lambda: jeff
>>> pierce = shirley()
>>> pierce()
______
6

Question 9: Lambda the Plentiful

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

Note: This is a challenging problem! Work together with your neighbors and see if you can arrive at the correct answer.

You can check your work with the Online Python Tutor, but try drawing it yourself first!

>>> def go(bears):
...     gob = 3
...     print(gob)
...     return lambda ears: bears(gob)
>>> gob = 4
>>> bears = go(lambda ears: gob)
______
3
>>> bears(gob)
______
4

Hint: What is the parent frame for a lambda function?

Note: The following questions are in lab02_extra.py.

Question 10: 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 cond(n, i). count_cond returns a one-argument function that counts all the numbers from 1 to n that satisfy cond.

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