Due by 9:00pm on Friday, 9/28/2018

## 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 the homework by uploading the `hw04.py` file to okpy.org. You may submit more than once before the deadline; only the final submission will be scored.

Readings: This homework relies on following references:

## Required questions

### Question 1: Coordinates

Implement a function `coords`, which takes a function, a sequence, and an upper and lower bound on output of the function. `coords` then returns a list of x, y coordinate pairs (lists) such that:

• Each pair contains `[x, fn(x)]`
• The x coordinates are the elements in the sequence
• Only pairs whose y coordinate is within the upper and lower bounds (inclusive)

See the doctests for examples.

One other thing: your answer can only be one line long. You should make use of list comprehensions!

``````def coords(fn, seq, lower, upper):
"""
>>> seq = [-4, -2, 0, 1, 3]
>>> def fn(x):
...     return x**2
>>> coords(fn, seq, 1, 9)
[[-2, 4], [1, 1], [3, 9]]
"""
return ______``````

Use OK to test your code:

``python3 ok -q coords --local``

### 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
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
"""
return ______``````

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 --local``

### 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
"""
return ______``````

Use OK to test your code:

``python3 ok -q double --local``

### 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
"""
return ______``````

Use OK to test your code:

``python3 ok -q count_cond --local``

### 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], ["Ting", 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

"""
``python3 ok -q match_and_apply --local``