I will be using a mix of JavaScript & TypeScript across the post. In case you aren't comfortable with these, let me know and I just might conjure up an example in your favourite language!
Another thing I take for granted is that you understand how
reduceworks too. If not, feel free to check these articles and come back to this post:Happy Learning! 🙌
contents
intro
The realm of functional programming is genuinely astounding. I've experienced a lot of joy in understanding and uncovering the plethora of ideas I've come across thus far. In this post(and possibly others in the future), I'd like to take a crack at sharing my excitement whilst exploring transducers! I hope that by the end, we'd share the same appreciation for them!
Some of us might've come across pure functions like map, filter and reduce(AKA fold in some programming languages). What each of these functions does, is quite simple. They run a function(callback/predicate) across each element of the list to produce new results. In the case of reduce we produce other data structures.
Reduce is not magic but has almighty capabilities
I had a hard time understanding the working of reduce at first. When I finally understood it, I was in awe of its simplicity and blown away by the myriads of use-cases that it could fulfil. For starters, we can even rewrite map and filter using reduce!
// The `map` function using reduce
const mapR = (inputList, mappingFn) => {
return inputList.reduce((accumulatedValue, currentValue) => {
return [...accumulatedValue, mappingFn(currentValue)];
}, []);
};
// The `filter` function using reduce
const filterR = (inputList, predicate) => {
return inputList.reduce((accumulatedValue, currentValue) => {
if (predicate(currentValue)) {
return [...accumulatedValue, currentValue];
}
return accumulatedValue;
}, []);
};
// produces a list of numbers from 1 to 10
const numbers = Array.from({ length: 10 }, (_, index) => index + 1);
// increments the value by 1
const inc = (num) => num + 1;
const onClickMapBtn = () => {
alert(mapR(numbers, inc));
};
// Remember that '0' is a `falsy` value in JS.
const isOdd = (num) => num % 2;
const onClickFilterBtn = () => {
alert(filterR(numbers, isOdd));
};In brief, reduce consumes a reducer and a starting value, when needed. The reducer is a function that consumes two arguments:
accumulator: the value returned from the previous call to thereducercurrent value: the value currently being evaluated
// The type signature for a reducer would look a lot like this
type Reducer<T, U> = (previousValue: U, currentValue: T) => U;
// Or as Rich Hickey writes:
// whatever, input -> whatever
// `whatever` is the result returned so far which eventually
// consumes a new input and returns the next `result-so-far`.
reduce is reasonably popular in the wild.
To list a few examples:
useReducerwithin React. See Here- Redux
- Plenty of methods implemented in the
Iteratortrait usereduce/fold. See Here - Evaluate values from an AST. See Here
- and numerous others...
With this power also comes great responsibility. Since we're traversing the list, one element at a time, performance might become a bottleneck in cases where the evaluation is eager and you ought to perform multiple reduction steps to reach the required output. These multiple traversals often produce intermediate lists that usually don't serve any other purpose than just being the inputs to our subsequent reduction operations.
While reduce is incredibly powerful, it has limitations when multiple operations are chained, such as map and filter, resulting in multiple traversals and temporary arrays. This is where transducers come in, offering a more efficient approach
Enter: Transducers
Clojure developers are very familiar with the idea of transducers. Rich Hickey made sure that transducers had first-class support within Clojure from the very beginning. So I'm not surprised when I see memes like this one.
It would indeed be great if a lot more languages supported transducers out of the box. What makes transducers special is that they "de-complect" or "decouple" the reducer.
complect
transitive verb
meaning: to intertwine, embrace, plait together
To begin understanding this, we need to take another look at the reducer.
type Reducer<T, U> = (previousValue: U, currentValue: T) => U;
// or just
// whatever, input -> whatever
reduce, as we now know, isn't bothered by:
- the context of use (what 'whatever' is, also meaning that it doesn't care about the data produced on each call of the reducer)
- the source of inputs (where the input comes from)
What the transducer adds to this list is the ability to abstract the job(the work done by the reducing function). The "over-arching" benefit is that this enables the composition of multiple reducers.
In case if you're wondering what composition is, here's a quick example:
// a short example on function composition
const inc = (num) => num + 1;
// Slightly modified `isOdd` method
// so that it's compatible with `inc`
const isOdd = (num) => (num % 2 ? num : 0);
const sum = (nums) =>
nums.reduce((sumCalculated, num) => {
return sumCalculated + num;
}, 0);
// Here's how you'd implement a `compose` function
// using JS (this is by no means complete)
const compose =
(...fns) =>
(args) => {
// similar to the `foldr` within in Haskell
// `reduceRight` is reduce, but the elements
// are tranversed in descending order (<---)
// So you can also say that `compose` executes
// the functions in reverse order
return fns.reduceRight(
(accumulatedResult, fn) => fn(accumulatedResult),
args
);
};
const onClickCheck = () => {
const composedFn = compose(inc, isOdd, sum);
alert(`Result: ${composedFn([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])}`);
};And finally, this is what a transducer looks like (or at least the type signature):
type Transducer<T, U> = (reducer: Reducer<T, U>) => Reducer<T, U>;
// Or more explicitly
type Transducer<T, U> = (
reducer: (previousValue: U, currentValue: T) => U
) => (previousValue: U, currentValue: T) => U;
// Or as Rich Hickey writes the:
// Reducer = whatever, input -> whatever
// Transducer = (whatever, input -> whatever) -> (whatever, input -> whatever)
In simple terms, transducers allow us to combine multiple data transformations (like mapping, filtering, etc.) into a single pass over the data, avoiding unnecessary intermediate steps.
Showing off the transducer
Let's quickly write down the mapping(the map reduction function) and the filtering(the filter reduction step) as reducers:
const mapping = (mappingFn) => (accumulatedValue, currentValue) => {
return [...accumulatedValue, mappingFn(currentValue)]; // `Array.concat` can be used here as well
};
const filtering = (predicate) => (accumulatedValue, currentValue) => {
if (predicate(currentValue)) {
return [...accumulatedValue, currentValue]; // `Array.concat` can be used here as well
}
return accumulatedValue;
};We're now looking at two reducing functions that could be utilised in place of map and filter, within reduce.
Now, to finally see a transducer in action, we need to:
- be able to compose the reducers together
- abstract the
jobperformed by our reducers(an operation that produces the next "whatever" in ourreducer)
and we have a transducer in action! 🎉
// To convert our reducers to transducers:
// is to first make `job` performed by our
// reducer separate from the reducer.
// In our case, we've got `job` = `Array.concat` or `Array.push` 🤷♀️
// NOTE: Using 'T' in the names to differentiate between the mapping
// and filtering reducers written here and the ones shown above.
const mappingT = (mappingFn) => (job) => (accumulatedValue, currentValue) => {
return job(accumulatedValue, mappingFn(currentValue));
};
const filteringT = (predicate) => (job) => (accumulatedValue, currentValue) => {
if (predicate(currentValue)) {
return job(accumulatedValue, currentValue);
}
return accumulatedValue;
};
// increment function
const inc = (num) => num + 1;
// function to check if odd
const isOdd = (num) => num % 2;
// function to help use `compose` our reducers
const compose =
(...fns) =>
(args) => {
return fns.reduceRight(
(accumulatedResult, fn) => fn(accumulatedResult),
args
);
};
const composedFns = compose(mappingT(inc), filteringT(isOdd));
const concat = (arr, elem) => arr.concat(elem);
const data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const transducedResult = data.reduce(composedFns(concat), []);
// The transducing that's just taken place is equivalent to:
// and as you can see it's got 2 traversals.
const equivalentResult = data.map(inc).filter(isOdd);
// It is also equivalent to this operation as well:
// If we consider the `mapping` and `filtering` reducers
// from above, we can do the following:
// const equivalentResult = data
// .reduce(mapping)
// .reduce(filtering);
render(
<>
<button
onClick={()=> {
alert(transducedResult);
}}
style={{ marginRight: "8px" }}
>
Action 🎬
</button>
<button
onClick={()=> {
alert(equivalentResult);
}}
>
Check Result ✅
</button>
</>
);Conclusion
Essentially, what we're achieving with this abstraction, is the ability to bypass the intermediate lists that might've been produced otherwise.
In hindsight, the cost of the abstraction in comparison with the gains are pretty stark. This is why I'm in awe of this. So subtle, yet very effective. Although the ramifications that it may cause within our code is pretty high, the ability to do complex operations becomes much easier, because all have to do now, is to have reducers in place. Combining them is easy and our reduce process looks a lot more elegant.
I hope that I did justice to the idea by sparking your curiosity to learn more about it and see how it's implemented in your favourite language.
So long then! 👋