Due by 9:00pm on Wednesday, 2/27/2019

Instructions

Download hw04.zip. Inside the archive, you will find starter files for the questions in this homework, 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 this article for more instructions on okpy and submitting assignments.

Readings: This homework relies on following references:

Required questions

Question 1: arange

Implement the function arange, which behaves just like np.arange(start, end, step) from Data 8. You only need to support positive values for step.

def arange(start, end, step=1):
    """
    arange behaves just like np.arange(start, end, step).
    You only need to support positive values for step.

    >>> arange(1, 3)
    [1, 2]
    >>> arange(0, 25, 2)
    [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
    >>> arange(999, 1231, 34)
    [999, 1033, 1067, 1101, 1135, 1169, 1203]

    """
    "*** YOUR CODE HERE ***"
    

Use OK to test your code:

python3 ok -q arange

Question 2: Repeated

Implement repeated(f, n):

  • f is a one-argument function that takes a number and returns another number.
  • n is a positive integer

repeated returns another function that, when given an argument x, will compute f(f(....(f(x))....)) (apply f a total n times). For example, repeated(square, 3)(42) evaluates to square(square(square(42))).

def repeated(f, n):
    """Return the function that computes the nth application of f.
    >>> def increment(x):
    ...     return x + 1
    >>> def square(x):
    ...     return x**2
    >>> def triple(x):
    ...     return x*3
    >>> add_three = repeated(increment, 3)
    >>> add_three(5)
    8
    >>> repeated(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    243
    >>> repeated(square, 2)(5) # square(square(5))
    625
    >>> repeated(square, 4)(5) # square(square(square(square(5))))
    152587890625
    """
    "*** YOUR CODE HERE ***"
    

Hint: You may find it convenient to use compose1 from the textbook:

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 repeated

Question 3: Double

Using repeated define a function double that takes a function of one argument as an argument and returns a function that applies the original function twice. For example, if inc is a function that returns 1 more than its argument, then double(inc) should be a function that returns two more:

def double(f):
    """ Return a function that applies f twice.

    f -- a function that takes one argument

    >>> def square(x):
    ...     return x**2
    >>> double(square)(2)
    16
    """
    "*** YOUR CODE HERE ***"
    

Use OK to test your code:

python3 ok -q double

Question 4: Count van Count

Consider the following implementations of count_factors and count_primes:

def count_factors(n):
    """Return the number of positive factors that n has."""
    i, count = 1, 0
    while i <= n:
        if n % i == 0:
            count += 1
        i += 1
    return count

def count_primes(n):
    """Return the number of prime numbers up to and including n."""
    i, count = 1, 0
    while i <= n:
        if is_prime(i):
            count += 1
        i += 1
    return count

def is_prime(n):
    return count_factors(n) == 2 # only factors are 1 and n

The implementations look quite similar! Generalize this logic by writing a function count_cond, which takes in a two-argument predicate function condition(n, i). count_cond returns a count of all the numbers from 1 to n that satisfy condition.

Note: A predicate function is a function that returns a boolean (True or False).

def count_cond(condition, n):
    """
    >>> def divisible(n, i):
    ...     return n % i == 0
    >>> count_cond(divisible, 2) # 1, 2
    2
    >>> count_cond(divisible, 4) # 1, 2, 4
    3
    >>> count_cond(divisible, 12) # 1, 2, 3, 4, 6, 12
    6

    >>> def is_prime(n, i):
    ...     return count_cond(divisible, i) == 2
    >>> count_cond(is_prime, 2) # 2
    1
    >>> count_cond(is_prime, 3) # 2, 3
    2
    >>> count_cond(is_prime, 4) # 2, 3
    2
    >>> count_cond(is_prime, 5) # 2, 3, 5
    3
    >>> count_cond(is_prime, 20) # 2, 3, 5, 7, 11, 13, 17, 19
    8
    """
    "*** YOUR CODE HERE ***"
    

Use OK to test your code:

python3 ok -q count_cond

Question 5: Match and Apply

Sometimes when we are given a dataset, we need to alter it for specific values. For example, say we have a table with one column being people's names and the other being the price they have to pay.

We can use a list of pairs for this:

[["Jessica", 5], ["Andrew", 9], ["Alex", 2], ["Amir", 11], ["John", 3], ["Lyric", 2]]

The first value in each pair is the name, the second is the price.

Now, let's say we want to give a discount to specific people. We have a discount function that we want to apply to the person's price. Now, we need a function that will only apply the discount function to specific people.

Implement match_and_apply(pairs, function):

  • pairs is a list of pairs.
  • function is some function

match_and_apply returns a function such that when the function is given an input that matches the first of a pair, returns the result of applying function to the second value in the pair.

def match_and_apply(pairs, function):
    """
    >>> pairs = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 0]]
    >>> def square(num):
    ...     return num**2
    >>> func = match_and_apply(pairs, square)
    >>> result = func(3)
    >>> result
    16
    >>> result = func(1)
    >>> result
    4
    >>> result = func(7)
    >>> result
    64
    >>> result = func(15)
    >>> print(result)
    None

    """
    "*** YOUR CODE HERE ***"
    

Use OK to test your code:

python3 ok -q match_and_apply