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 filterQuestion 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 reduceLambdas 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_curry2Question 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 polynomialOptional 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.pyQuestion 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.pyQuestion 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 decimalQuestion 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