# 61A Homework 2

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.

### Question 1

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

def factorial(n):
""" Return n factorial for n >= 0 by calling product.

>>> factorial(4)
24
>>> factorial(6)
720
"""

### Question 2

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

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

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

### Question 3

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

def double(f):
""" Return a function that applies f twice.

f -- a function that takes one argument

>>> double(square)(2)
16
"""

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:

### Question 4: Challenge Problem (optional)

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

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