How do I avoid looping multiple times through a list while chaining maps, and filters?

Finding the answer took me step by step to implementing transducers in JavaScript. Id like to take you on this journey so that you too can utilize this powerful abstraction. So, shall we trance?

The problem


[1, 2, 3].map(x => x + 1).filter(x => x > 3)

And This:

[1, 2, 3].reduce((a, x) => { 
let y = x + 1;
return y > 3 ? a.concat(y) : a}, [])

do the same thing. They both add 1 to each number in a list and then keep only the numbers that are greater than 3.

But deciding which one to use leads us to two important questions:

1. Which implementation is more readable?

If you are familiar with functional programming idioms then the first implementation should be much more readable. It maps very well to what we wanted the implementations to do,

…add 1 to each number in a list and then keep only the numbers that are greater than 3.

So long as you know that map transforms each item of the list by the function it is passed, and filter filters the list by the function it is passed, then the first implementation reads almost like a sentence.

The second implementation on the other hand follows a more imperative approach. When a new developer sees it they would be staring at how it does whatever it does and from that the developer would have to work out what the hell it actually does!

To be fair the second implementation is also using a functional idiom: reduce (also known as fold in some languages), but this highlights an important point that I find developers miss: just because you are using map, filter, or reduce, in your Javascript code doesn’t mean your code is as declarative as it could be!

2. How many times does the implementation loop through a list?

map, filter, and reduce each go through all of the elements in a list.

So, at least theoretically, the first implementation would go through the list twice because it uses both map and filter, and the second will only go through the list once since it only uses reduce.

Does this mean the second one has a better performance? It depends on the browser. For example these are the benchmark results when running the implementations in my Safari:

As expected we see the map & filter implementation to be slower than just using reduce. But when I ran the implementations in my Firefox:

The first implementation is faster! So as you can see, some browsers may perform optimizations on these chained functions. Perhaps overtime more browsers will adopt these optimization and we won’t have to choose between performance and readability.

But how can we guarantee that our implementation only loops once? (Promise this question will lead us down an interesting abstraction. 😏)

Well, instead of creating an intermediate list after map, we create a pipeline of transformations we want to do on a single item then iterate through the list once passing each item through the pipeline. So in our example we would go through the list only once first adding 1 as specified in the map to each item and then keeping it if it is greater than 3 as specified in filter.

Let’s start by implementing this sort of pipeline concept with an even simpler example.

Composing Chained Maps

Say we have 2 maps in a row:

[1, 2, 3].map(x => x + 1).map(x => x * 3)

Without any optimization we expect the first map to iterate over the list and return [2, 3, 4]. Then the second map to again iterate and produce [6, 9, 12]. But since we don’t care for the intermediate list, we would be just as happy if we iterate once adding 1 to each value and then multiplying it by 3.

So in other words we could create a single function that can combine x => x + 1 and x => x * 3. The term for combining functions like this where the output of one becomes the input of the next is called composition. So you could rewrite our double map into:

const add1 = x => x + 1;
const multiply3 = x => x * 3;
[1, 2, 3].map(compose(multiply3, add1));

Here you can easily see that we will be transforming each item in the list by adding 1 and then multiplying 3. Note: Compose is not native to JavaScript, but is available in several libraries and if you want to you can implement it yourself. Also in Ramda’s definition the functions are composed from right to left; hence why multiply3 is first.

The lesson here is that any chain of maps can be turned into a single map and a composition of all of the functions you want to apply passed as a single argument to that map. This could provide some performance improvements and still remain, at least in my opinion, quite readable.

But what about if we want to chain maps and filters?

Composing Chained Maps and Filters?

It would be nice if we could just add a filter function into the list of composed functions like so:

[1, 2, 3].map(compose(keepGreaterThan7, multiply3, add1))

But the problem here is map transforms each item in the list, but with filter we want to remove items from a list. In order to do that in keepGreaterThan7 we would have to transform the item into something that represents nothingness:

const keepGreaterThan7 = x => x > 7 ? x : undefined

Here we are treating the value undefined as meaning nothing. Then we would have to remove all the nothing values:

[1, 2, 3].map(compose(add1, multiply3, keepGreaterThan7))
.filter(x => x !== undefined);

Using this technique we limit the number of iterations through the list to 2 regardless of how long the chain is.

But what if we wanted to multiply3 after we keepGreaterThan7? Then we would have to make multiply3 aware that undefined means nothing so we shouldn’t operate on it. What if undefined is something meaningful? Then we need to think of another value to represent nothing. What if we want to chain a reduce too? 😖

As you can see composing the functions passed to map gets clunky quick if you want to do anything other than transform values. This is because filter cannot be derived from map. But they do have a common ancestor…

Enter the Trance-ducers…

map and filter can be defined with reduce. Just as we were able to use composition for specific uses of map, perhaps we can use composition for specific uses of reduce like map, filter, and even other things. This is where things get fun! 😼

Let’s start with looking at the definition of map, and filter in terms of reduce:

// map : add 1 to each item
[1, 2, 3].reduce((a, x) => a.concat(x + 1), []);
// filter : keep items greater than 2
[1, 2, 3].reduce((a, x) => x > 2 ? a.concat(x) : a, [])

As you can see the function passed to reduce (in bold) is the only thing different between the two. We’ll call these functions reducers. Reducers have the following method signature:

(a, x) => a

where a reducer takes as arguments:

  1. The current result a
  2. The current item x

And returns the new a (result).

OK, let’s extract just the reducers from the two reduce functions:

Hmm, well, one way we can bring the number of reduce down to one is by making filterGreaterThan2Reducer call mapAdd1Reducer whenever x > 2.

As you can see we created a chain of reducers where one reducer does it’s job on a and x and then passes them along to the next reducer.

But one issue is in filterGreaterThan2AndMapAdd1Reducer we are hard wiring filterGreaterThan2 to always be chained to mapAdd1Reducer. Let’s try to make it slightly more customize-able.

So now filterGreaterThan2Transducer let’s you choose what the next reducer in the chain is by passing it as an argument.

⏸ Wait, what’s a transducer?

A transducer is a function that returns a reducer when given as an argument the next reducer that the returned reducer should delegate to.* So in our case filterGreaterThan2Transducer(mapAdd1Reducer) returns a reducer that calls mapAdd1Reducer(x, a) only when x > 2.

Okay cool. But, what if we wanted to filter after we map? We could also turn mapAdd1Reducer into a transducer and pass in the filter as the next argument:

But then what’s filterGreaterThan2Transducer’s next reducer ?! In it’s definition, we can see the next reducer is only invoked when x > 2. In this condition we expect that the item will be added to list a; so let’s pass in a reducer that does that (a, x) => a.concat(x). Remember the reducer signature is (a, x) => a.

[1, 2, 3].reduce(
(a, x) => a.concat(x))), []);

Nice, now we can put the reducers in any order making the last one always the concat!

Also, if you notice mapAdd1Transducer() takes the reducer returned by filterGreaterThan2Transducer((a, x) => a.concat(x)) as an input. Whenever you see one function take the output of another function as an input, you can compose them:

const trance = 
compose(mapAdd1Transducer, filterGreaterThan2Transducer);

This leaves trance expecting the same input as the first function in the composition, filterGreaterThan2Transducer, which would be the next reducer after filtering. Remember the next and last reducer in the chain is (a, x) => a.concat(x). We can pass this at the call sight like this:

[1, 2, 3].reduce(trance((a, x) => a.concat(x)));

We did it! 🎉 We achieved composition across different kinds of reduces! So now we built a nice pipeline of reducers that a single item will travel through, which means we only have to loop once through the list! 👑

But let’s see if we can go one step further and make something that can create any kind of map and any kind of filter transducers, by extracting out the mapping and filtering logic:

Okay, now mapping and filtering take the logic by which they do their mapping/filtering before producing a transducer. The impact on our composition is:

const trance = compose([filtering(x => x > 2), mapping(x => x + 1)]);
[1, 2, 3].reduce(trance((a, x) => a.concat(x)), []);

Nice, right? We, more or less, maintain the declarative style of our chained filter and map, but do all of the reducer logic in one iteration.

Keep Trancin’ 🚨

The deeper point is NOT that we did it in one iteration. It’s that we were able to distill the ‘essence’ of the transformation from the input and the output. In other words we were able to separate trance from the actual reduce.

This could potentially let us use the process described by trance on other inputs besides JS arrays, as long as those structures also offer something like reduce for us. If you want to know where this road leads check out transducer-js. I also hope to expand on this in another post.

I tried to approach transducers the way I discovered them myself in hopes that it would be an approachable read. Let me know if this worked and what could have been better in the comments (or any other thoughts). If you found this post interesting drop of few 👏 Thanks! 🙏

The One Footnote

*My transducer definition is not actually the most general definition, but I think it’s easy to think of it in terms of reduce when you first start learning about it. In the words of Rich Hickey:

Transducers are a powerful and composable way to build algorithmic transformations that you can reuse in many contexts