Transducers I: Introduction to map, filter, and reduce

Suppose you’re given a list, and you want to do some computations on it. Mostly, if not always, your computations will be one of the following three types:

• transforming each element of the list in some way

• filtering out elements of the list based on some criterion

• computing some aggregate function on the list to reduce it to a single value

These situations are so pervasive that most languages nowadays provide specific functions for these operations, namely, the map, filter, and reduce functions. Let’s examine these functions more closely.

Note: Though the following discussion is easily generalizable to all iterables, we’ll refer to all collections as lists for ease of exposition.

The map and filter functions#

Most of us are somewhat familiar with the map and filter functions, as they have become more or less standard list operations. In summary:

• The map function applies a function on each element of the list

• The filter function filters the input list according to some criterion

This is how these functions can be used in Python:

It’s actually straightforward to implement these functions:

The reduce function#

Another function that’s used to compute some aggregate value over some list is the reduce function. Let’s take a look at this function from the functools library. It takes in three parameters:

1. A reducer function is any function that takes two values and combines them into one (e.g., addition, multiplication, etc.)

2. An input list

3. An optional initializer object (if given, this is used in the first iteration as an initial value for the computation)

Here’s how the reduce function works. It starts by initializing an accumulator object with the provided initial value, or with the first element of the list if an initial value is not provided. It then iterates through the rest of the list one object at a time, using the reducer function in each iteration with the current value of the accumulator as the first parameter and the object being processed in the current iteration as the second parameter to compute the updated accumulator.

Here’s how we can use the reduce function:

Let’s go through this execution. The reduce function initializes an accumulator with the provided initial value, 10. Then, it applies the provided reducer function lambda x, y: x + y, passing the accumulator as x and the current element of the list as y, updating the accumulator in each iteration, as shown below:

1. We start with 10 as the initial value

2. Then, we get 10 + 1 = 11

3. 11 + 3 = 14

4. 14 + 4 = 18

5. 18 + 7 = 25

6. 25 + 8 = 33

7. 33 + 12 = 55

8. Finally, we get 55 + 15 = 70

It’s fairly simple to write our own implementation of the reduce function:

• In line 3, we initialize the accumulator acc with the initial value if it is provided, otherwise we initialize it with the first element of the list.

• In lines 4–5, we loop over the list, apply the reducer function on acc and the current element x of the list, and update acc with the returned value.

• Finally, in line 6 we return acc, which contains the desired result.

All you need is reduce#

If you think a bit more abstractly, you'll notice that the lists returned by the map and filter functions can be thought of as the result of a computation over the input list. That is, we've reduced the input list to the output list. This would imply that the reduce function is actually more basic, and both the map and the filter functions can be thought of as its applications.

It’s fairly straightforward to implement these functions by using just the reduce function. Let’s take a look at the map function first:

Using the empty list [] as the initial value of the accumulator, the reducer function reduces the accumulator list computed so far and concatenates it (using the + operator) with a list containing just one element func(y) (i.e., the current element y of the list with the provided function func applied on it). The final output list is built incrementally:

1. []

2. [] + [1**2] = [1]

3. [1] + [3**2] = [1, 9]

4. [1, 9] + [4**2] = [1, 9, 16]

5. [1, 9, 16] + [7**2] = [1, 9, 16, 49]

6. And so on

Similarly, we can define the filter function using reduce:

As before, taking the empty list [] as the initial value of the accumulator, the reducer function builds the final list incrementally, but this time using the provided function as the condition based on which either the list containing the current element [y] or the empty list [] is appended to the accumulator. This is how the computation goes:

1. []

2. [] + [] = [], since 1 is not even

3. [] + [] = [], since 3 is not even

4. [] + [] = [4], since 4 is even

5. [4] + [] = [4], since 7 is not even

6. [4] + [8] = [4, 8], since 8 is even

7. [4, 8] + [11] = [4, 8], since 11 is not even

8. [4, 8] + [12] = [4, 8, 12], since 12 is even

9. [4, 8, 12] + [] = [4, 8, 12], since 15 is not even

Chaining map and filter#

In many applications—for instance, in data preprocessing—we need to apply various transformations and filters on a list sequentially. As a simple example of this, consider the case where we want to first filter out even numbers and then compute squares of those numbers.

One disadvantage of chaining these operations in this way is that it produces intermediate lists. In the example given above, we don’t really need the evens list, but we need to generate it to pass it to the map function. Even if we move the call to the filter function to the call in the map function, a temporary list will still be produced. This becomes problematic, especially when we’re dealing with large lists and when there are several operations we need to chain.

To chain map and filter functions without producing intermediate lists, why can’t we simply compose the functions provided to map and filter?

The reason is that the functions provided to the map and filter functions are of different types. The functions provided to the map function are transformations, that is, they transform an element to some other element. Whereas the functions provided to the filter function are the criteria based on which an element is selected to be in the final output. The output of the functions provided to the filter function is always boolean.

Let’s look at this problem a bit more closely.

Defining a compose function#

Let’s look at how we can compose multiple functions into one. That is, given a bunch of functions,

we want to be able to compose them

so that

We can do so in a straightforward manner using the reduce function we’ve seen earlier:

The compose function returns the composed function that takes the parameter x and applies each function in the functions list. That is, with x as the initial value of the accumulator (i.e., x serving as the output of the identity function $x \mapsto x$), the reducer function takes the accumulated value val computed so far and the next function func from the list, and updates the accumulator with func(val). So, we get:

1. $x$

2. $f_1(x)$

3. $f_2(f_1(x))$

4. $f_3(f_2(f_1(x)))$

5. $\cdots$

6. $f_{n-1}(\cdots(f_3(f_2(f_1(x)))))$

7. $f_n(f_{n-1}(\cdots(f_3(f_2(f_1(x))))))$

Chaining map and filter using compose#

Let’s see how we can use this function to compose the two functions we had in our chain:

Note that the first function—the filter function lambda x: x % 2 == 0—maps the input value it receives to a boolean value, therefore the map function invoked after it gets only the boolean values to process. This is not what we want.

This will work if we have just the map functions in our chain.

But what we want is the flexibility of chaining any number of operations (of any type) in any order. This problem can be solved by transducers, which will be a topic for our next blog.

Do note that we can't compose the reducer functions used to implement the map and filter functions either, for the simple reason that a reducer requires two inputs and produces one output. Transducers will solve this problem as well. Understanding the limitations of traditional reducer functions in composing operations, we'll explore how transducers provide an innovative approach to effectively combine map, filter, and reduce functions for more efficient data processing.

If you want to learn more about how we can simplify programming using functions, these ideas are explored in a more systematic way in the functional programming paradigm. Consider taking the following courses on Educative: