The Case for Transducers

It is often said that functional programming has a negative impact on memory usage. Transducers address that issue.

Photo by Patrick Hendry on Unsplash

The map, filter and reduce functions are well-known array methods in JavaScript, widely used in functional programming. One can chain them easily, significantly adding to the developer experience.

However, each operation creates an intermediary array. This is not an issue for most applications that don’t require performance optimisation but can become a serious limitation for large arrays —think thousands, or worse: millions of values.

The following example illustrates this, with additional types that will help for the next to come sections of this article:

In addition to the initial array ([0, 1, 2, 3]), two intermediary arrays have been created during the process: [1, 2, 3, 4] and [2, 4].

One could wish for a tool that maps, filters and sums each value of the initial array one after the other, like:

Initial array -> increment -> isEven -> sum
0             -> 1         ->        -> 0
1             -> 2         -> 2      -> 2
2             -> 3         ->        -> 2
3             -> 4         -> 4      -> 6

This tool is called a transducer. For the sake of precision, in this example, the transducer is map piped with filter and is used with the sum reducer. More on that later.

Initial array -> transducer -> sum
0             ->            -> 0
1             -> 2          -> 2
2             ->            -> 2
3             -> 4          -> 6

So, a transducer is a function that transforms a reducer into another reducer, opening the doors of composition:

reducer: (accumulator, current) -> accumulator
transducer: reducer -> reducer

Map and filter as transducers, allowing composition

Our objective is compose map and filter operations, which requires these methods to be rewritten as transducers. Let’s begin with map:

map: fn -> reducer -> reducer

array.map(increment) is now rewritten as array.reduce(map(increment)(identity), []). That’s much progress and might sound complicated, so let’s take steps one after the other:

• identity: as per its name, that is a reducer that accumulates an array’s values into a new array. Hence the result equals the array itself: [0, 1, 2, 3].reduce(identity); // [0, 1, 2, 3]
• map(increment) is a transducer. As such, it transforms a reducer (identity) into a new reducer, applying the increment function meanwhile.

This, alone, would be much work for no benefit. But this will make sense once the filter method is prepared in the same manner:

filter: fn -> reducer -> reducer

Again, array.filter(isEven) is rewritten as array.reduce(filter(isEven)(identity), []), with the same reasoning as previously.

And this finally makes sense (hopefully), since we are now able to compose map and filter rewritten as transducers:

Quite powerful, isn’t it?

Even more powerful, I should say, since we can provide this transducer with other initial reducers:

sum:

count:

What a journey, huh? But there’s more!

Transducers x Iterables

So far, we have worked with arrays, whose length is finite. E.g. [0, 1, 2, 3]. What about working with “infinite” objects, like Observables or Iterables?

Let’s consider an iterable built upon a generator of natural numbers:

We’d like the previously built transducer to be used with this iterable. For that, we need a reduce function, and it’s up to us to define what this means.

Roughly simplified, the Array.reduce function has the following signature (simplified because in the specification, the reducer accepts additional arguments, an index and the array itself):

Array<U>.reduce(reducer: ReducerFunction<U, R>, seed: R): R

Inspired by this signature, we could define a reduce function that, instead of returning a raw value R, returns a new Iterable<R>. This would make sense especially for infinite iterables, for which a reduce operation should take into consideration all the values produced “up to now”, without an end:

Iterable<U>.reduce(reducer: ReducerFunction<U, R>, seed: R): Iterable<R>

Let’s call IterableAndReducible an Iterable that is also a Reducible (i.e. exposes a reduce function):

This work on the native Iterable type allows reusing the reducers and transducers previously built for arrays. Great! The same applies for Observables with the scan method in RxJS. The takeaway is: as long as a data structure exposes a reduce function, reducers and transducers can be used!

Further readings

• https://medium.com/javascript-scene/transducers-efficient-data-processing-pipelines-in-javascript-7985330fe73d (Transducers, by Eric Elliott)
• https://medium.com/@dtipson/javascript-transducers-2-stateful-gateful-1faa1b01ae50 (stateful transducers)
• https://github.com/mathieueveillard/transducers

More content at plainenglish.io. Sign up for our free weekly newsletter here.