*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) 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. 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) 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 ***" 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)) 8 >>> church_to_int(pow_church(three, two)) 9 """ "*** 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.