Transducers Explained
Why?
What?
Transducers are composable algorithmic transformations.
They are independent from the context of their input and output sources and specify only the essence of the transformation in terms of an individual element.
Because transducers are decoupled from input or output sources, they can be used in many different processes - collections, streams, channels, observables, etc.
Transducers compose directly, without awareness of input or creation of intermediate aggregates.
How?
Reducing Function
function sum(result, item){
return result + item;
}
var output = [2,3,4].reduce(sum, 1);
// 10 (=1+2+3+4)
var output = arrayReduce(sum, 1, [2,3,4]);
// 10 (=1+2+3+4)
function arrayReduce(step, init, array){
// Start with an initial value
var value = init;
// Input one item at a time, passing each result
// to next iteration using reducing function
var idx = 0;
var length = array.length;
for(; idx < length; idx++){
value = step(value, array[idx]);
}
// Output last computed result
return value;
}
Reducing Function
function mult(result, item){
return result * item;
}
var output = [2,3,4].reduce(mult, 1);
// 24 (=1*2*3*4)
var output = arrayReduce(mult, 1, [2,3,4]);
// 24 (=1*2*3*4)
function arrayReduce(step, init, array){
// Start with an initial value
var value = init;
// Input one item at a time, passing each result
// to next iteration using reducing function
var idx = 0;
var length = array.length;
for(; idx < length; idx++){
value = step(value, array[idx]);
}
// Output last computed result
return value;
}
Reducing Function
function mult(result, item){
return result * item;
}
var output = [2,3,4].reduce(mult, 2);
// 48 (=2*2*3*4)
var output = arrayReduce(mult, 2, [2,3,4]);
// 48 (=2*2*3*4)
function arrayReduce(step, init, array){
// Start with an initial value
var value = init;
// Input one item at a time, passing each result
// to next iteration using reducing function
var idx = 0;
var length = array.length;
for(; idx < length; idx++){
value = step(value, array[idx]);
}
// Output last computed result
return value;
}
Transformer
var transformer = function(reducingFunction){
return {
// Start with an initial value
init: function(){
return 1;
},
// Input one item at a time, passing each result
// to next iteration using reducing function
step: reducingFunction,
// Output last computed result
result: function(result){
return result;
}
};
};
Transformer
// Input source
var input = [2,3,4];
// Create transformer from reducing function
var xf = transformer(sum);
// start with an initial value
var init = xf.init();
// reduce using step reducing function
var value = input.reduce(xf.step, init);
// Output last computed result
var output = xf.result(value);
// output = 10 (=1+2+3+4)
Transformer
// Input source
var input = [2,3,4];
// Create transformer from reducing function
var xf = transformer(mult);
// start with an initial value
var init = xf.init();
// reduce using step reducing function
var value = input.reduce(xf.step, init);
// Output last computed result
var output = xf.result(value);
// output = 24 (=1*2*3*4)
Reduce with Transformers
function reduce(xf, init, input){
var result = input.reduce(xf.step, init);
return xf.result(result);
}
Reduce with Transformers
var input = [2,3,4];
var init = xf.init();
var xf = transformer(sum);
var output = reduce(xf, init, input);
// output = 10 (=1+2+3+4)
Reduce with Transformers
var input = [2,3,4];
var init = xf.init();
var xf = transformer(mult);
var output = reduce(xf, init, input);
// output = 24 (=1*2*3*4)
Reduce with Transformers
var input = [2,3,4];
var init = 2;
var xf = transformer(mult);
var output = reduce(xf, init, input);
// output = 48 (=2*2*3*4)
Reduce with Transformers
var input = [2,3,4];
var init = 2;
var xf = transformer(sum);
var output = reduce(xf, init, input);
// output = 11 (=2+2+3+4)
Reduce with Functions (again)
function reduce(xf, init, input){
if(typeof xf === 'function'){
// make sure we have a transformer
xf = wrap(xf);
}
var result = input.reduce(xf.step, init);
return xf.result(result);
}
Reduce with Functions
function wrap(xf){
return {
// We require init as arg, so do not need here
init: function(){
throw new Error('init not supported');
},
// Input one item at a time, passing
// each result to next iteration
step: xf,
// Output last computed result
result: function(result){
return result;
}
};
}
Reduce with Functions
var input = [2,3,4];
var output = reduce(sum, 1, input);
// output = 10 (=1+2+3+4)
Reduce with Functions
var input = [2,3,4];
var output = reduce(mult, 2, input);
// output = 48 (=2*2*3*4)
Reduce with Transformers
var input = [2,3,4];
var xf = wrap(sum);
var output = reduce(xf, 2, input);
// output = 11 (=2+2+3+4)
Reduce with Transformers
var input = [2,3,4];
var xf = wrap(mult);
var output = reduce(xf, 1, input);
// output = 24 (=1*2*3*4)
Append +1
function append(result, item){
return result.concat(item);
}
var input = [2,3,4];
var output = reduce(append, [], input);
// output = [2, 3, 4]
Append +1
function plus1(item){
return item + 1;
}
var xfplus1 = {
init: function(){
throw new Error('init not needed');
},
step: function(result, item){
var plus1ed = plus1(item);
return append(result, plus1ed);
},
result: function(result){
return result;
}
};
Append +1
var xf = xfplus1;
var init = [];
var result = xf.step(init, 2);
// [3] (=append([], 2+1)))
result = xf.step(result, 3);
// [3,4] (=append([3], 3+1)))
result = xf.step(result, 4);
// [3,4,5] (=append([3,4], 4+1)))
var output = xf.result(result);
// [3,4,5]
Sum +1
var output = reduce(sum, 0, output);
// 12 (=0+3+4+5)
// But needed intermediate array...
Sum +1
var xfplus1 = {
init: function(){
throw new Error('init not needed');
},
step: function(result, item){
var plus1ed = plus1(item);
return sum(result, plus1ed);
},
result: function(result){
return result;
}
};
Append +1
var xfplus1 = {
init: function(){
throw new Error('init not needed');
},
step: function(result, item){
var plus1ed = plus1(item);
return append(result, plus1ed);
},
result: function(result){
return result;
}
};
Transducer +1
var transducerPlus1 = function(xf){
return {
init: function(){
return xf.init();
},
step: function(result, item){
var plus1ed = plus1(item);
return xf.step(result, plus1ed);
},
result: function(result){
return xf.result(result);
}
};
};
Transducer +1
var stepper = wrap(append);
var init = [];
var transducer = transducerPlus1;
var xf = transducer(stepper);
var result = xf.step(init, 2);
// [3] (=append([], 2+1)))
result = xf.step(result, 3);
// [3,4] (=append([3], 3+1)))
result = xf.step(result, 4);
// [3,4,5] (=append([3,4], 4+1)))
var output = xf.result(result);
// [3,4,5]
Transducer +1
var stepper = wrap(sum);
var init = 0;
var transducer = transducerPlus1;
var xf = transducer(stepper);
var result = xf.step(init, 2);
// 3 (=sum(0, 2+1)))
result = xf.step(result, 3);
// 7 (=sum(3, 3+1)))
result = xf.step(result, 4);
// 12 (=sum(7, 4+1)))
var output = xf.result(result);
// 12
Transducer +2
function plus2(input){
return input+2;
}
var transducerPlus2 = ???
Transducer +1
var transducerPlus1 = function(xf){
return {
init: function(){
return xf.init();
},
step: function(result, item){
var plussed = plus1(item);
return xf.step(result, plussed);
},
result: function(result){
return xf.result(result);
}
};
};
Transducer +2
var transducerPlus2 = function(xf){
return {
init: function(){
return xf.init();
},
step: function(result, item){
var plussed = plus2(item);
return xf.step(result, plussed);
},
result: function(result){
return xf.result(result);
}
};
};
Mapping Transducer
var map = function(f){
return function(xf){
return {
init: function(){
return xf.init();
},
step: function(result, item){
var mapped = f(item);
return xf.step(result, mapped);
},
result: function(result){
return xf.result(result);
}
};
};
};
Transducer +2
var transducer = map(plus2);
var stepper = wrap(append);
var xf = transducer(stepper);
var init = [];
var result = xf.step(init, 2);
// [4] (=append([], 2+2)))
result = xf.step(result, 3);
// [4,5] (=append([4], 3+2)))
result = xf.step(result, 4);
// [4,5,6] (=append([4,5], 4+2)))
var output = xf.result(result);
// [4,5,6]
Transducer +1
var transducer = map(plus1);
var stepper = wrap(append);
var xf = transducer(stepper);
var init = [];
var result = xf.step(init, 2);
// [3] (=append([], 2+1)))
result = xf.step(result, 3);
// [3,4] (=append([3], 3+1)))
result = xf.step(result, 4);
// [3,4,5] (=append([3,4], 4+1)))
var output = xf.result(result);
// [3,4,5]
Transduce
// First, initialize the transformation by calling a transducer
// with a stepper transformation and defining initial value.
var transducer = map(plus1);
var stepper = wrap(append);
var xf = transducer(stepper);
var init = [];
// Then step through each input item by using the reducing function
var result = xf.step(init, 2);
// [3] (=append([], 2+1)))
result = xf.step(result, 3);
// [3,4] (=append([3], 3+1)))
result = xf.step(result, 4);
// [3,4,5] (=append([3,4], 4+1)))
// Finalize to output using result
var output = xf.result(result);
// [3,4,5]
Transduce
// First, initialize the transformation by calling a transducer
// with a stepper transformation and defining initial value.
var transducer = map(plus1);
var stepper = wrap(append);
var xf = transducer(stepper);
var init = [];
// Then step through each input item by using the reducing function
// var result = xf.step(init, 2);
// [3] (=append([], 2+1)))
// result = xf.step(result, 3);
// [3,4] (=append([3], 3+1)))
// result = xf.step(result, 4);
// [3,4,5] (=append([3,4], 4+1)))
// Finalize to output using result
var output = reduce(xf, init, [2,3,4]);
// [3,4,5]
Transduce
// First, initialize the transformation by calling a transducer
// with a stepper transformation and defining initial value.
var transducer = map(plus1);
var stepper = wrap(append);
var xf = transducer(stepper);
var init = [];
var input = [2,3,4];
// Reduce result
var output = reduce(xf, init, input);
// [3,4,5]
Transduce
// First, initialize the transformation by calling a transducer
// with a stepper transformation and defining initial value.
var transducer = map(plus1);
var stepper = append;
var init = [];
var input = [2,3,4];
if(typeof stepper === 'function'){
// make sure we have a transformer for stepping
stepper = wrap(stepper);
}
// pass in stepper to create transformer
var xf = transducer(stepper);
// Reduce result
var output = reduce(xf, init, input);
// [3,4,5]
Transduce
function transduce(transducer, stepper, init, input){
if(typeof stepper === 'function'){
// make sure we have a transformer for stepping
stepper = wrap(stepper);
}
// pass in stepper to create transformer
var xf = transducer(stepper);
// Reduce result
return reduce(xf, init, input);
}
Transduce
var transducer = map(plus1);
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [3,4,5]
Transduce
var transducer = map(plus2);
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [4,5,6]
Transduce
var transducer = map(plus1);
var stepper = sum;
var init = 0;
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// 12 (=3+4+5)
Transduce
var transducer = map(plus2);
var stepper = sum;
var init = 0;
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// 15 (=4+5+6)
Transduce
var transducer = map(plus1);
var stepper = mult;
var init = 1;
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// 60 (=3*4*5)
Transduce
var transducer = map(plus2);
var stepper = mult;
var init = 1;
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// 120 (=4*5*6)
Composition
function plus3(input){
return input+3;
}
var transducerPlus3 = map(plus3);
Composition
var plus3 = function(item){
var result = plus2(item);
result = plus1(result);
return result;
};
Composition
function compose2(fn1, fn2){
return function(item){
var result = fn2(item);
result = fn1(result);
return result;
};
}
Composition
var plus3 = compose2(plus1, plus2);
var output = [plus3(2), plus3(3), plus3(4)];
// [5,6,7]
Composition
var transducerPlus3 = map(plus3);
var transducer = transducerPlus3;
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [5,6,7]
Composition
var transducerPlus3 = map(compose2(plus1, plus2));
var transducer = transducerPlus3;
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [5,6,7]
Composition
var transducerPlus3 = compose2(map(plus1), map(plus2));
var transducer = transducerPlus3;
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [5,6,7]
Composition
var transducerPlus1 = map(plus1);
var transducerPlus2 = map(plus2);
var transducerPlus3 = compose2(transducerPlus1, transducerPlus2);
var transducerPlus4 = compose2(transducerPlus3, transducerPlus1);
var transducer = transducerPlus4;
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [6,7,8]
Composition
function compose(/*fns*/){
var fns = arguments;
return function(xf){
var i = fns.length - 1;
for(; i >= 0; i--){
xf = fns[i](xf);
}
return xf;
};
}
Composition
var value = plus1(plus1(plus2(5)));
// 9
var value = compose(plus1, plus1, plus2)(5);
// 9
Composition
var transducer = compose(
map(plus1), // [3,4,5]
map(plus2), // [5,6,7]
map(plus1), // [6,7,8]
map(plus1)); // [7,8,9]
var stepper = append;
var init = [];
var input = [2,3,4];
var output = transduce(transducer, stepper, init, input);
// [7,8,9]
Map
var map = function(f){
return function(xf){
return {
init: function(){
return xf.init();
},
step: function(result, item){
var mapped = f(item);
return xf.step(result, mapped);
},
result: function(result){
return xf.result(result);
}
};
};
};
Filter
function isOdd(num){
return num % 2 === 1;
}
var transducer = filter(isOdd);
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [1,3,5]
Map
var map = function(f){
return function(xf){
return {
init: function(){
return xf.init();
},
step: function(result, item){
var mapped = f(item);
return xf.step(result, mapped);
},
result: function(result){
return xf.result(result);
}
};
};
};
Filter
function filter(predicate){
return function(xf){
return {
init: function(){
return xf.init();
},
step: function(value, item){
var allow = predicate(item);
if(allow){
value = xf.step(value, item);
}
return value;
},
result: function(value){
return xf.result(value);
}
};
};
}
Filter
function isEqual(y){
return function(x){
return x === y;
};
}
var transducer = filter(isEqual(2));
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [2]
Filter
function not(predicate){
return function(x){
return !predicate(x);
};
}
var transducer = filter(not(isEqual(2)));
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [1,3,4,5]
Pipeline order
var transducer = compose(
map(plus1), // [2,3,4,5,6]
filter(isOdd)); // [3,5]
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [3,5]
Pipeline order
var transducer = compose(
filter(isOdd), // [1,3,5]
map(plus1)); // [2,4,6]
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [2,4,6]
Filter
var transducer = filter(not(isEqual(2)));
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [1,3,4,5]
Remove
var transducer = remove(isEqual(2));
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [1,3,4,5]
Remove
function remove(predicate){
return filter(not(predicate));
}
Remove
var transducer = compose(
filter(isOdd), // [1,3,5]
map(plus1), // [2,4,6]
remove(isEqual(4))); // [2,6]
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [2,6]
Drop
var transducer = drop(2);
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [3,4,5]
Drop
function drop(n){
return function(xf){
var left = n;
return {
init: function(){
return xf.init();
},
step: function(value, item){
if(left > 0){
left--;
} else {
value = xf.step(value, item);
}
return value;
},
result: function(value){
return xf.result(value);
}
};
};
}
Take
var transducer = take(3);
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [1,2,3]
Take
function take(n){
return function(xf){
var left = n;
return {
init: function(){
return xf.init();
},
step: function(value, item){
value = xf.step(value, item);
if(--left <= 0){
// how do we stop???
}
return value;
},
result: function(value){
return xf.result(value);
}
};
};
}
Reduce Redux
function transduce(transducer, stepper, init, input){
if(typeof stepper === 'function'){
stepper = wrap(stepper);
}
var xf = transducer(stepper);
return reduce(xf, init, input);
}
Reduce Redux
function reduce(xf, init, input){
if(typeof xf === 'function'){
xf = wrap(xf);
}
// how do we stop??
var value = input.reduce(xf.step, init);
return xf.result(value);
}
Reduce Redux
function reduce(xf, init, input){
if(typeof xf === 'function'){
xf = wrap(xf);
}
return arrayReduce(xf, init, input);
}
Reduce Redux
function arrayReduce(xf, init, array){
var value = init;
var idx = 0;
var length = array.length;
for(; idx < length; idx++){
value = xf.step(value, array[idx]);
// We need to break here, but how do we know?
}
return xf.result(value);
}
Reduce Redux
function reduced(value){
return {
value: value,
__transducers_reduced__: true
};
}
function isReduced(value){
return value && value.__transducers_reduced__;
}
function deref(reducedValue){
return reducedValue.value;
}
Reduce Redux
function arrayReduce(xf, init, array){
var value = init;
var idx = 0;
var length = array.length;
for(; idx < length; idx++){
value = xf.step(value, array[idx]);
if(isReduced(value)){
value = deref(value);
break;
}
}
return xf.result(value);
}
Take 2
function take(n){
return function(xf){
var left = n;
return {
init: function(){
return xf.init();
},
step: function(value, item){
value = xf.step(value, item);
if(--left <= 0){
// we are done, so signal reduced
value = reduced(value);
}
return value;
},
result: function(value){
return xf.result(value);
}
};
};
}
Take 2
var transducer = take(3);
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [1,2,3]
Take 2
var transducer = compose(
drop(1), // [2,3,4,5]
take(3), // [2,3,4]
drop(1)); // [3,4]
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [3,4]
Appending
var transducer = appending(7);
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [1,2,3,4,5,7]
Appending
function appending(toAppend){
return function(xf){
return {
init: function(){
return xf.init();
},
step: function(value, item){
return xf.step(value, item);
},
result: function(value){
value = xf.step(value, toAppend);
if(isReduced(value)){
value = deref(value);
}
return xf.result(value);
}
};
};
}
Appending
var transducer = compose(
map(plus1), // [2,3,4,5,6]
appending(7)); // [2,3,4,5,6,7]
var stepper = append;
var init = [];
var input = [1,2,3,4,5];
var output = transduce(transducer, stepper, init, input);
// [2,3,4,5,6,7]
In Review
function xxx(){
return function(xf){
return {
init: function(){
// reserved for future use
return xf.init();
},
step: function(value, item){
// Optionally:
// 1. Step to wrapped transformer
// 2. Transform item
// 3. Terminate with reduced
//
// Value/Accumulator is off limits
// Pass all the way to stepper
return xf.step(value, item);
},
result: function(value){
// Optionally cleanup
// Must check for reduced if stepped
// Should call result on nested transformer.
return xf.result(value);
}
};
};
}
In Review
// convert reducing function to transformer
function wrap(stepper){
return {
init: function(){
throw new Error('init not supported');
},
step: stepper,
result: function(value){
return value;
}
};
}
// signal early termination
function reduced(value){
return {
value: value,
__transducers_reduced__: true
};
}
function isReduced(value){
return value && value.__transducers_reduced__;
}
function deref(reducedValue){
return reducedValue.value;
}
In Review
function arrayReduce(xf, init, array){
var value = init;
var idx = 0;
var length = array.length;
for(; idx < length; idx++){
value = xf.step(value, array[idx]);
if(isReduced(value)){
value = deref(value);
break;
}
}
return xf.result(value);
}
In Review
function transduce(transducer, stepper, init, input){
if(typeof stepper === 'function'){
stepper = wrap(stepper);
}
var xf = transducer(stepper);
return reduce(xf, init, input);
}
function reduce(xf, init, input){
if(typeof xf === 'function'){
xf = wrap(xf);
}
return arrayReduce(xf, init, input);
// or objectReduce, iteratorReduce
}
Transducers are composable algorithmic transformations.
They are independent from the context of their input and output sources and specify only the essence of the transformation in terms of an individual element.
Because transducers are decoupled from input or output sources, they can be used in many different processes - collections, streams, channels, observables, etc.
Transducers compose directly, without awareness of input or creation of intermediate aggregates.
Transducers Explained