# Homework 2

*Due by 11:59pm on Monday, 9/14*

## 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. See Lab 1 for 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:

## Required questions

Several doctests refer to these one-argument functions:

```
def square(x):
return x * x
def triple(x):
return 3 * x
def identity(x):
return x
def increment(x):
return x + 1
```

### Question 1: Piecewise

Implement `piecewise`

, which takes two one-argument functions, `f`

and `g`

,
along with a number `b`

. It returns a new function that takes a number `x`

and
returns either `f(x)`

if `x`

is less than `b`

, or `g(x)`

if `x`

is greater than
or equal to `b`

.

```
def piecewise(f, g, b):
"""Returns the piecewise function h where:
h(x) = f(x) if x < b,
g(x) otherwise
>>> def negate(x):
... return -x
>>> abs_value = piecewise(negate, identity, 0)
>>> abs_value(6)
6
>>> abs_value(-1)
1
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q piecewise`

### Question 2: Product

The `summation(term, n)`

function from lecture adds up `term(1) + ... + term(n)`

Write a similar `product(n, term)`

function that returns ```
term(1) * ... *
term(n)
```

. Show how to define the
factorial function in terms of
`product`

. *Hint*: try using the `identity`

function for `factorial`

.

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

Use OK to test your code:

```
python3 ok -q product
python3 ok -q factorial
```

### Question 3: Accumulate

Show that both `summation`

and `product`

are instances of a more
general function, called `accumulate`

, with the following signature:

```
from operator import add, mul
def accumulate(combiner, base, n, term):
"""Return the result of combining the first n terms in a sequence.
>>> 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
"""
"*** YOUR CODE HERE ***"
```

`accumulate(combiner, base, n, term)`

takes the following arguments:

`term`

and`n`

: the same arguments as in`summation`

and`product`

`combiner`

: a two-argument function that specifies how the current term combined with the previously accumulated terms.`base`

: value that specifies what value to use to start the accumulation.

For example, `accumulate(add, 11, 3, square)`

is

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

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(5, square)
55
>>> summation_using_accumulate(5, triple)
45
"""
"*** 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, triple)
524880
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

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

### Question 4: Repeated

Implement `repeated(f, n)`

:

`f`

is a one-argument function that takes a number and returns another number.`n`

is a positive integer

`repeated`

returns another function that, when given an argument `x`

, will
compute `f(f(....(f(x))....))`

(apply `f`

a total `n`

times). For example,
`repeated(square, 3)(42)`

evaluates to `square(square(square(42)))`

.

```
def repeated(f, n):
"""Return the function that computes the nth application of f.
>>> add_three = repeated(increment, 3)
>>> add_three(5)
8
>>> repeated(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> repeated(square, 2)(5) # square(square(5))
625
>>> repeated(square, 4)(5) # square(square(square(square(5))))
152587890625
"""
"*** 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
```

Use OK to test your code:

`python3 ok -q repeated`

## Extra questions

Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!

### Question 5: 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)"""
"*** YOUR CODE HERE ***"
def two(f):
"""Church numeral 2: same as successor(successor(zero))"""
"*** YOUR CODE HERE ***"
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
"""
"*** YOUR CODE HERE ***"
def add_church(m, n):
"""Return the Church numeral for m + n, for Church numerals m and n.
>>> 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.
>>> four = successor(three)
>>> church_to_int(mul_church(two, three))
6
>>> church_to_int(mul_church(three, four))
12
"""
"*** YOUR CODE HERE ***"
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
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

```
python3 ok -q church_to_int
python3 ok -q add_church
python3 ok -q mul_church
python3 ok -q pow_church
```