Homework 2: Higher Order Functions and Recursion

• hw02.zip

Due by 11:59pm on Tuesday, 7/3

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:

• Section 1.6
• Section 1.7

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

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
    """
    "*** YOUR CODE HERE ***"
    return 'REPLACE ME'

Use Ok to test your code:

python3 ok -q make_adder

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
    """
    "*** YOUR CODE HERE ***"

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
    """
    "*** YOUR CODE HERE ***"

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
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q product
python3 ok -q factorial

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
    "*** YOUR CODE HERE ***"

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
    """
    "*** YOUR CODE HERE ***"

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
    """
    "*** 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
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'product_using_accumulate',
    ...       ['Recursion', 'For', 'While'])
    True
    """
    "*** 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

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):
        "*** YOUR CODE HERE ***"
    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

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
    """
    "*** YOUR CODE HERE ***"

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

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 'YOUR_EXPRESSION_HERE'

Use Ok to test your code:

python3 ok -q make_anonymous_factorial