1. What Is a Transducer?
In functional programming, a transducer is an efficient, composable data-processing function that creates no intermediate data.
That definition may not tell you much. Let's walk through some straightforward code:
Suppose we want the sum of the squares of all odd numbers below 100 that are divisible by 3. (All examples use TypeScript to make function parameters and return values clearer.)
// First, define a helper function to generate an array within a given range
function range(from: number = 0, to: number = 0, skip: number = 1): number[] {
const result = [];
for (let i = from; i < to; i += skip) {
result.push(i);
}
return result;
}
const odd = (num: number): boolean => num % 2 !== 0; // Test whether a number is odd
const pow2 = (num: number): number => Math.pow(num, 2); // Calculate the square
const sum = (cum: number, num: number): number => cum + num; // Sum the values
const data: number = range(0, 100).filter(odd).map(pow2).reduce(sum); // Calculate the result
console.log(data); // 166650
This is how we'd usually write it. The array is traversed three times, and since we only need the result of reduce, filter and map both create intermediate data we don't need. With large datasets, repeated traversals and all that intermediate data will undoubtedly cause serious performance problems. This is one of the drawbacks people criticize about functional programming in JavaScript.
So when processing large datasets, people generally favor an imperative approach: a for loop. But do we have to? Of course not! The Clojure community had already introduced the concept of transducers: https://clojure.org/reference/transducers . With this approach, we can compose data-processing functions such as map and filter into an efficient function that creates no intermediate data.
Now suppose we have a function called compose that combines other functions to produce transducer functions. We could implement the algorithm like this:
const trans = compose(filter(odd), map(pow2), reduce(sum));
const data: number = trans(range(0, 100));
The trans function traverses the array just once, performing filter, map, and reduce together to produce the result directly.
2. Make Functions Composable
The compose function needs to combine each function passed to it into a transducer, so every input function must be composable. That means the functions need compatible parameters and return values. The default map and filter don't meet this requirement, so we need to wrap them to give them a common parameter and return-value pattern.
Whether we're using map, filter, or forEach, we're traversing a collection. Any traversal can be implemented with reduce, so we'll use reduce to implement map and filter with the same parameter and return-value pattern.
type Reducing<T, U> = (T, U) => T;
type F<T, U> = (T) => U;
const mapReducer = <T, U> (f: F<T, U>) => (result: U[], item: T) => {
result.push(f(item));
return result;
};
const filterReducer = <T> (predicate: F<T, boolean>) => (result: T[], item: T) => {
if (predicate(item)) {
result.push(item);
}
return result;
};
const data: number = range(0, 100)
.reduce(filterReducer(odd), [])
.reduce(mapReducer(pow2), [])
.reduce(sum, 0);
console.log(data); // 166650
We can now use mapReducer and filterReducer in place of map and filter. The functions they return share the same parameter and return-value pattern. We'll call this a reducing function, represented in TypeScript as type Reducing<T, U> = (T, U) => T;. Let's add another layer of abstraction so we can pass the reducing function in from outside:
const map = <T, U> (f: F<T, U>) => (reducing: Reducing<U[], U>) => (result: U[], item: U) => reducing(result, f(item));
const filter = <T> (predicate: F<T, boolean>) => (reducing: Reducing<T[], T>) => (result: T[], item: T) => predicate(item) ? reducing(result, item) : result;
Now filter and map both return a higher-order function that can accept another function—including functions returned by filter and map. That makes them composable! Let's combine them and use reduce:
const trans: Reducing<number> = filter(odd)(map(pow2)(sum));
const data: number = range(0, 100).reduce(trans, 0);
console.log(data); // 166650
Well done! With these functions, we can easily compose a series of functions into one efficient function and calculate the result in a single traversal!
3. Compose Function
An expression such as filter(odd)(map(pow2)(sum)) does compose the functions, but the deep nesting and all those parentheses make the code much harder to read. So let's implement a compose function to handle the composition:
const compose = (...f: ((...any) => any)[]): Reducing<any> => {
const [r, ...fs] = [...f].reverse();
return [...fs].reduce((res, fn) => fn(res), r);
};
The compose function takes a reducing function and a series of higher-order functions: (((a, b, …, n) → o), (o → p), …, (x → y), (y → z)) → ((a, b, …, n) → z). It passes the first function to the second, then passes the returned function to each subsequent function in turn. The result is a new reducing function, which we'll call a transducer.
Now we can use compose to combine a series of functions:
const trans: Reducing<number> = compose(filter(odd), map(pow2), sum);
const data: number = range(0, 100).reduce(trans1);
console.log(data); // 166650
Bingo! The correct result! Simple, clear, elegant, and efficient.
4. Benchmark
Calculate the sum of the squares of all numbers below 1000000 that are multiples of 7, have an even units digit, and have a preceding digit that is not divisible by 4:
const even: (number) => boolean = (x) => !odd(x);
const trans: Reducing<number, number> = compose(
filter(x => x % 7 === 0),
filter(x => even(x % 10)),
filter(x => (x - 1) % 4 !== 0),
map(x => x * x),
sum
);
console.time("With transducer");
const result1 = range(0, 1000000).reduce(trans, 0);
console.log(result1);
console.timeEnd("With transducer");
console.time("Without transducer");
const result2 = range(0, 1000000)
.filter(x => x % 7 === 0)
.filter(x => even(x % 10))
.filter(x => (x - 1) % 4 !== 0)
.map(x => x * x)
.reduce(sum, 0);
console.log(result2);
console.timeEnd("Without transducer");
Benchmark results (Node v8.9.1, macOS 10.13.3, i7 2.5 GHz, 16GB):
- With transducer: 50.254ms
- Without transducer: 89.749ms
In this example, using a transducer and some simple function composition improved performance by 44%!
5. Code
Here's all the code needed to implement a transducer. Just three functions!
type Reducing<T, U> = (T, U) => T;
type F<T, U> = (T) => U;
const map = <T, U> (f: F<T, U>) => (reducing: Reducing<U[], U>) => (result: U[], item: U) => reducing(result, f(item));
const filter = <T> (predicate: F<T, boolean>) => (reducing: Reducing<T[], T>) => (result: T[], item: T) => predicate(item) ? reducing(result, item) : result;
const compose = (...f: ((...any) => any)[]): Reducing<any, any> => {
const [r, ...fs] = [...f].reverse();
return [...fs].reduce((res, fn) => fn(res), r);
};