61A Homework 2

Due by 11:59pm on Wednesday, 7/2

Readings: You might find the following references useful:

Submission: See the online submission instructions. We have provided a hw2.py starter file for the questions below.

Table of Contents

Question 1

The summation function from lecture is only the simplest of a vast number of similar abstractions that can be captured as higher-order functions. Write a similar product function that returns the product of the values of a function for n natural number arguments. Show how to define the factorial function in terms of product:

def product(n, term):
    """ Return the product of the first n terms in a sequence.

    term -- a function that takes one argument

    >>> product(4, square)
    576
    >>> product(3, lambda x: 2 * x)
    48
    >>> product(6, lambda x: 2)
    64
    """
    "*** YOUR CODE HERE ***"

def factorial(n):
    """ Return n factorial for n >= 0 by calling product.

    >>> factorial(4)
    24
    >>> factorial(6)
    720
    """
    "*** YOUR CODE HERE ***"

Question 2

Show that both summation and product are instances of a more general function, called accumulate, with the following signature:

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

    >>> accumulate(lambda a, b: a + b, 0, 5, lambda x: x)
    15
    >>> accumulate(pow, 2, 3, lambda x: 2)
    65536
    >>> accumulate(lambda x, y: x * y, 1, 4, lambda k: 3)
    81
    """
    "*** YOUR CODE HERE ***"

Accumulate takes as arguments the same arguments term and n as summation and product, together with a combiner function (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a start value that specifies what base value to use to start the accumulation. Implement accumulate and show how summation and product can both be defined as simple calls to accumulate:

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

    >>> summation_using_accumulate(4, square)
    30
    >>> summation_using_accumulate(4, lambda x: 2**x)
    30
    """
    "*** YOUR CODE HERE ***"

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

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

Question 3

If f is a numerical function and n is a positive integer, then we can form the nth repeated application of f, which is defined to be the function whose value at x is f(f(...(f(x))...)). For example, if f adds 1 to its argument, then the nth repeated application of f adds n. Write a function that takes as inputs a function f and a positive integer n and returns the function that computes the nth repeated application of f:

def repeated(f, n):
    """ Return the function that computes the nth application of f.

    f -- a function that takes one argument
    n -- a positive integer

    >>> repeated(square, 2)(5)
    625
    >>> repeated(square, 4)(5) # square(square(square(square(square(x)))))
    152587890625
    >>> repeated(lambda x: x + 1, 5)(309)
    314
    >>> repeated(lambda x: 2**x, 3)(2)
    65536
    """
    "*** YOUR CODE HERE ***"

def double(f):
    """ Return a function that applies f twice.

    f -- a function that takes one argument

    >>> double(square)(2)
    16
    """
    "*** YOUR CODE HERE ***"

Hint: You may find it convenient to use compose1 from the textbook:

def compose1(f, g):
    """ Return a function h, such that h(x) = f(g(x)). """
    def h(x):
        return f(g(x))
    return h

Using repeated define a function double that takes a function of one argument as an argument and returns a function that applies the original function twice. For example, if inc is a function that returns 1 more than its argument, then double(inc) should be a function that returns two more:

Question 4: Challenge Problem (optional)

The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. Here are the definitions of 0, and a function that returns 1 more than its argument:

def zero(f):
    return lambda x: x

def successor(n):
    return lambda f: lambda x: f(n(f)(x))

This representation is known as Church numerals. Define one and two directly, which are also functions. To get started, apply successor to zero. Then, give a direct definition of the add function (not in terms of repeated application of successor) over Church numerals. Finally, implement a function church_to_int that converts a church numeral argument to a regular Python int:

def one(f):
    """ Church numeral 1. """
    "*** YOUR CODE HERE ***"

def two(f):
    """ Church numeral 2. """
    "*** YOUR CODE HERE ***"

def church_to_int(n):
    """ Convert the Church numeral n to a Python integer.

    >>> church_to_int(zero)
    0
    >>> church_to_int(one)
    1
    >>> church_to_int(two)
    2
    """
    "*** YOUR CODE HERE ***"

def add_church(m, n):
    """ Return the Church numeral for m + n, for Church numerals m and n.

    >>> three = successor(two)
    >>> church_to_int(add_church(two, three))
    5
    """
    "*** YOUR CODE HERE ***"

def mul_church(m, n):
    """ Return the Church numeral for m * n, for Church numerals m and n.

    >>> three = successor(two)
    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    "*** YOUR CODE HERE ***"

It is easy to find answers to this question on the Internet. Try to solve it on your own before looking it up!

Note: "Challenge" problems are completely optional. You are encouraged to try these questions, but certainly don't be discouraged if you don't solve them.