The Array.reduce Method Part 6 - Transducers
Greetings, friends! This is Part 6 of my tutorial series on the Array.reduce method in JavaScript, and it's an interesting one! In this tutorial, I will discuss how to make transducers in JavaScript.
Reducer Review
First, let's refresh on what reducers are. In case you may have forgotten, a reducer is the name of the callback function we pass into the reduce or reduceRight method.
const sum = (accumulator, currentValue) => accumulator + currentValue;
const result = [1, 2, 3].reduce(sum);
console.log(result); // 6
In the example above, the function, sum, is the known as the reducer. We pass this function into the reduce method, and it is called multiple times.
What are Transducers and Why Use Them?
Transducers are simply reducers that return new reducers!
reducer = (accumulator, currentValue) => newAccumulatorValue
transducer = reducer => transformedReducer
That's it. Tutorial over. Just kidding 🙂
Transducers are composable transformations that we can apply to one or more values. We learned in Part 5 that we can apply function compositions easily using a compose function.
const compose = (...functions) => initialValue => functions.reduceRight(
(acc, fn) => fn(acc),
initialValue
)
const array = [-1, 1, -2, 2, -3, 3, -4, 4];
const mapDouble = array => array.map(x => x * 2);
const mapTriple = array => array.map(x => x * 3);
const filterEven = array => array.filter(x => x % 2 === 0);
const filterPositive = array => array.filter(x => x > 0);
// Similar to: mapTriple(filterEven(filterPositive(mapDouble(array))))
const compositeFunction = compose(
mapTriple,
filterEven,
filterPositive,
mapDouble
);
const result = compositeFunction(array);
console.log(result); // [6, 12, 18, 24]
There's a problem with this approach though. We are running a separate call to map and filter methods for each operation we supply to the compose function. That's a total of four iterations over the entire array: two map calls and two filter calls. That doesn't even include the iteration done by the reduceRight method inside the compose function. Therefore, we have a total of five iterations over array. Wow! What a waste of computational resources! Shame! Shame! 🔔
Transducers help overcome this dilemma. What if I told you that you only have to iterate through the array once? Exciting, right?! 😁
Transducers became really popular due to the Clojure programming language. As a result, very intelligent developers decided to build JavaScript libraries that utilized transducers such as Ramda and transducers-js.
In this tutorial, we won't be building transducers that are as sophisticated as Ramda. We will be building simple ones that hopefully prove how useful they are. Our goal is to perform as few iterations on an array as possible.
Let's look at an example of code that uses the native map and filter methods to transform an array, but causes the array to be iterated over multiple times.
const array = [1, 2, 3, 4, 5];
const isEven = x => x % 2 === 0;
const newArray = array
.map((x) => x * 3)
.map((x) => x + 1)
.filter(isEven)
.slice(0, 2); // grab the first two elements from the array
console.log(newArray); // [4, 10]
We learned in Part 2 that we can replace map and filter method chains with a reduce method. However, writing a reduce method to replace these method chains starts to become more complex as you apply more operations onto an array. Let's try replacing these method chains with an intelligent reducer that we can pass into the reduce method.
const array = [1, 2, 3, 4, 5];
const isEven = x => x % 2 === 0;
// acc = accumulator
// cur = currentValue
const newArray = array.reduce(
(acc, cur) =>
acc.length >= 2 ? acc : isEven(cur * 3 + 1) ? acc.concat(cur * 3 + 1) : acc,
[]
);
console.log(newArray); // [4, 10]
Now, the array is iterated over once. This isn't much code, but it doesn't look pretty. It would be nice if we could create a list of operations and apply them in a reducer automatically without having to worry about rewriting so much code.
How to Build Filter Transducers
We don't want to run operations that iterate the array multiple times like the native map and filter methods in JavaScript. Therefore, we'll have to create our own versions of them in the form of transducers. Remember, transducers are functions that returns a new reducer. Think of them as higher-order reducers, similar to higher-order functions. A higher-order function returns a new function. A higher-order reducer returns a new reducer.
Let's start with creating a "filter" transducer.
const filterTransducer = (predicate) => {
return nextReducer => (acc, cur) => predicate(cur) ? nextReducer(acc, cur) : acc;
}
Let's analyze this code carefully. The filterTransducer function accepts a predicate, a test that is normally passed into the native filter method.
const isEven = x => x % 2 === 0;
const result = [1, 2, 3, 4, 5].filter(isEven);
console.log(result); // [2, 4]
In the code snippet above, isEven would be the predicate.
Next, the filterTransducer function will return a function that accepts a reducer. Then, it returns another reducer. It might look confusing with arrow functions, so let's rewrite the code using function statements.
function filterTransducer(predicate) {
return function(nextReducer) {
return function(acc, cur) {
return predicate(cur) ? nextReducer(acc, cur) : acc;
}
}
}
Lots of nested functions, right? The filterTransducer is actually saying to run the next reducer only if the predicate is true. If the predicate is false, then we'll prevent the next reducer from ever seeing this value.
Let's see how we can use this filter transducer.
function filterTransducer(predicate) {
return function(nextReducer) {
return function(acc, cur) {
return predicate(cur) ? nextReducer(acc, cur) : acc;
}
}
}
const isEven = x => x % 2 === 0;
// pass a predicate to the filter transducer
const transduce = filterTransducer(isEven);
// use our filter transducer to "transduce" or modify a reducer, so it becomes a new reducer
const filterReducer = transduce((acc, cur) => acc.concat(cur));
// run the reduce method with our new reducer and set the inital value to an empty array
const result = [1, 2, 3, 4, 5].reduce(filterReducer, []);
console.log(result); // [2, 4]
You have just created a transducer that behaves similar to the filter method! Awesome! 😎
I think the most important line in the code is the following:
const newReducer = transduce((acc, cur) => acc.concat(cur));
We have to pass in a "default" reducer, so that we have a starting point. Transducers must first accept a reducer, so that it can return a new, modified reducer. In our example, we create a very simple reducer that concatenates or adds new values to an array. Effectively, it just returns the same array we call the reduce method on.
const concatReducer = (acc, cur) => acc.concat(cur);
const initialValue = [];
const result = [1, 2, 3, 4, 5].reduce(concatReducer, initialValue);
console.log(result); // [1, 2, 3, 4, 5]
We then take this boring concatReducer and use a transducer to transform it into a reducer that can filter values.
const filterReducer = transduce((acc, cur) => acc.concat(cur));
This reducer will only filter out even numbers because we passed isEven as our predicate.
How to Build Map Transducers
We learned how to create our own filter transducer to replace the need for native filter methods. Now, we need to create our own map transducer to replace the need for map methods.
const mapTransducer = (fn) => {
return nextReducer => (acc, cur) => nextReducer(acc, fn(cur));
}
If we rewrite this code using function statements instead of arrow functions, we obtain the following code:
function mapTransducer(fn) {
return function(nextReducer) {
return function(acc, cur) {
return nextReducer(acc, fn(cur));
}
}
}
This transducer accepts a function, fn, as a parameter. When iterating over an array, the new reducer will wrap each value by this function.
Let's see how we can use this map transducer.
function mapTransducer(fn) {
return function(nextReducer) {
return function(acc, cur) {
return nextReducer(acc, fn(cur));
}
}
}
const double = x => x * 2;
// pass a function to the map transducer
const transduce = mapTransducer(double);
// use our map transducer to "transduce" or modify a reducer, so it becomes a new reducer
const mapReducer = transduce((acc, cur) => acc.concat(cur));
// run the reduce method with our new reducer and set the inital value to an empty array
const result = [1, 2, 3, 4, 5].reduce(mapReducer, []);
console.log(result); // [2, 4, 6, 8, 10]
Again, we start with a boring concatReducer and use a transducer to transform it into a reducer that can map over values and perform an operation on them.
const mapReducer = transduce((acc, cur) => acc.concat(cur));
Composing Transducers
The main reason why we created filter and map transducers was to make sure that we only iterate an array once when performing multiple transformations. By creating our own filter and map transducers, we can compose them using the compose function I discussed in Part 5.
const compose = (...functions) => initialValue => functions.reduceRight(
(acc, fn) => fn(acc),
initialValue
);
const filterTransducer = (predicate) => {
return nextReducer => (acc, cur) => predicate(cur) ? nextReducer(acc, cur) : acc;
}
const mapTransducer = (fn) => {
return nextReducer => (acc, cur) => nextReducer(acc, fn(cur));
}
const isEven = x => x % 2 === 0;
const double = x => x * 2;
const evenFilterTransduce = filterTransducer(isEven);
const doubleMapTransduce = mapTransducer(double);
const concatReducer = (acc, cur) => acc.concat(cur);
const composedTransduce = compose(evenFilterTransduce, doubleMapTransduce);
const combinedReducer = composedTransduce(concatReducer);
const result = [1, 2, 3, 4, 5].reduce(combinedReducer, []);
console.log(result); // [4, 8]
We effectively ran a custom filter and map operation over an array, but only iterated through the array once!!! This can drastically speed up our code.
In the example above, we are using the compose function to create a composition out of the transducers. We then can create a new "combined" reducer that modifies the concatReducer to both filter and map over values in an array.
Pay attention to the order by which the operations are applied.
const composedTransduce = compose(evenFilterTransduce, doubleMapTransduce);
In our example, the "even filter" was applied before the "double map." We know this is true because our final result contains an array with just two values. If we had doubled the values in the array first, then they all would have been even values. The final result would have then contained five elements, not two.
What Libraries Implement Transducers?
Multiple libraries already implement transducers such as Ramda and transducers-js. Observable pipelines in RxJS are also very similar to transducers. If you'd like to use transducers in your code, I'd recommend using one of these libraries instead of writing transducers from scratch.
These libraries have utilities to make it easier to work with transducers and have very performant code. In the transducers we made in this tutorial, we iterated over an array just once, but it would be nice to terminate or "cancel" the reducer early. It would also be helpful if we could use transducers on other types of objects instead of only arrays. These libraries take care of these features for us.
Ramda and transducers-js have already optimized transducers and follow a common protocol. By following the same protocol, it allows interoperability between libraries. You'll be able to use transducers from other libraries or create your own and then use them in Ramda.
Conclusion
Transducers are perhaps the most complicated tools we can build out of reducers. However, they are extremely powerful and help us make highly performant code. Instead of chaining a bunch of filter, map, and/or reduce methods, we can iterate through an an array only once.
This concludes my tutorial series on the reduce method. I hope you learned a lot! The reduce method is indeed one of the most powerful methods in all of JavaScript. If you take time to understand how to wield it, you will surely become a mighty developer!!!