# Homework 4 Solutions

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

## 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]
"""
if s == []:
return s
if f(s[0]):
return [s[0]] + filter(f, s[1:])
return filter(f, s[1:])
```

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
"""
if s == []:
return base
next_base = reducer(base, s[0])
return reduce(reducer, s[1:], next_base)
```

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
"""
return lambda arg1: lambda arg2: func(arg1, arg2)
```

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
"""
# Option 1
return lambda x: sum([coeffs[i]*(x ** (degree - i)) for i in range(degree + 1)])
# Option 2
def poly_func(x):
return sum([coeffs[i]*(x ** (degree - i)) for i in range(degree + 1)])
return poly_func
```

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 -!"
"""
if op == "-":
return lambda x,y : x - y
elif op == "+":
return lambda x,y : x + y
else:
return lambda x,y : "Remember to only use + or -!"
```

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
"""
return lambda m : lambda n : m * n
```

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]
"""
if n < 0:
return ['-'] + decimal(-1 * n)
elif n < 10:
return [n % 10]
else:
return decimal(n // 10) + [n % 10]
```

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]
"""
if n < 0:
return ['-'] + binary(-1 * n)
elif n < 2:
return [n % 2]
else:
return binary(n // 2) + [n % 2]
```

Use OK to test your code:

`python3 ok -q binary`