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
    """

    total, k = 1, 1
    while k <= n:
        total, k = term(k) * total, k + 1
    return total

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

    >>> factorial(4)
    24
    >>> factorial(6)
    720
    """

    return product(n, lambda k: k)

The product function has similar structure to summation, but starts accumulation wtih the value total=1. Factorial is a product with the identity function as term.

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
    """

    total, k = start, 1
    while k <= n:
        total, k = combiner(term(k), total), k + 1
    return total

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
    """

    from operator import add
    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, lambda x: 3)
    729
    """

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

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
    """

    g = f
    while n > 1:
        g = compose1(f, g)
        n = n - 1
    return g

def repeated(f, n):
    def h(x):
        k = 0
        while k < n:
            x, k = f(x), k + 1
        return x
    return h

def repeated(f, n):
    return accumulate(compose1, f, n-1, lambda k: f)

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

    f -- a function that takes one argument

    >>> double(square)(2)
    16
    """

    return repeated(f, 2)

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

There are many correct ways to implement repeated. The first solution above creates a new function in every iteration of the while statement (via compose1). The second solution shows that it is also possible to implement repeated by creating only a single new function. That function repeatedly applies f.

repeated can also be implemented compactly using accumulate, the third solution.

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:

Note that using compose1 from class, the body of double can also be written as return compose1(f, f)

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. """

    return lambda x: f(x)

def two(f):
    """ Church numeral 2. """

    return lambda x: f(f(x))

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
    """

    return n(lambda x: x + 1)(0)

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
    """

    return lambda f: lambda x: m(f)(n(f)(x))

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
    """

    return lambda f: m(n(f))

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.

Church numerals are a way to represent non-negative integers via repeated function application. The definitions of zero, one, and two show that each numeral is a function that takes a function and repeats it a number of times on some argument x.

The church_to_int function reveals how a Church numeral can be mapped to our normal notion of non-negative integers using the increment function.

Addition of Church numerals is function composition of the functions of x, while multiplication (added to the question for these solutions) is composition of the functions of f.