DEV Community

Roman Liutikov
Roman Liutikov

Posted on

Understanding Transducers in JavaScript

I’ve found a very good article explaining Transducers. If you are familiar with Clojure, go and read it: “Understanding Transducers”. But if you are JavaScript developer and not used to read Lisp code, I’ve translated code examples from that article into JavaScript. So you can still read the article and see code examples here.

What are Transducers?

A quick noob intro: transducers are composable and efficient data transformation functions that doesn’t create intermediate collections.

In some languages this optimization is known as loop fusion or stream fusion. However transducers offer much more than that (at a cost of being purely runtime optimization).

Here’s a visualization to show the difference between chained transformations and transduced once.

Why use them?

The above visualization means that given transformations like map, filter, or basically any other operation on sequence of values, we want to compose them together and efficiently pipe every piece of data through them step by step. But the following example is not this kind of composition:



array
  .map(fn1)
  .filter(fn2)
  .reduce(fn3);


Enter fullscreen mode Exit fullscreen mode

The above example doesn’t decouple transformation from data and creates arrays on every step in the chain.

Instead we want something like this:



const transformation = compose(map(fn1), filter(fn2), reduce(fn3));
transformation(array);


Enter fullscreen mode Exit fullscreen mode

This way we can reuse the transformation and compose it with others. In order to achieve such composability these functions have to be generalized. Turns out all of them can be expressed in terms of reduce.

Code examples from the article

map and filter, and how they can be combined together:



[0, 1, 2, 3, 4, 5, 6, 7, 8, 9].map((x) => x + 1);
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].filter((x) => x % 2 === 0);
// [2, 4, 6, 8, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  .map((x) => x + 1)
  .filter((x) => x % 2 === 0);
  // [2, 4, 6, 8, 10]


Enter fullscreen mode Exit fullscreen mode

map and filter can be implemented using reduce. Here’s map implementation:



const mapIncReducer = (result, input) => result.concat(input + 1);
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9].reduce(mapIncReducer, []);
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


Enter fullscreen mode Exit fullscreen mode

Let’s extract incrementing function to allow it to be passed into reducer:



const mapReducer = f => (result, input) => result.concat(f(input));
[0, 1, 2, 3, 4, 5, 6].reduce(mapReducer((x) => x + 1), []);
// [1, 2, 3, 4, 5, 6, 7]


Enter fullscreen mode Exit fullscreen mode

More usage examples of map reducer:



[0, 1, 2, 3, 4, 5].reduce(mapReducer(x => x - 1), []);
// [-1, 0, 1, 2, 3, 4]
[0, 1, 2, 3, 4, 5].reduce(mapReducer(x => x * x), []);
// [0, 1, 4, 9, 16, 25]


Enter fullscreen mode Exit fullscreen mode

filter implementation using reduce:



const filterEvenReducer = (result, input) =>
  input % 2 === 0 ? result.concat(input) : result;
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].reduce(filterEvenReducer, []);
// [2, 4, 6, 8, 10]


Enter fullscreen mode Exit fullscreen mode

Again, extract predicate function, so it can be passed from the outside:



const filterReducer = (predicate) => (result, input) =>
  predicate(input) ? result.concat(input) : result;
[1, 2, 3, 4, 5, 6].reduce(filterReducer(x => x % 2 === 0), []);
// [2, 4, 6]


Enter fullscreen mode Exit fullscreen mode

Combine both reducers together:



[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  .reduce(mapReducer(x => x + 1), [])
  .reduce(filterReducer(x => x % 2 === 0), []);
  // [2, 4, 6, 8, 10]


Enter fullscreen mode Exit fullscreen mode

Similar to what you usually do with built-in array methods:



[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  .map(x => x + 1)
  .filter(x => x % 2 === 0);
  // [2, 4, 6, 8, 10]


Enter fullscreen mode Exit fullscreen mode

Here are both reducers again and both of them are using array concat as a reducing function:



const mapReducer = f => (result, input) => result.concat(f(input));
const filterReducer = (predicate) => (result, input) => 
  predicate(input) ? result.concat(input) : result;


Enter fullscreen mode Exit fullscreen mode

concat and + are both reducing operations, they take initial value and input, and reduce them to a single output value:



array.concat(4); // [1, 2, 3, 4]
10 + 1; // 11


Enter fullscreen mode Exit fullscreen mode

Let’s extract reducing function, so it can be also passed from the outside:



const mapping = f => reducing => (result, input) =>
  reducing(result, f(input));
const filtering = predicate => reducing => (result, input) =>
  predicate(input) ? reducing(result, input) : result;


Enter fullscreen mode Exit fullscreen mode

Here’s how reducers can be used now:



[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  .reduce(mapping(x => x + 1)((xs, x) => xs.concat(x)), [])
  .reduce(filtering(x => x % 2 === 0)((xs, x) => xs.concat(x)), []);
  // [2, 4, 6, 8, 10]


Enter fullscreen mode Exit fullscreen mode

Type signature of reducers is result, input -> result:



mapping(x => x + 1)((xs, x) => xs.concat(x))([], 1); // [2] 
mapping(x => x + 1)((xs, x) => xs.concat(x))([2], 2); // [2, 3]
filtering(x => x % 2 === 0)((xs, x) => xs.concat(x))([2, 4], 5);
// [2, 4]
filtering(x => x % 2 === 0)((xs, x) => xs.concat(x))([2, 4], 6);
// [2, 4, 6]


Enter fullscreen mode Exit fullscreen mode

Composition of reducers has the exact same type:



mapping(x => x + 1)(filtering(x => x % 2 === 0)((xs, x) =>
  xs.concat(x)));


Enter fullscreen mode Exit fullscreen mode

So it also can be used as a reducer:



[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  .reduce(mapping(x => x + 1)(filtering(x => x % 2 === 0)((xs, x) =>
    xs.concat(x))), []);
  // [2, 4, 6, 8, 10]


Enter fullscreen mode Exit fullscreen mode

Let’s use R.compose from Ramda library for better readability:



const xform = R.compose(mapping(x => x + 1),
                        filtering(x => x % 2 === 0));
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  .reduce(xform((xs, x) => xs.concat(x)), []);
  // [2, 4, 6, 8, 10]


Enter fullscreen mode Exit fullscreen mode

More complex example:



const square = x => x * x;
const isEven = x => x % 2 === 0;
const inc = x => x + 1;
const xform = R.compose(filtering(isEven),
                        filtering(x => x < 10),
                        mapping(square),
                        mapping(inc));
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  .reduce(xform((xs, x) => xs.concat(x)), []);
  // [1, 5, 17, 37, 65]


Enter fullscreen mode Exit fullscreen mode

Finally let’s wrap it into transduce function:



const transduce = (xform, reducing, initial, input) =>
  input.reduce(xform(reducing), initial);


Enter fullscreen mode Exit fullscreen mode

Final usage example:



const xform = R.compose(mapping((x) => x + 1),
                        filtering((x) => x % 2 === 0));  
transduce(
  xform,
  (xs, x) => xs.concat(x),
  [],
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
// [2, 4, 6, 8, 10]
transduce(
  xform,
  (sum, x) => sum + x,
  0,
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
// 30


Enter fullscreen mode Exit fullscreen mode

Check out transducers-js library for a complete and performant transducers implementation in JavaScript. Read about Transducer protocol which enables safe interop between libraries (like Lodash, Underscore and Immutable.js).

Transducers are a part of standard library in Clojure. Make sure to take a look at ClojureScript.

Top comments (1)

Collapse
 
prog profile image
prog

Thank you for this amazing article 🏆