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