# 61A Homework 2

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
"""

def factorial(n):
"""Return n factorial by calling product.

>>> factorial(4)
24
"""
```

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:

```def summation_using_accumulate(n, term):
"""An implementation of summation using accumulate.

>>> summation_using_accumulate(4, square)
30
"""

def product_using_accumulate(n, term):
"""An implementation of product using accumulate.

>>> product_using_accumulate(4, square)
576
"""
```

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

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

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

def two(f):
"""Church numeral 2."""

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
"""

"""Return the Church numeral for m + n, for Church numerals m and n.

>>> three = successor(two)
5
"""

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
"""

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
"""