Lab 2: Higher-Order Functions

Due at 11:59pm on 09/25/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 using ok. You may submit more than once before the deadline; only the final submission will be graded.

  • All questions for this lab are required.

Functions as Arguments

Question 1: Composing Function Arguments

def twice(f,x):
    """Apply f to the result of applying f to x"
    >>> twice(square,3)
    81
    """

    "*** YOUR CODE HERE ***"

    return f(f(x))

Use OK to test your code:

python ok -q twice --local
def apply_n(f, x, n):
    """Apply function f to x n times.

    >>> apply_n(increment, 2, 10)
    12
    """

    "*** YOUR CODE HERE ***"

    res = x
    for i in range(n):
        res = f(res)
    return res

Use OK to test your code:

python ok -q apply_n --local

Returning Functions

Question 2: Intersect

Two functions intersect at an argument x if they return equal values. Implement intersects, which takes a one-argument functions f and a value x. It returns a function that takes another function g and returns whether f and g intersect at x.

def intersects(f, x):
    """Returns a function that returns whether f intersects g at x.

    >>> at_three = intersects(square, 3)
    >>> at_three(triple) # triple(3) == square(3)
    True
    >>> at_three(increment)
    False
    >>> at_one = intersects(identity, 1)
    >>> at_one(square)
    True
    >>> at_one(triple)
    False
    """

    "*** YOUR CODE HERE ***"

    def at_x(g):
        return f(x) == g(x)
    return at_x

Use OK to test your code:

python ok -q intersects --local

Question 3: Piecewise

Implement piecewise, which takes two one-argument functions, f and g, along with a number b. It returns a new function that takes a number x and returns either f(x) if x is less than b, or g(x) if x is greater than or equal to b.

def piecewise(f, g, b):
    """Returns the piecewise function h where:

    h(x) = f(x) if x < b,
           g(x) otherwise

    >>> def negate(x):
    ...     return -x
    >>> abs_value = piecewise(negate, identity, 0)
    >>> abs_value(6)
    6
    >>> abs_value(-1)
    1
    """

    "*** YOUR CODE HERE ***"

    def h(x):
        if x < b:
            return f(x)
        return g(x)
    return h

Use OK to test your code:

python ok -q piecewise --local

Question 4: Flight of the Bumblebee

Write a function that takes in a number n and returns a function that takes in a number m which will print all numbers from 0 to m - 1 (including 0 but excluding m) 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 buzz(m):
        i = 0
        while i < m:
            if i % n == 0:
                print('Buzz!')
            else:
                print(i)
            i += 1
    return buzz

Use OK to test your code:

python ok -q make_buzzer --local

List Comprehensions, Map

List comprehensions are a compact and powerful way of creating new lists out of sequences. Let's work with them directly:

>>> [i**2 for i in [1, 2, 3, 4] if i%2 == 0]
[4, 16]

is equivalent to

>>> lst = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         lst += [i**2]
>>> lst
[4, 16]

The general syntax for a list comprehension is

[<expression> for <element> in <sequence> if <conditional>]

The syntax is designed to read like English: "Compute the expression for each element in the sequence if the conditional is true."

Question 5: Variants of map

Let's get some experience in building your own variations on map that take functions as arguments and apply them in interesting ways to sequences of data.

Let's see how to implement a basic version of map.

def map(f,s):
    return [f(x) for x in s]

As you can see, list comprehensions can be very useful for mapping. Both functinos below can be completed very concisely using list comprehensions.

Complete the function mapn that applies a function f to all the values in the sequence from 0 to n-1.

def mapn(f, n):
    """Return the list resulting from applying function f to the seguence 0 to n-1.

    >>> mapn(square,4)
    [0, 1, 4, 9]
    """

    "*** YOUR CODE HERE ***"

    return [f(x) for x in range(n)]

Use OK to test your code:

python ok -q mapn --local

Complete the function maxfun that takes two functions f and g and returns the maximum of these for each of the values from low to high-1.

def maxfun(f, g, low, high):
    """Return the list of the maximums of f and g applied to the low..high-1.

    >>> maxfun(four,square,-4,4)
    [16, 9, 4, 4, 4, 4, 4, 9]
    """

    "*** YOUR CODE HERE ***"

    return [max(f(i),g(i)) for i in range(low, high)]

Use OK to test your code:

python ok -q maxfun --local

Reduce, Accumulate

Question 6: Using aggregation function

Write the higher order function reduce which takes

  • reducer - a two-argument function that reduces elements to a single value
  • s - a sequence of values
  • base - the starting value in the reduction. This is usually the identity of the reducer
def reduce(reducer, s, base):
    """Reduce a sequence under a two-argument function starting from a base value.

    >>> reduce(add, [1,2,3,4], 0)
    10
    >>> reduce(mul, [1,2,3,4], 0)
    0
    >>> reduce(mul, [1,2,3,4], 1)
    24
    """

    "*** YOUR CODE HERE ***"

    result = base
    for x in s:
        result = reducer(result, x)
    return result

Use OK to test your code:

python ok -q reduce --local

Question 7: Accumulate

Putting some of these ideas together, we could write a general function, called accumulate, with the following signature:

accumulate(combiner, base, n, term) takes the following arguments:

  • term is a function applied to 1 through n, inclusively
  • combiner: a two-argument function that specifies how the current term is combined with the previously accumulated terms.
  • base: value that specifies what value to use to start the accumulation.

For example, accumulate(add, 11, 3, square) is

11 + square(1) + square(2) + square(3)

Implement accumulate and show how summation and product can both be defined as simple calls to accumulate:

from operator import add, mul

def accumulate(combiner, base, n, term):
    """Return the result of combining the first n terms in a sequence.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)   # 2 * 1^2 * 2^2 * 3^2
    72
    """

    "*** YOUR CODE HERE ***"

    total, k = base, 1
    while k <= n:
        total, k = combiner(term(k), total), k + 1
    return total
def summation_using_accumulate(n, term):
    """An implementation of summation using accumulate.

    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    """

    "*** YOUR CODE HERE ***"

    return accumulate(add, 0, n, term)

def product_using_accumulate(n, term):
    """An implementation of product using accumulate.

    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    """

    "*** YOUR CODE HERE ***"

    from operator import mul
    return accumulate(mul, 1, n, term)

Use OK to test your code:

python ok -q accumulate --local
python ok -q summation_using_accumulate --local
python ok -q product_using_accumulate --local