# Homework 4

*Due at 11:59:59 pm on Sunday, March 1.*

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

## MapReduce

We wrote the recursive version of the function `map`

in lecture. Here it is again:

`map`

takes

- m - a one-argument function that you want to map onto each element in the list.
- s - a sequence of values

```
def map(f, s):
"""
Map a function f onto a sequence.
>>> def double(x):
... return x * 2
>>> def square(x):
... return x ** 2
>>> def toLetter(x):
... alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
... return alpha[x%26]
>>> map(double, [1,2,3,4])
[2, 4, 6, 8]
>>> map(square, [1, 2, 3, 4, 5, 10])
[1, 4, 9, 16, 25, 100]
>>> map(toLetter, [3, 0, 19, 0])
['d', 'a', 't', 'a']
"""
if s == []:
return s
return [f(s[0])] + map(f, s[1:])
```

### Question 1: Filter

Write the recursive version of the function `filter`

which takes

- filter - a one-argument function that returns True if the argument passed in should be included in the list, and False otherwise.
- s - a sequence of values

```
def filter(f, s):
"""Filter a sequence to only contain values allowed by filter.
>>> def is_even(x):
... return x % 2 == 0
>>> def divisible_by5(x):
... return x % 5 == 0
>>> filter(is_even, [1,2,3,4])
[2, 4]
>>> filter(divisible_by5, [1, 4, 9, 16, 25, 100])
[25, 100]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q filter`

### Question 2: Reduce

Write the recursive version of the function `reduce`

which takes

- reducer - a two-argument function that reduces elements to a single value
- s - a sequence of values
- base - the starting value in the reduction. This is usually the identity of the reducer

If you're feeling stuck, think about the parameters of `reduce`

.

```
from operator import add, mul
def reduce(reducer, s, base):
"""Reduce a sequence under a two-argument function starting from a base value.
>>> def add(x, y):
... return x + y
>>> def mul(x, y):
... return x*y
>>> reduce(add, [1,2,3,4], 0)
10
>>> reduce(mul, [1,2,3,4], 0)
0
>>> reduce(mul, [1,2,3,4], 1)
24
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q reduce`

## Lambdas and HOF

### Question 3: Lambdas and Currying

We can transform multiple-argument functions into a chain of single-argument, higher order functions by taking advantage of lambda expressions. This is useful when dealing with functions that take only single-argument functions. We will see some examples of these later on.

Write a function `lambda_curry2`

that will curry any two argument
function using lambdas. See the doctest if you're not sure what this
means.

```
def lambda_curry2(func):
"""
Returns a Curried version of a two argument function func.
>>> from operator import add
>>> x = lambda_curry2(add)
>>> y = x(3)
>>> y(5)
8
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q lambda_curry2`

### Question 4: Polynomial

A polynomial function is a function with coefficients, variables and constants. A polynomial function is said to be the nth degree polynomial if there is a term in the function with the variable to the nth degree. For example, a 4th degree polynomial must contain the term x^4 with some coefficient multiplied to it.

Complete the function `polynomial`

, which takes in a degree and a list of coefficients. The function should output the corresponding polynomial function.

Hint: the staff solutions is one line and uses lambda + a list comprehension.

```
def polynomial(degree, coeffs):
"""
>>> fourth = polynomial(4, [3,6,2,1, 100])
>>> fourth(3) # 3*(3**4) + 6*(3**3) + 2*(3**2) + 1*(3**1) + 100
526
>>> third = polynomial(3, [2, 0, 0, 0])
>>> third(4) # 2*(4**3) + 0*(4**2) + 0*(4**1) + 0
128
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q polynomial`

## Optional questions

### Question 5: Compare Lambda

Write a function that returns a subtraction `lambda`

function or addition `lambda`

function depending on the operator passed into compare `lambda`

. Both `lambda`

functions take in two arguments.

```
def comparelambda(op):
"""
Write a function that returns a subtraction lambda function or addition lambda function depending on the operator passed into compare lambda.
Both lambda functions take in two arguments.
>>>adding = comparelambda("+")
>>>adding(3,2)
5
>>>subtracting = comparelambda("-")
>>>subtracting(6,2)
4
>>>operator_not_supported = comparelambda("*")
>>>operator_not_supported(2,3)
"Remember to only use + or -!"
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q comparelambda.py`

### Question 6: Higher Order Lambdas

Return a lambda function that takes in a multiplier and returns a lambda function that given an input will return the input multiplied by the multiplier.

```
def higher_order_lambdas():
"""
Return a lambda function that takes in a multiplier and returns a lambda function that given an input will
return the input multiplied by the multiplier
>>>hol = higher_order_lambdas():
>>>doubles = hol(2)
>>>doubles(3)
6
>>>hol = higher_order_lambdas():
>>>triples = hol(3)
>>>triples(4)
12
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q higher_order_lambdas.py`

### Question 7: Decimal

Write the recursive version of the function `decimal`

which takes in `n`

, a number, and returns a list representing the decimal representation of the number.

```
def decimal(n):
"""Return a list representing the decimal representation of a number.
>>> decimal(55055)
[5, 5, 0, 5, 5]
>>> decimal(-136)
['-', 1, 3, 6]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q decimal`

### Question 8: Binary

Write the recursive version of the function `binary`

which takes in `n`

, a number, and returns a list representing the representation of the number in base 2.

```
def binary(n):
"""Return a list representing the representation of a number in base 2.
>>> binary(55055)
[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
>>> binary(-136)
['-', 1, 0, 0, 0, 1, 0, 0, 0]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q binary`