Due by 5pm on Friday, 9/7.
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) 576 """ "*** YOUR CODE HERE ***" def factorial(n): """Return n factorial by calling product. >>> factorial(4) 24 """ "*** 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) 30 """ "*** YOUR CODE HERE ***" def product_using_accumulate(n, term): """An implementation of product using accumulate. >>> product_using_accumulate(4, square) 576 """ "*** 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) 16 """ "*** 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) 625 >>> repeated(square, 4)(5) 152587890625 """ "*** 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. 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: "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.