# Homework 2: Higher-Order Functions hw02.zip

Due by 11:59pm on Tuesday, June 30

## Instructions

Download hw02.zip. Inside the archive, you will find a file called hw02.py, along with a copy of the `ok` autograder.

Submission: When you are done, submit with ```python3 ok --submit```. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 3 points.

The `construct_check` module is used in this assignment, which defines the function `check`. For example, a call such as

``check("foo.py", "func1", ["While", "For", "Recursion"])``

checks that the function `func1` in file `foo.py` does not contain any `while` or `for` constructs, and is not an overtly recursive function (i.e., one in which a function contains a call to itself by name.) Note that this restriction does not apply to all problems in this assignment. If this restriction applies, you will see a call to `check` somewhere in the problem's doctests.

# Required questions

Several doctests refer to these functions:

``````from operator import add, mul, sub

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1``````

### Q1: Product

The `summation(n, term)` function from the higher-order functions lecture adds up `term(1) + ... + term(n)`. Write a similar function called `product` that returns `term(1) * ... * term(n)`.

``````def product(n, term):
"""Return the product of the first n terms in a sequence.
n -- a positive integer
term -- a function that takes one argument to produce the term

>>> product(3, identity)  # 1 * 2 * 3
6
>>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square)    # 1^2 * 2^2 * 3^2
36
>>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple)    # 1*3 * 2*3 * 3*3
162
"""
``````

Use Ok to test your code:

``python3 ok -q product``

### Q2: Accumulate

Let's take a look at how `summation` and `product` are instances of a more general function called `accumulate`:

``````def accumulate(combiner, base, n, term):
"""Return the result of combining the first n terms in a sequence and base.
The terms to be combined are term(1), term(2), ..., term(n).  combiner is a
two-argument commutative function.

>>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11
11
>>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square)    # 2 * 1^2 * 2^2 * 3^2
72
>>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
19
>>> accumulate(lambda x, y: 2 * (x + y), 2, 3, square)
58
>>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
16
"""
``````

`accumulate` has the following parameters:

• `term` and `n`: the same parameters as in `summation` and `product`
• `combiner`: a two-argument function that specifies how the current term is combined with the previously accumulated terms.
• `base`: value at which to start the accumulation.

For example, the result of `accumulate(add, 11, 3, square)` is

``11 + square(1) + square(2) + square(3) = 25``

Note: You may assume that `combiner` is commutative. That is, `combiner(a, b) == combiner(b, a)` for all `a`, `b`, and `c`. However, you may not assume `combiner` is chosen from a fixed function set and hard-code the solution.

After implementing `accumulate`, show how `summation` and `product` can both be defined as simple calls to `accumulate`:

``````def summation_using_accumulate(n, term):
"""Returns the sum of term(1) + ... + term(n). The implementation
uses accumulate.

>>> summation_using_accumulate(5, square)
55
>>> summation_using_accumulate(5, triple)
45
>>> from construct_check import check
>>> # ban iteration and recursion
>>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
...       ['Recursion', 'For', 'While'])
True
"""

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

>>> product_using_accumulate(4, square)
576
>>> product_using_accumulate(6, triple)
524880
>>> from construct_check import check
>>> # ban iteration and recursion
>>> check(HW_SOURCE_FILE, 'product_using_accumulate',
...       ['Recursion', 'For', 'While'])
True
"""
``````

Use Ok to test your code:

``````python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate``````

### Q3: Make Repeater

Implement the function `make_repeater` so that `make_repeater(func, n)(x)` returns `func(func(...func(x)...))`, where `func` is applied `n` times. That is, `make_repeater(func, n)` returns another function that can then be applied to another argument. For example, `make_repeater(square, 3)(42)` evaluates to `square(square(square(42)))`.

``````def make_repeater(func, n):
"""Return the function that computes the nth application of func.

8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
5
"""
``````

For an extra challenge, try defining `make_repeater` using `compose1` and your `accumulate` function in a single one-line return statement.

``````def compose1(func1, func2):
"""Return a function f, such that f(x) = func1(func2(x))."""
def f(x):
return func1(func2(x))
return f``````

Use Ok to test your code:

``python3 ok -q make_repeater``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``

# Just for fun Question

This question is out of scope for 61a. Do it if you want an extra challenge or some practice with HOF and abstraction!

### Q4: Church numerals

The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. The purpose was to show that functions are sufficient to describe all of number theory: if we have functions, we do not need to assume that numbers exist, but instead we can invent them.

Your goal in this problem is to rediscover this representation known as Church numerals. Here are the definitions of `zero`, as well as a function that returns one more than its argument:

``````def zero(f):
return lambda x: x

def successor(n):
return lambda f: lambda x: f(n(f)(x))``````

First, define functions `one` and `two` such that they have the same behavior as `successor(zero)` and `successsor(successor(zero))` respectively, but do not call `successor` in your implementation.

Next, implement a function `church_to_int` that converts a church numeral argument to a regular Python integer.

Finally, implement functions `add_church`, `mul_church`, and `pow_church` that perform addition, multiplication, and exponentiation on church numerals.

``````def one(f):
"""Church numeral 1: same as successor(zero)"""

def two(f):
"""Church numeral 2: same as successor(successor(zero))"""

three = successor(two)

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
>>> church_to_int(three)
3
"""

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

5
"""

def mul_church(m, n):
"""Return the Church numeral for m * n, for Church numerals m and n.

>>> 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 m ** n, for Church numerals m and n.

>>> church_to_int(pow_church(two, three))
8
>>> church_to_int(pow_church(three, two))
9
"""
``````python3 ok -q church_to_int