Map and filter arrays in a performant way with transducers in Typescript

We all ran into the use case where we have an array on which we want to :

1. filter elements
2. apply a transformation on each of the filtered elements

Consider the following example:

We have an array of numbers on which we want to double only the even numbers.

The easiest way of writing the later would be:

const double = (n:number) => n * 2
const isEven = (n:number) => n % 2 === 0
const doubleTheEven = (numbers:number[]) => numbers.filter(isEven).map(double)
doubleTheEven([1, 2, 3, 4]) // [4, 8] ✅

That works fine but is not awesome performance wise, since we are iterating through the whole array twice.

A way to get around that perf problem would be to write our doubleTheEven function with some imperative code like this:

const doubleTheEven = (numbers:number[]) => {
  const result = [];
  for (const number of numbers) {
    if (isEven(number)) {
      result.push(double(number));
    }
  }
  return result;
};

That fixes the performance issue but reduces our code quality and scalability (suppose we want to chain multiple maps and filters, and in any order we like).

Transducers are the tool that will allow us to get around that compromise 🚀

First lets explicit some definitions that we'll be using.

map is a method that takes a transformation of type:

type Transformation<T, W> = (a: T) => W; 
// takes a value of type T and returns of value of type W.
// our transformation "double" has type Transformation<number, number>

filter method takes a predicate:

type Predicate<T> = (a: T) => boolean;

reduce method takes a reducer:

type Reducer<A, C> = (acc: A, curr: C) => A;

A transducer takes a reducer and returns a reducer, thus has type:

type Transducer<A, C> = (r: Reducer<A, C>) => Reducer<A, C>;

We'll also need the compose function available in any FP library near you:

const compose = (...fns: Function[]) => (x: any) =>
  fns.reduceRight((y, f) => f(y), x);
compose(n => n * 2, n => n + 1)(2) // 6
compose(n => n + 1, n => n * 2)(2) // 5

Now let's get to work 🤓

We'll first need a reducer that takes a value and pushes it to the accumulator.

const pushReducer = (accumulator, current) => [...accumulator, current];

Naturally, since pushReducer doesn't do anything to the current value, when we reduce an array with pushReducer, we get back the same array.

[1,2,3].reduce(pushReducer,[]) // [1,2,3] ✅

(spoiler alert🚨: our transducers are going to tap into those values to transform or filter them before they get to the pushReducer 😉).

Remember how we said transducers take a reducer and return a reducer ?

We are going to apply transducers to pushReducer, and those transducers will do transformation or filtering.

Creating transducers for transforming

Let's write a function that takes a transformation, and returns a transducer that applies that transformation to the current value for the provided reducer:

const makeXfTransducer = (xf: Transformation): Transducer => reducer => (
  acc,
  curr
) => reducer(acc, xf(curr));

Let's apply it to double:

const doubleTransducer = makeXfTransducer(double);

So, when we apply doubleTransducer to pushReducer, we get back a reducer that does the same thing as pushReducer but with xf applied to curr.

Let's verify that:

const reducerThatDoubles = doubleTransducer(pushReducer);
[1, 2, 3, 4].reduce(reducerThatDoubles), []); // [2, 4, 6, 8] ✅

Creating transducers for filtering

We need need a similar function that handles filters and here it is:

const makeFilterTransducer = (pred: Predicate): Transducer => reducer => (
  acc,
  curr
) => (pred(curr) ? reducer(acc, curr) : acc);

Let's smoke test it:

[1, 2, 3, 4].reduce(isEvenTransducer(pushReducer), []); // [2, 4] ✅

Composing transducers

Now you probably saw this coming: we are going compose those transducers!

const doubleEvenReducer = compose(
  isEvenTransducer,
  doubleTransducer
)(pushToReducer);

[1, 2, 3, 4].reduce(doubleEvenReducer, []); // [4, 8] ✅

And there you have it 🎉

But wait, it's sort of a pain to have too explicit the use of the pushReducer everytime...

Let's write a more concise way of doing all this that we'll call into.
It has the following type and implementation:

type Into<A, C> = (t: A, x: Transducer<A, C>, i: A) => A;
// In our case A = number[] and C = number
const into: Into = (target, transducer, input) =>
  input.reduce(transducer(pushReducer), target);

And we see that everything works:

into(
  [],
  compose(
    isEvenTransducer,
    doubleTransducer
  ),
  [1, 2, 3, 4]
); // [4, 8] ✅

Implement transducers with Ramda

Obviously we invented nothing here and the Ramda library already provides all these utilities out of the box

  import { into, compose, map, filter } from "ramda";

  const input = [1, 2, 3, 4];
  const expected = [4, 8];
  const doubleTransducer = map(double);
  const isEvenTransducer = filter(isEven);
  into(
    [],
    compose(
      isEvenTransducer,
      doubleTransducer
    ),
    [1, 2, 3, 4]
  );

All code examples can be found here

Happy coding ! 💻

Comments

[Joachim]

Do you if it's possible to type makeXfTransducer in typescript?