Posted onApr 22, 2020 • Edited onApr 30 • Originally published atromanliutikov.com

Understanding Transducers in JavaScript

#javascript #clojure #clojurescript #transducers

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 asloop fusion orstream 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);

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

Instead we want something like this:

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

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]

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

constmapIncReducer=(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]

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

constmapReducer=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]

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]

filter implementation using reduce:

constfilterEvenReducer=(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]

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

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

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]

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]

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

constmapReducer=f=>(result,input)=>result.concat(f(input));constfilterReducer=(predicate)=>(result,input)=>predicate(input)?result.concat(input):result;

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

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

constmapping=f=>reducing=>(result,input)=>reducing(result,f(input));constfiltering=predicate=>reducing=>(result,input)=>predicate(input)?reducing(result,input):result;

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]

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]

Composition of reducers has the exact same type:

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

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]

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

constxform=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]

More complex example:

constsquare=x=>x*x;constisEven=x=>x%2===0;constinc=x=>x+1;constxform=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]

Finally let’s wrap it into transduce function:

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

Final usage example:

constxform=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

Check outtransducers-js library for a complete and performant transducers implementation in JavaScript. Read aboutTransducer 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 atClojureScript.