Due by 11:59pm on Wednesday, September 24

Instructions

Download hw03.zip. Inside the archive, you will find a file called hw03.py, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment to Gradescope. 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 Gradescope. 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. This homework is out of 6 points.

Required Questions

Higher-Order Functions

Q1: Product

Write a function called product that returns the product of the first n terms of a sequence. Specifically, product takes in an integer n and term, a single-argument function that determines a sequence. (That is, term(i) gives the ith term of the sequence.) product(n, term) should return 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 an index as input and produces a 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: Funception

Implement funception, which takes in a function func1 and a number begin and returns a function func2. func2 should take a single argument, end, and apply func1 on all the numbers from begin (inclusive) up to end (exclusive) and return the product.

If begin is greater than or equal to end, the range of numbers is invalid, and func2 should return 1.

Note 1: The function returned by funception merges terms over the range [begin, end).

Note 2: If you attempt to modify begin in func2, you will get an UnboundLocalError. You're not allowed to rebind variables defined outside of our current frame! However, you can still access the value of begin in func2 and set it equal to a new variable. An example is shown below:

Unbound Local Error:

>>> def f():
...     x = 5
...     def g():
...         x += 1 # UnboundLocalError: cannot modify variable X outside current frame
...         print(x)
...     return g
...
>>> h = f()
>>> h()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in g
UnboundLocalError: local variable 'x' referenced before assignment

No Error:

>>> def f():
...     x = 5
...     def g():
...         i = x # No Error: accesses value X from parent frame, binds it to I in the current frame
...         i += 1
...         print(i)
...     return g
...
>>> h = f()
>>> h()
6

def funception(func1, begin):
    """ Takes in a function (func1) and a begin value.
    Returns a function (func2) that will find the product of
    func1 applied to the range of numbers from
    begin (inclusive) to end (exclusive)

    >>> def increment(num):
    ...     return num + 1
    >>> def double(num):
    ...     return num * 2
    >>> g1 = funception(increment, 0)
    >>> g1(3)    # increment(0) * increment(1) * increment(2) = 1 * 2 * 3 = 6
    6
    >>> g1(0)    # Returns 1 because begin >= end
    1
    >>> g1(-1)   # Returns 1 because begin >= end
    1
    >>> g2 = funception(double, 1)
    >>> g2(3)    # double(1) * double(2) = 2 * 4 = 8
    8
    >>> g2(4)    # double(1) * double(2) * double(3) = 2 * 4 * 6 = 48
    48
    >>> g3 = funception(increment, -3)
    >>> g3(-1)   # increment(-3) * increment(-2) = -2 * -1 = 2
    2
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q funception
Copy
✂️

Q3: Make Repeater

Implement the function make_repeater which takes a one-argument function f and a positive integer n. It returns a one-argument function so that make_repeater(f, n)(x) returns the value of f(f(...f(x)...)), in which f is applied n times to x. For example, make_repeater(square, 3)(5) squares 5 three times and returns 390625, just like square(square(square(5))).

def make_repeater(f, n):
    """Returns 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, 3)(5) # square(square(square(5)))
    390625
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q make_repeater
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.