1 Task

Early in the days of “Big Data” the MapReduce programming model became quite popular. The core of this model is two functions, map and reduce, which you will write in this assignment.

Write a file named map_reduce.py that implements two functions:

1.1 mymap(func, lst)

Given a single-argument function and a list, return a list containing the result of applying that function to each element of that list. For example, mymap(abs, [3,-1,4,-1,5,-9]) should return [3, 1, 4, 1, 5, 9].

1.2 myreduce(func, lst)

Given a two-argument function and a list, return the result of using the function repeatedly to combine all elements of the list into a single value. For example, myreduce(pow, [3,-1,4,1,-5]) should compute pow(pow(pow(pow(3, -1), 4), 1), -5) and return 3486784401.0.

1.3 Restrictions

There are several full or partial implemenations of map and reduce in Python already; since this is a programming exercise, you may not use them. Do not import anything. Do not use the built-in function map. Do not use list comprehensions (you likely don’t even know what those are, but if you do, don’t use them).

Neither of your functions (nor the file itself) should print anything nor ask for any input.

In addition to functional correctness, some points will be reserved for

  1. having good variable names
  2. having meaningful docstrings for all functions you write

2 Example Invocations

When you run map_reduce.py, nothing should happen. It defines a function, it does not run it.

If in another file (which you do not submit) you write the following:

import map_reduce

def wiggle(a,b):
    a, b = abs(a), abs(b)
    if a > b:
        a,b = b,a
    c = b % a
    if c == 0:
        return a + b
    return c
def waggle(a):
    if a < 0:
        return -2*a
    else:
        return 2*a+1
x = [3, -1, 4, -1, 5, -9, 2, -6, 5, -3, 5]

print(map_reduce.myreduce(wiggle, x))
print(map_reduce.mymap(waggle, x))
print(map_reduce.myreduce(wiggle, map_reduce.mymap(waggle, x)))
print(x)

you should get the following output:

6
[7, 2, 9, 2, 11, 18, 5, 12, 11, 6, 11]
12
[3, -1, 4, -1, 5, -9, 2, -6, 5, -3, 5]

3 Troubleshooting

Although our example invocation uses custom functions, it might be easier to test using the abs and pow examples in the function descriptions.

Particularly for myreduce, but likely also for mymap, you’ll want to test smaller examples than we have first. What’s myreduce(pow, [2,3]), for example? How about myreduce(pow, [2,3,4])?