Transducers

gistfile1.txt

/**
 * reducer :: a -> b -> a
 *
 * reduce :: Iterable f => (a -> b -> a) -> f b -> a -> a
 *
 * makeMappingTransducer :: (a -> b) -> (c -> b -> c) -> (c -> a -> c)
 */
const makeMappingTransducer = (transformer) => (reducer) => {
	return (acc, input) => reducer(acc, transformer(input))
}

// the call below returns a fn that takes a reducer to return a reducer.
// that result is a transducer!
const mapIncTransducer = makeMappingTransducer(it => it + 1);

// when we apply our transducer, we get to specify how reduction will work.
// this is part of the power of transducers: you're decoupling how to do 
// the ultimate reduction from any element-wise transformations. 
// And, we get to specify separately where the values come from (which 
// would also be true of a partially applied reduce fn, but still).
const incConcatReducer = mapIncTransducer((acc, input) => acc.concat(input));
const incSumReducer = mapIncTransducer((acc, input) => acc + input);

// examples
[1, 2, 3, 4, 5].reduce(incConcatReducer, []) // -> [2, 3, 4, 5, 6]
[1, 2, 3, 4, 5].reduce(incSumReducer, 0) // -> 20


// The examples above are cool, but transducers us do other cool stuff too.
// In the example below, when we create our new reducer, we have the option
// to not even call the reducer we were provided. This lets us implement filter,
// and control flow like things in general! Sorta like how Maybe.map can 
// decide to call the provided function or can ignore it.
const makeFilteringTransducer = (predicate) => (reducer) => {
  return (acc, input) => predicate(input) ? reducer(acc, input) : acc;
}

// Again, we can create one transducer and use it with different reductions.
const filterOddTransducer = makeFilteringTransducer(it => it % 2 == 1);
const oddSumReducer = filterOddTransducer((acc, it) => it + acc);
const oddProductReducer = filterOddTransducer((acc, it) => it * acc)

// examples
[1, 2, 3, 4, 5].reduce(oddSumReducer, 0)  // -> 9
[1, 2, 3, 4, 5].reduce(oddProductReducer, 1) // 15


// Lastly, for function composition to work in general, each function has
// to take only one argument, whose type is the return type of the prior argument.
// Because a transducer goes from reducer -> reducer, we can now arbitrarily
// compose transducers, into a pipeline that'll take a reducer in and return
// a reducer that's been transformed by each transducer in the pipeline.
// Consider: 
const compose = (a, b) => (x) => a(b(x))
const mapIncThenfilterOddTransducer = compose(mapIncTransducer, filterOddTransducer);

// Now, we again define our final reduction and it gets transformed through the pipeline.
const sumFilteredOddMappedInc = mapIncThenfilterOddTransducer((acc, it) => acc + it);

[1, 2, 3, 4, 5].reduce(sumFilteredOddMappedInc, 0) // 8 (map to [2, 3, 4, 5, 6]; filter to [3, 5] sum)

// ^ Note: it's a bit counterintuitive that the map happens first, since we ran the 
// composition through the filterOddTransducer first. But the reason for this is that,
// even though we first transform the sum reducer into the oddSumReducer and then pass
// that reducer into the mapIncTransducer, when we run the resulting reducer, it does
// the map(inc) before calling the oddSumReducer it was created with.