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

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
"""
"*** YOUR CODE HERE ***"
def factorial(n):
""" Return n factorial for n >= 0 by calling product.
>>> factorial(4)
24
>>> factorial(6)
720
"""
"*** YOUR CODE HERE ***"
```

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
"""
"*** 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
>>> summation_using_accumulate(4, lambda x: 2**x)
30
"""
"*** YOUR CODE HERE ***"
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
"""
"*** YOUR CODE HERE ***"
```

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
"""
"*** YOUR CODE HERE ***"
def double(f):
""" Return a function that applies f twice.
f -- a function that takes one argument
>>> double(square)(2)
16
"""
"*** YOUR CODE HERE ***"
```

*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
```

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:

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*: "Challenge" problems are completely optional. You are
encouraged to try these questions, but certainly don't be discouraged
if you don't solve them.