map and reduce | Ucode

Appearance

On this page

map and reduce ​

Python has built-in functions map() and reduce().

If you've read Google's famous paper "MapReduce: Simplified Data Processing on Large Clusters" , you can grasp the concepts of map and reduce.

The map() Function ​

The map() function takes two parameters: a function and an iterable. It applies the given function to each element of the sequence and returns the results as a new iterator.

For example, suppose we have a function f(x) = x^2 and we want to apply this function to a list ([1, 2, 3, 4, 5, 6, 7, 8, 9]). We can implement it using map() as follows:

f(x) = x * x
  │
  │
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │   │
▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼
[ 1   2   3   4   5   6   7   8   9 ]
  │   │   │   │   │   │   │   │   │
  ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼   ▼
[ 1   4   9  16  25  36  49  64  81 ]

Now, let's implement this in Python:

python
def f(x):
    return x * x

r = map(f, [1, 2, 3, 4, 5, 6, 7, 8, 9])
print(list(r))

Output:

[1, 4, 9, 16, 25, 36, 49, 64, 81]

In this example, the first argument passed to map() is f, which is the function object itself. Since the result r is an iterator (which is a lazy sequence), we call the list() function to compute the entire sequence and return it as a list.

You might wonder, why use map()? Couldn't we just use a loop to compute the result?

python
L = []
for n in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
    L.append(f(n))
print(L)

This works, but can you quickly understand from the loop code that it "applies f(x) to each element of the list and generates a new list"?

Thus, map(), as a higher-order function, abstracts the operation rules. We can not only compute a simple function like ( f(x) = x^2 ) but also apply any complex function. For example, to convert all numbers in the list to strings:

python
print(list(map(str, [1, 2, 3, 4, 5, 6, 7, 8, 9])))

Output:

['1', '2', '3', '4', '5', '6', '7', '8', '9']

The reduce() Function ​

Next, let’s look at how reduce() works. reduce() takes a function and a sequence [x1, x2, x3, ...] as input. The function must accept two parameters. reduce() continuously applies the function to the accumulated result and the next element in the sequence, effectively yielding:

reduce(f, [x1, x2, x3, x4]) = f(f(f(x1, x2), x3), x4)

For example, to compute the sum of a sequence, we can use reduce() as follows:

python
from functools import reduce

def add(x, y):
    return x + y

print(reduce(add, [1, 3, 5, 7, 9]))

Output:

25

Of course, the sum can be computed directly using Python's built-in function sum(), so there’s no need to use reduce() for that.

However, if we want to transform the sequence ([1, 3, 5, 7, 9]) into the integer 13579, reduce() can be quite useful:

python
from functools import reduce

def fn(x, y):
    return x * 10 + y

print(reduce(fn, [1, 3, 5, 7, 9]))

Output:

13579

This example itself may not be particularly useful, but if we consider that strings are also sequences, we can modify the previous example and combine it with map() to create a function that converts a string to an integer:

python
from functools import reduce

def fn(x, y):
    return x * 10 + y

def char2num(s):
    digits = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
    return digits[s]

print(reduce(fn, map(char2num, '13579')))

Output:

13579

Now, we can organize this into a str2int function:

python
from functools import reduce

DIGITS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}

def str2int(s):
    def fn(x, y):
        return x * 10 + y
    def char2num(s):
        return DIGITS[s]
    return reduce(fn, map(char2num, s))

We can simplify this further using a lambda function:

python
from functools import reduce

DIGITS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}

def str2int(s):
    return reduce(lambda x, y: x * 10 + y, map(lambda s: DIGITS[s], s))

This means that if Python did not provide the int() function, you could write your own function to convert a string to an integer, and it would only take a few lines of code!

Exercises ​

  1. Use the map() function to convert user input of unformatted English names to formatted names with the first letter capitalized and the rest in lowercase. Input: ['adam', 'LISA', 'barT'], Output: ['Adam', 'Lisa', 'Bart']:
python
def normalize(name):
    pass

# Test:
L1 = ['adam', 'LISA', 'barT']
L2 = list(map(normalize, L1))
print(L2)
  1. Python’s built-in sum() function can accept a list and compute the sum. Please write a prod() function that can accept a list and use reduce() to compute the product:
python
from functools import reduce

def prod(L):
    pass

print('3 * 5 * 7 * 9 =', prod([3, 5, 7, 9]))
if prod([3, 5, 7, 9]) == 945:
    print('test passed!')
else:
    print('test failed!')
  1. Use map and reduce to create a str2float function that converts the string '123.456' into the float 123.456:
python
from functools import reduce

def str2float(s):
    pass

print('str2float(\'123.456\') =', str2float('123.456'))
if abs(str2float('123.456') - 123.456) < 0.00001:
    print('test passed!')
else:
    print('test failed!')

Summary ​

  • map() is used to apply a function to a sequence, yielding another sequence.
  • reduce() applies a function sequentially to the previous result and the next element in the sequence, producing a final result.