61A Homework 2

Due by 11:59pm on Wednesday, 2/6.

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

Readings. Section 1.6 of the online lecture notes.

Several doctests refer to the square function, which we define as:

def square(x):
    """Return x squared."""
    return x * x

Q1. 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)
    "*** YOUR CODE HERE ***"

def factorial(n):
    """Return n factorial by calling product.

    >>> factorial(4)
    "*** YOUR CODE HERE ***"

Q2. 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."""
    "*** 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)
    "*** YOUR CODE HERE ***"

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

    >>> product_using_accumulate(4, square)
    "*** YOUR CODE HERE ***"

Q3. 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 successor is a function that returns 1 more than its argument, then double(inc) should be a function that returns two more:

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

    f -- a function that takes one argument

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

Q4. 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)
    >>> repeated(square, 4)(5)
    "*** YOUR CODE HERE ***"

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

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

Q5. (Extra for experts) 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. Similarly, provide direct definitions of the mul and pow functions (not in terms of repeated applications of add or mul). 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)
    >>> church_to_int(one)
    >>> church_to_int(two)
    "*** 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))
    "*** 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))
    >>> church_to_int(mul_church(three, four))
    "*** YOUR CODE HERE ***"

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

    >>> three = successor(two)
    >>> church_to_int(pow_church(two, three))
    >>> church_to_int(pow_church(three, two))
    "*** 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: "Extra for Experts" problems are completely optional. You are encouraged to try these questions, but certainly don't be discouraged if you don't solve them.