**Due by 4pm on Monday, 1/30**

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 (the dot is significant: it denotes the current directory)

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 the sequence formed by applying term to the integers 1, ..., n. term -- a function that takes one argument """

**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 accumulation of the
preceding terms is to be combined with each value returned by term,
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.