Let's start with a definition: A transducer is a function that takes a reducer function and returns a reducer function.
A reducer is a binary function that takes an accumulator and a value and returns an accumulator. A reducer can be executed with a reduce function (let's also define a curry function to make working with reduce easier):
const curry = f => {
const _curry = (...args) => args.length < f.length ?
(...restArgs) => _curry(...args, ...restArgs) :
f(...args);
return _curry;
}
const _reduce = (reducer, init, data) => {
let result = init;
for (const item of data) {
result = reducer(result, item);
}
return result;
}
const reduce = curry(_reduce);
With reducer we can implement map and filter functions:
const mapReducer = xf => (acc, item) => [...acc, xf(item)];
const _map = (xf, arr) => reduce(mapReducer(xf), [], arr);
const map = curry(_map);
const filterReducer = predicate => (acc, item) => predicate(item) ?
[...acc, item] :
acc;
const _filter = (predicate, arr) => reduce(filterReducer(predicate), [], arr);
const filter = curry(_filter);
As we can see there're a few similarities between map and filter and both of those functions work only with arrays. Another disadvantage is that when we compose those two functions, in each step a temporary array is created that gets passed to another function.
const pipeReducer = (acc, f) => f(acc);
const pipe = (...fs) => data => reduce(pipeReducer, data, fs);
const even = n => n % 2 === 0;
const double = n => n * 2;
const doubleEven = pipe(filter(even), map(double));
doubleEven([1,2,3,4,5]);
// first we get [2, 4]
// then final result: [4, 8]
Transducers help us solve that concerns: when we use a transducer there are no temporary arrays created and we can generalize our functions to work not only with arrays. Transducers need a transduce function to work:
const _transduce = (xform, iterator, init, data) =>
reduce(xform(iterator), init, data);
const transduce = curry(_transduce);
const compose = (...fs) => pipe(...fs.reverse());
const _mapping = (xf, reducer) => (acc, item) => reducer(acc, xf(item));
const mapping = curry(_mapping);
const _filtering = (predicate, reducer) => (acc, item) => predicate(item) ?
reducer(acc, item) :
acc;
const filtering = curry(_filtering);
const arrReducer = (acc, item) => [...acc, item];
const transformer = compose(filtering(even), mapping(double));
const performantDoubleEven = transduce(transformer, arrReducer, [])
performantDoubleEven([1, 2, 3, 4, 5]); // -> [4, 8] with no temporary arrays created
We can also define map and filter using transducer:
const p_map = (xf, data) => transduce(mapping(xf), arrReducer, [], data);
const pmap = curry(_map);
const p_filter = (predicate, data) => transduce(filtering(predicate), [], data);
const pfilter = curry(_filter);
const pdoubleEven = pipe(pfilter(even), pmap(double));
doubleEven([1,2,3,4,5]);
no comments
sign in to comment