# Homework 2: Higher Order Functions hw02.zip

Due by 11:59pm on Friday, 2/8

## 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 effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points.

The `construct_check` module is used in this assignment, which defines a 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.)

## 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: Make Adder with a Lambda

Implement the `make_adder` function, which takes in a number `n` and returns a function that takes in an another number `k` and returns `n + k`. Your solution must consist of a single `return` statement.

``````def make_adder(n):
"""Return a function that takes an argument K and returns N + K.

9
3
"""
``````

Use Ok to test your code:

``python3 ok -q make_adder``

### Q2: 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)`. Do not use recursion.

``````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
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple)    # 1*3 * 2*3 * 3*3
162
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'product', ['Recursion'])
True
"""
``````

Now, define the factorial function in terms of `product` in one line.

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

>>> factorial(4)  # 4 * 3 * 2 * 1
24
>>> factorial(6)  # 6 * 5 * 4 * 3 * 2 * 1
720
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'factorial', ['Recursion', 'For', 'While'])
True
"""
``````

Use Ok to test your code:

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

### Q3: 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, associative 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      #(((2 + 1^2 + 1) + 2^2 + 1) + 3^2 + 1)
"""
``````

`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 associative and commutative. That is, `combiner(a, combiner(b, c)) == combiner(combiner(a, b), c)` and `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
>>> 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
>>> 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``````

## Extra questions

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

### Q4: Make Repeater

Implement a function `make_repeater` so that `make_repeater(f, n)(x)` returns `f(f(...f(x)...))`, where `f` is applied `n` times. That is, `make_repeater(f, 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)))`. See if you can figure out a reasonable function to return for that case. You may use either loops or recursion in your implementation.

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

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(f, g):
``python3 ok -q make_repeater``