Functional JavaScript: transducers
February 2, 2025
This is our third article about functional programming in JavaScript. We have already covered its basics and digged into the transformers. Now its the time to address transducers.
To do this, we will need to rely on the composition of transformers we saw earlier.
Transformers composition
The map and filter functions we saw in the previous article have a difference compared to those provided by Array.map and Array.filter: they create functions that receive a reducer and return another reducer.
language-javascript
// map = (fn) => (reducer) => reducer
const map = (mapper) => (reducer) => (acc, val) =>
reducer(acc, mapper(val));
const filter = (predicate) => (reducer) => (acc, val) =>
predicate(val) ? reducer(acc, val) : acc;
Which means that our transformers are composable.
language-javascript
(reducer) => reducer
(reducer) => reducer
(reducer) => reducer ...
Let's try with an example: we might need to select those elements of an array that are less than five, and then calculate their squares. We can create a filter function for the selection and a mapper function for the power calculation, and use them with our reduce function.
language-javascript
const data = [1, 2, 3, 4, 5];
const lessThanFive = filter((x) => x < 5);
const squares = map((x: number) => power(x, 2));
const filteredAndSquared = reduce(
lessThanFive(squares(arrayConcat)),
data, []
);
console.log(filteredAndSquared); // [1, 4, 9, 16]
And again, let's remember we said that although composition is associative, it is not commutative: the order in which the functions are composed matters.
f \circ g \neq g \circ f
We could take advantage of this and, if necessary, reverse the positions of lessThanFive and squares to first calculate the squares, and then get those that are less than five.
language-javascript
const data = [1, 2, 3, 4, 5];
const squaredAndFiltered = reduce(
squares(lessThanFive(arrayConcat)),
data, []
);
console.log(squaredAndFiltered); // [1, 4]
Or we might need to filter those elements whose squares are less than five:
language-javascript
const data = [1, 2, 3, 4, 5];
const isSquareLessThanFive = filter((x) => power(x, 2) < 5);
const filtered = reduce(
isSquareLessThanFive(arrayConcat),
data, []
);
console.log(filtered); // [1, 2]
Or we could even square each element and reduce it to a single value.
language-javascript
const accumulate = (a: number, b: number): number => a + b;
const data = [1, 2, 3, 4, 5];
const filteredSquaredAndAccumulated = reduce(
lessThanFive(squares(accumulate)),
data,
0
);
console.log(filteredSquaredAndAccumulated); // 30
And since our transformers can be composed, we can use our compose function for all these operations:
language-javascript
const compose = (...fns) => (items) =>
fns.reduceRight((acc, curr) => curr(acc), items);
const data = [1, 2, 3, 4, 5];
const filterAndSquare = compose(lessThanFive, squares);
const filteredSquaredAndAccumulated = reduce(
filterAndSquare(accumulate), data, 0
);
console.log(filteredSquaredAndAccumulated); // 30
With this, we have all the pieces needed for the operation we are focusing on in this article: transduction.
Transducers
As we mentioned, our filter and map functions have their analogs in Array.filter and Array.map. One might then ask, what is the point of implementing our own functions when the Array object already has these methods.
Well, let’s consider the following scenario: suppose we have a large array —ten million elements— on which we need to perform various operations.
language-javascript
const data = Array.from({ length: 10000000 }, (_, index) => index + 1);
To process it with Array.map and Array.filter, we need to first store the entire array in memory. And since both methods return a new array, each time we call one of them we are creating a new one.
For an array with just a few hundred elements this is not much of an issue. But it is not a scalable pattern because when we deal with a large list we could be consuming a significant amount of resources.
Additionally we could face another problem: since we're storing the processed data in memory, if the application encounters a failure and throws during the processing we may lose the data already processed.
This all happens because Array methods execute sequentially over the entire array: that is, if we want to apply Array.map and Array.filter over an array, map will first traverse the entire array, transforming all its elements and returning a new array, and then filter will do the same, selecting the elements we are interested in.
language-javascript
const data = ["1", "2", "3"];
const result = data
.map((x) => (console.log("map"), Number(x)))
.filter((x) => (console.log("filter"), x % 2 !== 0));
console.log(result); // [1, 3]
// map
// map
// map
// filter
// filter
// filter
// [1, 3]
It would be fantastic if we could decouple the processing of each individual element from the processing of the entire array.
To achieve this we could start with a change: instead of making successive passes over the entire array, we could try performing all the necessary actions on the first element, then the second, and so on, until we reach the last element.
Well, we do not need to implement anything to achieve this, because this is precisely what our map and filter functions are already doing with reduce.
language-javascript
const data = ["1", "2", "3"];
const toInt = map((x: string) => (console.log("map"), Number(x)));
const isOdd = filter((x: number) => (console.log("filter"), x % 2 !== 0));
const toIntAndFilterOdds = compose(toInt, isOdd);
const result = reduce(toIntAndFilterOdds(concat), data, []);
console.log(result);
// map
// filter
// map
// filter
// map
// filter
// [1, 3]
Although it seems like a small difference, it is not, as it opens the door to transform reduce into a function that, instead of receiving a transformer with a reducer already applied, receives them separately and applies them within itself.
In this way, instead of reducing with reduce:
language-javascript
const reduce = (reducer, iterable, initialValue) => {
let acc = initialValue;
for (const item of iterable) {
acc = reducer(acc, item);
}
return acc;
};
We would use transduce, which would look like this:
language-javascript
const transduce = (
transformer,
reducer,
iterable,
initialValue
) => {
let acc = initialValue;
const transformedReducer = transformer(reducer);
for (const item of iterable) {
acc = transformedReducer(acc, item);
}
return acc;
};
const data = ["1", "2", "3"];
const toInt = map((x: string) => (console.log("map"), Number(x)));
const isOdd = filter((x: number) => (console.log("filter"), x % 2 !== 0));
const toIntAndFilterOdds = compose(toInt, isOdd);
const result = transduce(toIntAndFilterOdds, concat, data, []);
console.log(result);
// map
// filter
// map
// filter
// map
// filter
// [1, 3]
This is a transducer: a function that takes a transformer —which can be a series of composed transformers— and a reducer —responsible for the reduction operation— along with an iterable and an initial value, and will reduce the iterable over the initial value using the transformer and the reducer.
Transducers have a significant efficiency advantage over method chaining, as seen with the Array methods. This becomes clear if we revisit the large array scenario we discussed earlier.
Let’s say we have a list of ten million products with different prices that we sell remotely, with a shipping cost of ten dollars. Buyers can finance the payment in twelve monthly installments, but only if each resulting monthly installment is an integer —without decimals—. With this, we have been asked to find the highest spending a customer can make when buying a financeable product.
We can do this with Array methods:
language-javascript
// Array with 10.000.000 elements
const data = [
{ name: "Product 1", price: 73 },
...
];
const addShippingCosts = (product: Product) => product.price + 10;
const isEligibleForFinancing = (price: number) => price % 12 === 0;
const getBiggerExpense = (a: number, b: number) => (a > b ? a : b);
console.time("array_methods");
const result = data
.map(addShippingCosts)
.filter(isEligibleForFinancing)
.reduce(getBiggerExpense);
console.log(result); // 120
console.timeEnd("array_methods"); // 141
Great, we get the correct result. Let’s take note of how long it takes to execute this code: at the time of writing, the TypeScript Playground shows 141 ms, though it might vary depending on the machine it’s executed on.
Now, let’s try using a transducer:
language-javascript
// Array with 10.000.000 elements
const data = [
{ name: "Product 1", price: 73 },
...
];
const eligibleForFinancing = filter(isEligibleForFinancing);
const priceWithShippingCosts = map(addShippingCosts);
const piped = pipe(eligibleForFinancing, priceWithShippingCosts);
console.time("transduce");
const result = transduce(piped, getBiggerExpense, data, 0);
console.log(result); // 120
console.timeEnd("transduce"); // 62
As we can see the same result is obtained, but with a notable efficiency gain. This, of course, will depend on the time and space complexity of the algorithms used: but it’s clear that, with the same algorithms, transducers are more efficient than method chaining.
However, once we call transduce, it will attempt to process the entire array by storing it in memory, which could potentially overload the system. In other words, the current transducer is eagerly evaluated.
What we actually want is a function that allows us to process the data with lazy evaluation, so that the data is processed only on demand. And if we recall our first article, we mentioned that lazy evaluation in JavaScript can be implemented with generators. Let’s look at an example of a generator:
language-javascript
function* lazySum(a, b) {
yield a + b;
}
let result = lazySum(1, 3);
console.log(result); // {} (not evaluated yet)
console.log(result.next().value); // 4
So, let's try to implement our transduce function in a way that lazily evaluates the data:
language-javascript
function* lazyTransduce(
transformer,
reducer,
iterable,
initialValue
) {
const transformedReducer = transformer(reducer);
let acc = initialValue;
for (const item of iterable) {
acc = transformedReducer(acc, item);
yield acc;
}
}
Instead of returning, lazyTransduce will return a generator that will yield its state in acc each time its next() method is executed.
language-javascript
// Array with 10.000.000 elements
const data = [
{ name: "Product 1", price: 73 },
...
];
const eligibleForFinancing = filter(isEligibleForFinancing);
const priceWithShippingCosts = map(addShippingCosts);
const piped = pipe(eligibleForFinancing, priceWithShippingCosts);
const result = lazyTransduce(piped, getBiggerExpense, data, 0);
console.log("result.next().value: ", result.next().value); // 0
console.log("result.next().value: ", result.next().value); // 0
console.log("result.next().value: ", result.next().value); // 0
console.log("result.next().value: ", result.next().value); // 120
console.log("result.next().value: ", result.next().value); // 120
console.log("result.next().value: ", result.next().value); // 120
...
Finally, this is what is properly referred to as a transducer. Here, lazy evaluation allows us to process the data on demand and perform actions on it while maintaining full control over the pace and frequency at which we do so.
For example, we might want to persist the data every certain number of elements, or send notifications to external services about the data found. And all of this can be done without causing system overload, since the spatial complexity is negligible and only the memory required for each iteration step will be used.
And just like when we used our reduce function, we can pass different reducers to our transducers to accumulate data in various ways. For example, by concatenating the data into a new array using concat:
language-javascript
const data = [
{ name: "Product 1", price: 74 },
{ name: "Product 2", price: 93 },
{ name: "Product 3", price: 110 },
{ name: "Product 5", price: 82 },
];
const eligibleForFinancing = filter(isEligibleForFinancing);
const priceWithShippingCosts = map(addShippingCosts);
const piped = pipe(eligibleForFinancing, priceWithShippingCosts);
const result = lazyTransduce(piped, concat, data, []);
console.log(result.next().value); // [84]
console.log(result.next().value); // [84]
console.log(result.next().value); // [84, 20]
console.log(result.next().value); // [84, 120]
console.log(result.next().done); // true
There is much to say about transducers, especially because there are numerous implementations: they are behind methods offered by various libraries, like pipe in RxJS, or are directly supported, as in the case of Ramda. The same goes for them as with other utilities: it is not always the best decission to implement our own ones due to the work and risk involved in developing the most efficient implementation possible. However, it’s important to be aware of their existence and their fundamentals, as they clearly show their potential.
As usual, the code can be run in the TypeScript Playground and is available for download at git.antoniodiaz.me.
If you have any questions or have found an error, feel free to contact me at the address listed in the footer.