Homework 4
Due at 11:59:59 pm on Friday, October 2.

Instructions

Download hw04.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

Readings: This homework relies on following references:

• Section 1.6

Lambdas

Question 1: Make your own lambdas

For each of the following expressions, write functions f1, f2, f3, and f4 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)()
    3
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q f1
python3 ok -q f2
python3 ok -q f3
python3 ok -q f4

Question 2: 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(fn):
    """
    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 ***"
    

Use OK to test your code:

python3 ok -q lambda_curry2

Higher Order Functions Review

Question 3: Reduce

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

If you're feeling stuck, think about the parameters of reduce. This is meant to be a simple problem that provides hands-on experience of understanding what reduce does.

from operator import add, mul

def reduce(reducer, s, base):
    """Reduce a sequence under a two-argument function starting from a base value.

    >>> def add(x, y):
    ...     return x + y
    >>> def mul(x, y):
    ...     return x*y
    >>> 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 ***"
    

Use OK to test your code:

python3 ok -q reduce

Question 4: 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.

    >>> identity = lambda x: x
    >>> square = lambda x: x * x
    >>> 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 ***"

def summation_using_accumulate(n, term):
    """An implementation of summation using accumulate.

    >>> square = lambda x: x * x
    >>> triple = lambda x: 3 * x
    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    """
    "*** YOUR CODE HERE ***"

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

    >>> square = lambda x: x * x
    >>> triple = lambda x: 3 * x
    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    """
    "*** YOUR CODE HERE ***"

python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate

python3 ok --submit