Due by 11:59pm on Thursday, July 7

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

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

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: Product

Write a function called product that returns term(1) * ... * term(n).

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 to produce the term

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

Use Ok to test your code:

python3 ok -q product
Copy
✂️

Q2: Accumulate

Let's take a look at how product is an instance of a more general function called accumulate, which we would like to implement:

def accumulate(merger, start, n, term):
    """Return the result of merging the first n terms in a sequence and start.
    The terms to be merged are term(1), term(2), ..., term(n). merger 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
    >>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    >>> # ((2 * 1^2 * 2) * 2^2 * 2) * 3^2 * 2
    >>> accumulate(lambda x, y: 2 * x * y, 2, 3, square)
    576
    >>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
    16
    """
    "*** YOUR CODE HERE ***"

accumulate has the following parameters:

• term and n: the same parameters as in product
• merger: a two-argument function that specifies how the current term is merged with the previously accumulated terms.
• start: 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 merger is commutative. That is, merger(a, b) == merger(b, a) for all a, b, and c. However, you may not assume merger 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 function calls to accumulate.

Important: You should have a single line of code (which should be a return statement) in each of your implementations for summation_using_accumulate and product_using_accumulate, which the syntax check will check for.

def summation_using_accumulate(n, term):
    """Returns the sum: term(0) + ... + term(n), using accumulate.

    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    >>> # You aren't expected to understand the code of this test.
    >>> # Check that the bodies of the functions are just return statements.
    >>> # If this errors, make sure you have removed the "***YOUR CODE HERE***".
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    "*** YOUR CODE HERE ***"

def product_using_accumulate(n, term):
    """Returns the product: term(1) * ... * term(n), using accumulate.

    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    >>> # You aren't expected to understand the code of this test.
    >>> # Check that the bodies of the functions are just return statements.
    >>> # If this errors, make sure you have removed the "***YOUR CODE HERE***".
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    "*** 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
Copy
✂️

Q3: Filtered Accumulate

Extend the accumulate function from the previous question to allow for filtering the results produced by its term argument by filling in the implementation for the filtered_accumulate function:

def filtered_accumulate(merger, start, cond, n, term):
    """Return the result of merging the terms in a sequence of N terms
    that satisfy the condition cond. merger is a two-argument function.
    If v1, v2, ..., vk are the values in term(1), term(2), ..., term(N)
    that satisfy cond, then the result is
         start merger v1 merger v2 ... merger vk
    (treating merger 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
    >>> # ban iteration and recursion
    >>> check(HW_SOURCE_FILE, 'filtered_accumulate', ['While', 'For', 'Recursion'])
    True
    """
    def merge_if(x, y):
        "*** YOUR CODE HERE ***"
    return accumulate(merge_if, start, n, term)

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

def greater_than_5(x):
    return x > 5

filtered_accumulate has the following parameters:

• merger, start, n and term: the same arguments as accumulate.
• cond: a one-argument function applied to the values of term(k) for each k from 1 to n. Only values for which cond returns a true value are included in the accumulated total. If no values satisfy cond, then start 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 merge_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 merger in your solution to accumulate matters here.

Use Ok to test your code:

python3 ok -q filtered_accumulate
Copy
✂️

Q4: Funception

Write a function (funception) that takes in another function func_a and a number start and returns a function (func_b) that will have one parameter to take in the stop value. func_b should take the following into consideration the following in order:

1. Takes in the stop value.
2. If the value of start is less than 0, exit the function by returning None.
3. If the value of start is greater than stop, apply func_a on start and return the result.
4. If not, apply func_a on all the numbers from start (inclusive) up to stop (exclusive) and return the product.

def funception(func_a, start):
    """ Takes in a function (function A) and a start value.
    Returns a function (function B) that will find the product of
    function A applied to the range of numbers from
    start (inclusive) to stop (exclusive)

    >>> def func_a(num):
    ...     return num + 1
    >>> func_b1 = funception(func_a, 0)
    >>> func_b1(3)    # func_a(0) * func_a(1) * func_a(2) = 1 * 2 * 3 = 6
    6
    >>> func_b2 = funception(func_a, 1)
    >>> func_b2(4)    # func_a(1) * func_a(2) * func_a(3) = 2 * 3 * 4 = 24
    24
    >>> func_b3 = funception(func_a, 3)
    >>> func_b3(2)    # Returns func_a(3) since start > stop
    4
    >>> func_b4 = funception(func_a, -2)
    >>> func_b4(-3)    # Returns None since start < 0
    >>> func_b5 = funception(func_a, -1)
    >>> func_b5(4)    # Returns None since start < 0
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q funception
Copy
✂️

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Bonus Questions

Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!

Note that exams from Spring 2020, Fall 2020, and Spring 2021 gave students access to an interpreter, so the question format may be different than other years. Regardless, the questions included remain good exam-level problems doable without access to an interpreter.

1. Fall 2019 MT1 Q3: You Again [Higher Order Functions]
2. Spring 2021 MT1 Q4: Domain on the Range [Higher Order Functions]
3. Fall 2021 MT1 Q1b: tik [Functions and Expressions]