Due by 5pm on Friday, 9/9
You can grab a template for this homework either by downloading the file from the calendar or by running the following command in terminal on one of the school computers
cp ~cs61a/lib/hw/hw2.py .
Readings. Chapter 1.6
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."""
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."""
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.
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."""
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."""
Your function should produce the following result:
>>> repeated(square, 2)(5) 625
Hint: You may find it convenient to use compose1 from the lecture notes.
Extra for Experts: Q5. 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.
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.