Transducers Compose Top-to-Bottom
Transducers are composable reducers. A transducer takes a reducer and returns another reducer. Transducers compose via simple function composition. But, there is a tiny difference between function and transducer composition: functions compose bottom-to-top while transducers top-to-bottom.
This text presumes you already have at least basic knowledge of transducers and function composition.
First of all we discuss the basics: function composition.
Function composition is the process of chaining the output of a function to the input of another function. In algebra, composition of functions
(f ⋅ g)(x) = f(g(x)).
const inc = (x) => x + 1; const double = (x) => x * 2; const incAndDouble = (x) => double(inc(x)); // compound function incAndDouble(2); // 6
Of course, we can do better! Let's create a general function compose:
const compose = (...fns) => x => fns.reduceRight((y, f) => f(y), x); const incAndDouble2 = compose(double, inc); incAndDouble2(2); // 6
As you can see, the functions are applied from bottom-to-top as in the definition
(f ⋅ g)(x) = f(g(x)). It means, first
g(x) is applied and, then, the output is used as the input for
f(). If we want a composition applying from top-to-bottom, we can do it: this kind of composition is called a pipe:
const pipe = (...fns) => x => fns.reduce((y, f) => f(y), x); const incAndDouble3 = pipe(inc, double); incAndDouble3(2); // 6
Probably the most useful is the mapping transducer. Let's define it:
const map = f => step => (a, c) => step(a, f(c));
map takes two curried parameters
f is a mapping function and
step is a reducer function to calculate (reduce) the result. We can peep at it with the following code:
const testReducer = map(double)((a, c) => console.log(c)); [1,2,3].reduce(testReducer, 0); // prints 2, 4, 6 into the console
Now we can use the composite function from above:
const incAndDouble4 = compose(map(inc), map(double)); const concat = (a, c) => a.concat([c]); const incAndDoubleReducer = incAndDouble4(concat); [1,2,3].reduce(incAndDoubleReducer, ); // 4, 6, 8
If you paid attention you maybe noticed one thing. Compare these two lines:
const incAndDouble2 = compose(double, inc); const incAndDouble4 = compose(map(inc), map(double));
We didn't redefine the compose function, the result remains the same, but the order of functions for the composition is the other way around. How is this possible? Let's analyse it...
The composite function is pretty straight-forward: it takes a function from bottom-to-top, applies it (first to the init value
x) and uses the output as the input for the next function. The difference between
map(double) is, that
map(double) returns a transducer function, not a scalar value as
double does. This transducer function takes a parameter
step, which is a reducer. It means,
f(y) from the compose function is
transducer(reducer); after evaluating it we get a
step reducer function, which is then used as a new input
y for the next transducer. Well, it means those two lines above define different kinds of function:
const incAndDouble2 = compose(double, inc); // function (x) => x const incAndDouble4 = compose(map(inc), map(double)); // transducer (reducer) => reducer
Composition uses reducing in the bottom-to-top direction (
reduceRight), the result of the composition is the top-most transducer function which contains the next (to-bottom direction) transducer's result reducer (in the
step parameter). This next reducer is applied after the current reduction (mapping) is applied.
We can write this particular composition function as:
const compose = (...reducers) => initReducer => reducers.reduceRight( (previousReducer, currectTransducer) => currectTransducer(previousReducer), initReducer);
Each reducer in the composition has a reference to the previous reducer (
step). The final reduction starts with the top-most reducer which applies its functionality (mapping) and then executes the referenced reducer (
step(...)). This brings the reducing in the opposite direction (top-to-bottom) from the transducers composition (bottom-to-top).
We can break down our example execution as following:
As we can see, the result reducer applies functions in order:
concat. As expected.