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)] + 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):
return [s] + 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.

...     return x + y
>>> def mul(x, y):
...     return x*y
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)
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.
>>> 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.

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