Homework 3 Solutions

Solution Files

You can find solutions for all questions in hw03.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

Q1: Has Seven

Write a function has_seven that takes a positive integer n and returns whether n contains the digit 7. Do not use any assignment statements - use recursion instead:

def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    >>> has_seven(7)
    >>> has_seven(2734)
    >>> has_seven(2634)
    >>> has_seven(734)
    >>> has_seven(7777)
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'has_seven',
    ...       ['Assign', 'AugAssign'])
if k % 10 == 7: return True elif k < 10: return False else: return has_seven(k // 10)

Use Ok to test your code:

python3 ok -q has_seven

The equivalent iterative version of this problem might look something like this:

while n > 0:
    if n % 10 == 7:
        return True
    n = n // 10

The main idea is that we check each digit for a seven. The recursive solution is similar, except that you depend on the recursive call to check the rest of the number for a seven. All that's left is to check the last digit in the current step.

Q2: Summation

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
    >>> summation(9, lambda x: x + 1) # 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
    >>> summation(5, lambda x: 2**x) # 2^1 + 2^2 + 2^3 + 2^4 + 2^5
    >>> # Do not use while/for loops!
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'summation',
    ...       ['While', 'For'])
    assert n >= 1
if n == 1: return term(n) else: return term(n) + summation(n - 1, term)

Use Ok to test your code:

python3 ok -q summation
  • 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 the current value n.
Several doctests refer to these one-argument functions:
def square(x):
    return x * x

def identity(x):
    return x

triple = lambda x: 3 * x

increment = lambda x: x + 1

add = lambda x, y: x + y

mul = lambda x, y: x * y

Q3: Accumulate

Show that both summation and product (from Homework 2) 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
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    >>> accumulate(add, 11, 0, identity) # 11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    >>> accumulate(mul, 2, 3, square)   # 2 * 1^2 * 2^2 * 3^2
total, k = base, 1 while k <= n: total, k = combiner(total, term(k)), k + 1 return total # Recursive solution # if n == 0: # return base # else: # return combiner(term(n), accumulate(combiner, base, n-1, term)) # Recursive solution using base to keep track of total # if n == 0: # return base # else: # return accumulate(combiner, combiner(base, term(n)), n-1, term)

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. You may assume that combiner is commutative, i.e., combiner(a, b) = combiner(b, a).
  • 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):
    """Returns the sum of term(1) + ... + term(n). The implementation
    uses accumulate.

    >>> summation_using_accumulate(5, square)
    >>> summation_using_accumulate(5, triple)
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'summation_using_accumulate',
    ...       ['Recursion', 'For', 'While'])
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

Q4: Filtered Accumulate

Show how to extend the accumulate function to allow for filtering the results produced by its term argument, by implementing the filtered_accumulate function in terms of accumulate:

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
    >>> filtered_accumulate(add, 11, lambda x: False, 5, identity) # 11
    >>> filtered_accumulate(add, 0, odd, 5, identity)   # 0 + 1 + 3 + 5
    >>> filtered_accumulate(mul, 1, greater_than_5, 5, square)  # 1 * 9 * 16 * 25
    >>> # Do not use while/for loops or recursion
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'filtered_accumulate',
    ...       ['While', 'For', 'Recursion'])
    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(combiner, base, pred, n, term) takes the following arguments:

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

For example, filtered_accumulate(add, 0, is_prime, 11, identity) would be

0 + 2 + 3 + 5 + 7 + 11

for a suitable 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 write any loops or recursive calls to filtered_accumulate.

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.

Q5: 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.

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

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    >>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    >>> make_repeater(square, 2)(5) # square(square(5))
    >>> make_repeater(square, 4)(5) # square(square(square(square(5))))
    >>> make_repeater(square, 0)(5)
g = identity while n > 0: g = compose1(f, g) n = n - 1 return g # Alternatives 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): 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!

Q6: Quine

Write a one-line program that prints itself, using only the following features of the Python language:

  • Number literals
  • Assignment statements
  • String literals that can be expressed using single or double quotes
  • The arithmetic operators +, -, *, and /
  • The built-in print function
  • The built-in eval function, which evaluates a string as a Python expression
  • The built-in repr function, which returns an expression that evaluates to its argument

You can concatenate two strings by adding them together with + and repeat a string by multipying it by an integer. Semicolons can be used to separate multiple statements on the same line. E.g.,

>>> c='c';print('a');print('b' + c * 2)

Hint: Explore the relationship between single quotes, double quotes, and the repr function applied to strings.

A program that prints itself is called a Quine. Place your solution in the multi-line string named quine.

Note: No tests will be run on your solution to this problem.

Q7: 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)"""
return lambda x: f(x)
def two(f): """Church numeral 2: same as successor(successor(zero))"""
return lambda x: f(f(x))
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 n(lambda x: x + 1)(0)
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 """
return lambda f: lambda x: m(f)(n(f)(x))
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 """
return lambda f: m(n(f))
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 """
return n(m)

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

Church numerals are a way to represent non-negative integers via repeated function application. The definitions of zero, one, and two show that each numeral is a function that takes a function and repeats it a number of times on some argument x.

The church_to_int function reveals how a Church numeral can be mapped to our normal notion of non-negative integers using the increment function.

Addition of Church numerals is function composition of the functions of x, while multiplication is composition of the functions of f.