Homework 2 Solutions hw02.zip

Solution Files

You can find solutions for all questions in hw02.py.

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

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
"""
return lambda k: n + k``````

Use Ok to test your code:

``python3 ok -q make_adder``

We can solve this with a nested `def` statement as follows:

``````def make_adder(n):
def inner(k):
return n + k
return inner``````

Since the solution must be a single return statement, we simply rewrite the inner function as a `lambda` expression.

Q2: Double Eights

Write a recursive function that takes in a number `n` and determines if the digits contain two adjacent `8`s. You can assume that `n` is at least a two-digit number.

Hint: See the recursion lecture for a simplified version of this problem where we use recursion to check if a number has a single `8`.

``````def double_eights(n):
""" Returns whether or not n has two digits in row that
are the number 8. Assume n has at least two digits in it.

>>> double_eights(1288)
True
>>> double_eights(880)
True
>>> double_eights(538835)
True
>>> double_eights(284682)
False
>>> double_eights(588138)
True
>>> double_eights(78)
False
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'double_eights', ['While', 'For'])
True
"""
last, second_last = n % 10, n // 10 % 10
if last == 8 and second_last == 8:
return True
elif n < 100:
return False
return double_eights(n // 10)

# Alternate solution
last, second_last = n % 10, n // 10 % 10
if n < 10:
return False
return (last == 8 and second_last == 8) or double_eights(n // 10)``````

Use Ok to test your code:

``python3 ok -q double_eights``

Q3: 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
"""
total, k = 1, 1
while k <= n:
total, k = term(k) * total, k + 1

After defining `product`, show how to define the factorial function in terms of `product`.

We've provided an `identity` function, defined with a lambda expression. You might need this to write `factorial`.

``````# The identity function, defined using a lambda expression!
identity = lambda k: k

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

>>> factorial(4)
24
>>> factorial(6)
720
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'factorial', ['Recursion', 'For', 'While'])
True
"""
return product(n, identity)``````

Use Ok to test your code:

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

The `product` function has similar structure to `summation`, but starts accumulation with the value `total=1`. Factorial is a `product` with the identity function as `term`.

Q4: Summation

Now, write a recursive implementation of `summation`, which takes a positive integer `n` and a function `term`. It applies `term` to every number from `1` to `n` including `n` and returns the sum of the results.

``````def summation(n, term):

"""Return the sum of the first n terms in the sequence defined by term.
Implement using recursion!

>>> summation(5, lambda x: x * x * x) # 1^3 + 2^3 + 3^3 + 4^3 + 5^3
225
>>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
54
>>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
62
>>> # Do not use while/for loops!
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'summation',
...       ['While', 'For'])
True
"""
assert n >= 1
if n == 1:
return term(n)
else:
return term(n) + summation(n - 1, term)
# Base case: only one item to sum, so we return that item.
# Recursive call: returns the result of summing the numbers up to n-1 using
# term. All that's missing is term applied to the current value n.``````

Use Ok to test your code:

``python3 ok -q summation``

Q5: 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
"""
total, k = base, 1
while k <= n:
total, k = combiner(total, term(k)), k + 1

# Recursive solution
def accumulate2(combiner, base, n, term):
if n == 0:
return base
return combiner(term(n), accumulate2(combiner, base, n-1, term))

# Alternative recursive solution using base to keep track of total
def accumulate3(combiner, base, n, term):
if n == 0:
return base
return accumulate3(combiner, combiner(base, term(n)), n-1, term)``````

`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. You may assume that `combiner` is commutative, i.e., `combiner(a, b) = combiner(b, a)`.
• `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``

You may use either iteration or recursion to solve this. 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
"""
return accumulate(add, 0, n, term)
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
"""
return accumulate(mul, 1, n, term)``````

Use Ok to test your code:

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

Both an iterative and recursive solution were allowed. Note that they are quite similar to the solution for summation! The main differences are:

• Abstracted away the method of combination (either `+` or `*`)
• Added in a starting base value, since product behaves poorly if we start with 0

Q6: Filtered Accumulate

Now, extend the `accumulate` function to allow for filtering the results produced by its `term` argument by filling in the implementation for the `filtered_accumulate` function:

``````def filtered_accumulate(combiner, base, pred, n, term):
"""Return the result of combining the terms in a sequence of N terms
that satisfy the predicate pred. combiner is a two-argument function.
If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
that satisfy pred, then the result is
base combiner v1 combiner v2 ... combiner vk
(treating combiner as if it were a binary operator, like +). The
implementation uses accumulate.

>>> filtered_accumulate(add, 0, lambda x: True, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
15
>>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
11
>>> filtered_accumulate(add, 0, odd, 5, identity)   # 0 + 1 + 3 + 5
9
>>> filtered_accumulate(mul, 1, greater_than_5, 5, square)  # 1 * 9 * 16 * 25
3600
>>> # Do not use while/for loops or recursion
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'filtered_accumulate',
...       ['While', 'For', 'Recursion'])
True
"""
def combine_if(x, y):
if pred(y):
return combiner(x, y)
else:
return x    return accumulate(combine_if, base, n, term)

def odd(x):
return x % 2 == 1

def greater_than_5(x):
return x > 5``````

`filtered_accumulate` has the following parameters:

• `combiner`, `base`, `term` and `n`: the same arguments as `accumulate`.
• `pred`: a one-argument predicate function applied to the values of `term(k)` for each `k` from 1 to `n`. Only values for which `pred` returns a true value are included in the accumulated total. If no values satisfy `pred`, then `base` is returned.

For example, the result of ```filtered_accumulate(add, 0, is_prime, 11, identity)``` is

``0 + 2 + 3 + 5 + 7 + 11``

for a valid definition of `is_prime`.

Implement `filtered_accumulate` by defining the `combine_if` function. Exactly what this function does is something for you to discover. Do not use any loops or make any recursive calls to `filtered_accumulate`.

Hint: The order in which you pass the arguments to `combiner` in your solution to `accumulate` matters here.

Use Ok to test your code:

``python3 ok -q filtered_accumulate``

The implementation of `filtered_accumulate` will depend on how you implemented your `accumulate`. This is because the `combine_if` function we use will always keep the first item (`x`), and conditionally join with the second item (`y`).

The idea behind this combiner goes something like this:

• `x` represents all the things we have successfully combined so far.
• If we want to include `y` in our combinations, then we return `combiner(x, y)`.
• On the other hand, if we don't want to include `y` in our combinations, then we don't want to discard our progress so far, so we will just return `x` as the "result" of combining `x` and `y`.

Q7: 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)))`. Yes, it makes sense to apply the function zero times! 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.

>>> add_three = make_repeater(increment, 3)
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)
5
"""
g = identity
while n > 0:
g = compose1(f, g)
n = n - 1
return g

# Alternative solutions
def make_repeater2(f, n):
def h(x):
k = 0
while k < n:
x, k = f(x), k + 1
return x
return h

def make_repeater3(f, n):
if n == 0:
return lambda x: x
return lambda x: f(make_repeater3(f, n - 1)(x))

def make_repeater4(f, n):
if n == 0:
return lambda x: x
return compose1(f, make_repeater4(f, n - 1))

def make_repeater5(f, n):
return accumulate(compose1, lambda x: x, n, lambda k: f)``````

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):
"""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 make_repeater``

There are many correct ways to implement `make_repeater`. The first solution above creates a new function in every iteration of the `while` statement (via `compose1`). The second solution shows that it is also possible to implement `make_repeater` by creating only a single new function. That function make_repeaterly applies `f`.

`make_repeater` can also be implemented compactly using `accumulate`, the third solution.

Extra questions

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

Q8: Anonymous factorial

The recursive factorial function can be written as a single expression by using a conditional expression.

``````>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120``````

However, this implementation relies on the fact (no pun intended) that `fact` has a name, to which we refer in the body of `fact`. To write a recursive function, we have always given it a name using a `def` or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact recursively without giving it a name!

Write an expression that computes `n` factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements). Note in particular that you are not allowed to use `make_anonymous_factorial` in your return expression. The `sub` and `mul` functions from the `operator` module are the only built-in functions required to solve this problem:

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

def make_anonymous_factorial():
"""Return the value of an expression that computes factorial.

>>> make_anonymous_factorial()(5)
120
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'make_anonymous_factorial', ['Assign', 'AugAssign', 'FunctionDef', 'Recursion'])
True
"""
return (lambda f: lambda k: f(f, k))(lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1))))``````

Use Ok to test your code:

``python3 ok -q make_anonymous_factorial``