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);
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);
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:
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]
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]
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:
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]
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]
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:
const mapReducer = f => (result, input) => result.concat(f(input));
const filterReducer = (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:
const mapping = f => reducing => (result, input) =>
reducing(result, f(input));
const filtering = 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:
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]
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]
Finally let’s wrap it into transduce function:
const transduce = (xform, reducing, initial, input) =>
input.reduce(xform(reducing), initial);
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
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)
Thank you for this amazing article 🏆