Lab 02: Higher Order Functions and Environment Diagrams

Table of Contents

Deadline

By the end of this lab, you should have submitted the lab02 assignment using the command submit lab02.

This lab is due by 11:59pm on 07/01/2014.

Here is a lab02.py starter file for this lab.

Error messages

By now, you've probably seen a couple of error messages. Even though they might look intimidating, error messages are actually very helpful in debugging code. The following are some common types of errors (found at the bottom of an error message):

Using these descriptions of error messages, you should be able to get a better idea of what went wrong with your code. If you run into error messages, try to identify the problem before asking for help. You can often Google unknown error messages to see what similar mistakes others have made to help you debug your own code.

For example:

>>> square(3, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: square() takes 1 positional argument but 2 were given

Notice that the last line of the error message tells us exactly what we did wrong - we gave square 2 arguments when it only takes in 1 argument. In general, the last line is the most helpful.

Here's a link to a helpful Debugging Guide written by Albert Wu. Pay particular attention to the section called "Error Types" (the other sections are fairly involved but will be useful in the larger projects).

Environment Diagrams

Question 1: (Optional, for extra practice)

If you haven't found this gem already, tutor.composingprograms.com has a great visualization tool for environment diagrams. Post in your python code and it will generate an environment diagram you can walk through step-by-step! Use it to help you check your answers!

Try drawing environment diagrams for the following examples and predicting what Python will output:

>>> def square(x):
...     return x * x
>>> def double(x):
...     return x + x
>>> a = square(double(4))
>>> a
______
>>> x, y = 4, 3
>>> def reassign(arg1, arg2):
...     x = arg1
...     y = arg2
>>> reassign(5, 6)
>>> x
______
>>> y
______
>>> def f(x):
...     f(x)
>>> print, f = f, print
>>> a = f(4)
______
>>> a
______
>>> b = print(4)
______
>>> b
______
>>> def adder_maker(x):
...     def adder(y):
...         return x + y
...     return adder
>>> add3 = adder_maker(3)
>>> add3(4)
______
>>> sub5 = adder_maker(-5)
>>> sub5(6)
______
>>> sub5(10) == add3(2)
______

Now we'll see where environment diagrams come in really handy: Lambdas and Higher Order Functions.

Lambdas

Question 2: What would Python print?

>>> a = lambda: 5
>>> a()
______
>>> a(5)
______
>>> a()()
______
>>> b = lambda: lambda x: 3
>>> b()(15)
______

Question 3

For each of the following expressions, write functions f1, f2, f3, f4 , and f5 such that the evaluation of each expression succeeds, without causing an error. Be sure to use lambdas in your function definition instead of nested def statements. Each function should have a one line solution.

def f1():
    """
    >>> f1()
    3
    """
    "*** YOUR CODE HERE ***" 

def f2():
    """
    >>> f2()()
    3
    """
    "*** YOUR CODE HERE ***"

def f3():
    """
    >>> f3()(3)
    3
    """
    "*** YOUR CODE HERE ***"

def f4():
    """
    >>> f4()()()
    3
    """
    "*** YOUR CODE HERE ***"

def f5():
    """
    >>> f5()()(3)()
    3
    """
    "*** YOUR CODE HERE ***"
def f1():
    return 3

def f2():
    return lambda: 3

def f3():
    return lambda x: x

def f4():
    return lambda: lambda: 3

def f5():
    return lambda: lambda x: lambda: x

Environment Diagrams (Optional, for extra practice)

Try drawing environment diagrams for the following code and predicting what Python will output:

# Q1
a = lambda x : x * 2 + 1

def b(x):
    return x * y

y = 3
b(y)
_________

def c(x):
    y = a(x)
    return b(x) + a(x+y)
c(y)
_________

# Q2: This one is pretty tough. A carefully drawn environment
# diagram will be really useful.
g = lambda x: x + 3

def wow(f):
    def boom(g):
      return f(g)
    return boom

f = wow(g)
f(2)
_________
g = lambda x: x * x
f(3)
_________

Please use the online environment diagram drawer, linked at the bottom of the class webpage.

  1. 9 (for the first blank), 30 (for the second blank).
  2. 5 (for the first blank), 6 (for the second blank). Notice that the line g = lambda x: x * x doesn't change what f(3) does!

Higher Order Functions

Higher order functions are functions that take a function as an input, and/or output a function. We will be exploring many applications of higher order functions.

Question 4: What Would Python Output?

>>> def square(x):
...     return x*x
>>> def neg(f, x):
...     return -f(x)
>>> neg(square, 4)
______
>>> def even(f):
...     def odd(x):
...         if x < 0:
...             return f(-x)
...         return f(x)
...     return odd
...
>>> def identity(x):
...     return x
...
>>> triangle = even(identity)
>>> triangle(61)
______
>>> triangle(-4)
______
>>> def first(x):
...     x += 8
...     def second(y):
...         print('second')
...         return x + y
...     print('first')
...     return second
...
>>> f = first(15)
______
>>> f(16)
______
>>> def foo(x):
...     def bar(y):
...         return x + y
...     return bar
>>> boom = foo(23)
>>> boom(42)
______
>>> foo(6)(7)
______
>>> func = boom
>>> func is boom
______
>>> func = foo(23)
>>> func is boom
______
>>> def troy():
...     abed = 0
...     while abed < 10:
...         def britta():
...             return abed
...         abed += 1
...     abed = 20
...     return britta
>>> annie = troy()
>>> def shirley():
...     return annie
>>> pierce = shirley()
>>> pierce()
______

Question 5: Flight of the Bumblebee

Write a function that takes in a number n and returns a function that takes in a number range which will print all numbers from 0 to range (including 0 but excluding range) but print Buzz! instead for all the numbers that are divisible by n.

def make_buzzer(n):
    """ Returns a function that prints numbers in a specified
    range except those divisible by n.

    >>> i_hate_fives = make_buzzer(5)
    >>> i_hate_fives(10)
    Buzz!
    1
    2
    3
    4
    Buzz!
    6
    7
    8
    9
    """
    "*** YOUR CODE HERE ***"
def make_buzzer(n):
    def buzz(m):
        i = 0
        while i < m:
            if i % n == 0:
                print('Buzz!')
            else:
                print(i)
            i += 1
    return buzz

Question 6: I heard you liked functions so I put functions in your 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:

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 cycle(f1, f2, f3):
    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

Question 7: Higher Order Functions and Linked Lists!

Write a function that takes in a linked list lst of numbers and returns the sum of the elements in the linked list.

def sum_linked_list(lst, term):
    """ Applies a function TERM to each number in LST and returns the sum
    of the resulting values

    >>> square = lambda x: x*x
    >>> double = lambda y: 2*y
    >>> lst1 = link(1, link(2, link(3, link(4, empty))))    
    >>> sum_linked_list(lst1, square)
    30
    >>> lst2 = link(3, link(5, link(4, link(10, empty))))
    >>> sum_linked_list(lst2, double)
    44
    """
    "*** YOUR CODE HERE ***"
Recursive solution:
def sum_linked_list(lst, term):
    if lst == empty:
        return 0
    return term(first(lst)) + sum_linked_list(rest(lst), term)

Iterative solution:

def sum_linked_list(lst, term):
    sum = 0
    while lst != empty:
        sum += term(first(lst))
        lst = rest(lst)
    return sum

If you have extra time, go back to the environment diagram problems in Questions 1 and 2 to get some extra practice.