# Homework 4 Solutions

**Solutions:** You can find the file with solutions for all
questions here.

## 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 [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]
```

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
>>> 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
"""
g = f
while n > 1:
g = compose1(f, g)
n = n - 1
return g
# Alternates
def repeated2(f, n):
def h(x):
k = 0
while k < n:
x, k = f(x), k + 1
return x
return h
def repeated3(f, n):
return accumulate(compose1, f, n-1, lambda k: f)
```

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

There are many correct ways to implement `repeated`

. The first
solution above creates a new function in every iteration of the `while`

statement (via `compose1`

). The second solution shows that it is also
possible to implement `repeated`

by creating only a single new
function. That function repeatedly applies `f`

.

`repeated`

can also be implemented compactly using `accumulate`

, the
third solution.

### 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 repeated(f, 2)
```

Use OK to test your code:

`python3 ok -q double --local`

Note that using `compose1`

from class, the body of `double`

can also be
written as `return compose1(f, f)`

.

### 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
"""
i, count = 1, 0
while i <= n:
if condition(n, i):
count += 1
i += 1
return count
```

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
"""
def foo(num):
for pair in pairs:
if pair[0] == num:
return function(pair[1])
return None
return foo
```

Use OK to test your code:

`python3 ok -q match_and_apply --local`