Homework 2 Solutions

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.

    >>> add_three = make_adder(3)
    >>> add_three(1) + add_three(2)
    9
    >>> make_adder(1)(2)
    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 8s. 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 return total

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 return total # 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)
    >>> add_three(5)
    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