fbpx Skip to content

Aquent | DEV6

Transducers to Compose Fast Map/Reduce Functions

Written by: Peter Wang

The Problem

When dealing with arrays in JavaScript nowadays, we are used to using Array’s built-in methods like `map`, `filter`, `reduce` instead of loops. One of the benefits of these methods is that they are chainable.

[1,2,3,4].map(num => num * 2).filter(num => num % 2 === 0)

While these methods are chained with each other beautifully, there is one problem, which is also the reason why it’s chainable, that is, each operation produces an intermediate array that is being operated on by the next method. This is not a problem when we are dealing with a small list of items and efficiency isn’t a concern. But when we have a huge list of items time and efficiency could be a big problem if we have to loop through the list multiple times. One thing we can do is go back to the good old for loop, but then we have to give up this nice declarative style and implement looping imperatively. Wouldn’t it be great if we can still use this declarative approach and compose our operations in some way and at the same time only go through the array once?

Reducers

To solve this problem, we have to take a look at what a reducer really is. A reducer is just a function that takes an accumulation and a value and returns an accumulation.

const reducer = (accumulation, value) => {
  // returns a new accumulation
  return accumulation + value
}
reducer(10, 5) // 15
 
reducer('Hello', ' world') // Hello world

We often use reducer in conjunction with the reduce method on Array, like this:

[1, 2, 3, 4, 5].reduce(reducer, 0); // 15     
['Hello', ' World'].reduce(reducer, '') // Hello World

It’s important that we understand that reducer is just a function that we pass into the reduce method. Reducer function itself is not coupled with iteration. In fact, we can call the reducer over and over again manually like this:

const num = reducer(10, 5) // 15
const num2 = reducer(num, 5) // 20

Another important thing to note is that the type of the seed value we pass into the reduce method should be the same type as the return value of the reducer.

Transformers

A transformer is a function that takes a value and returns a transformed value. This can be easily demonstrated in the following example:

const toUpper = str => str.toUpperCase()
const shout = str => `${str} !!!`
 
toUpper('hello') // HELLO
shout('world') // world !!!

One nice thing about transformers is that they are composable. What I mean by composable is this:

const scream = str => shout(toUpper(str))
scream('I am screaming') // I AM SCREAMING !!!

Here, scream transformer is just the composition of shout and toUpper transformers. And the reason we can compose these transformers is that they don’t care how the value is being passed. toUpper transformer doesn’t care if it’s a string literal or a function that produces a string or a function that returns a function that produces a string, as long as it’s a string that’s all it matters.

Rewrite map and filter as reducers

Now let’s first define some transformers:

const doubleTheNumber = num => num * 2;
 
[1,2,3,4].map(doubleTheNumber); // [2, 4, 6, 8]
 
const doubleTwice = num => doubleTheNumber(doubleTheNumber(num));
 
[1,2,3,4].map(doubleTwice);  // [4, 8, 12, 16]

When using the built in map operation, we pass a transformer which describes our transformation. The logic for how these new values are added into the resulting array is abstracted away from us. This is a great thing since we only care about how the transformation happens. Note that we composed `doubleTheNumber` to make the `doubleTwice` transformer.

Now, let’s see if we can extend this and add in a filter operation. Let’s create an “even only” predicate that’s going to take a number, but it’s only going to return true if the number is even.

const evenOnly = num => num % 2 === 0;

Now, let’s try and compose this with double the number.

const doubleAndEven = num => doubleTheNumber(evenOnly(num))
[1, 2, 3].filter(doubleAndEven) // 2

Well this is not going to work because `evenOnly` returns a boolean while `doubleTheNumber` takes a number. We’ve got a problem here. The reason is that the built-in map() method takes a transformer, and filter is a predicate (a function that takes a value and returns a boolean).

Apparently, Array’s built in reduce method can solve the problem. Now let’s reimplement map()on Array using reduce():

const myMap = (xf, arr) => {
  return arr.reduce((accumulation, value) => {
    accumulation.push(xf(value));
    return accumulation;
  }, []);
}

Here we take xf(short for transformer function) and an array, then return the result of applying that function on the given array. In the reducer function that we pass in to reduce(), we just push the result of the transformer (xf) call on the value. Now we can use map like this:

myMap(doubleTheNumber, [1,2,3,4]); // [2, 4, 6, 8]

Let’s do the same to filter:

const myFilter = (predicate, arr) => {
  return arr.reduce((accumulation, value) => {
 
    if (predicate(value)) accumulation.push(value);
    return accumulation;
 
  }, []);
};

The only difference is that we are passing a predicate and using it to determine when to push the value to the accumulation.

myFilter(evenOnly, [1,2,3,4]); // [2, 4]

Create map and filter transducers

We created map and filter functions based on reduce, but we still can’t compose them together. Let’s add more abstractions.

The first abstraction we want to do is a decomposition, where we remove the dependency on this array. We want this whole map function to be a reducer we can post to reduce. Instead of returning the result of this whole reduction, we just want to return the actual reducer.

const myMap = xf => {
  return (accumulation, value) => {
    accumulation.push(xf(value))
    return accumulation
  }
}

And we can call map like this:

[1, 2, 3, 4].reduce(myMap(doubleTheNumber), []); // [2, 4, 6, 8]

Same to the filter:

const myFilter = predicate => {
  return (accumulation, value) => {
 
    if (predicate(value)) accumulation.push(value)
    return accumulation
 
  }
 
}
[1, 2, 3, 4].reduce(myFilter(evenOnly), []); // [2, 4]

We can chain the two reduce functions together:

[1, 2, 3, 4]
  .reduce(myFilter(evenOnly), [])
 
  .reduce(myMap(doubleTheNumber), []) // [4, 8]

Our goal here is to compose the map and filter functions and only run reduce once. Let’s see if we can solve that by hard-coding the map operation into the filter function.

const filterTheDoubles = predicate => {
  return (accumulation, value) => {
 
    if(predicate(value)) {
      return myMap(doubleTheNumber)(accumulation, value)
 
    }
    return accumulation
  }
}

Here we replaced the push call with map call. Let’s try calling filterTheDoubles on the array:

[1, 2, 3, 4]
 
  .reduce(filterTheDoubles(evenOnly), []) // 4, 8

Now we go through reduce once but we hard coded the map call into the filterTheDoubles function. Obviously, we don’t want to hard code this map logic in it. In fact, if we take a closer look at the map call inside `filterTheDoubles`, we can see this is just a reducer, so we can take another parameter and add another level of currying:

const myFilter = predicate => reducer => {
  return (accumulation, value) => {
 
    if(predicate(value)) {
      return reducer(accumulation, value)
 
    }
    return accumulation
 
  }
}

Now we can just call reduce like this:

[1, 2, 3, 4]
  .reduce(myFilter(evenOnly)(myMap(doubleTheNumber)), []) // 4, 8

Ok now let’s talk through this. Our filter function now takes a predicate, which determines the logic for how you want to filter. It then takes the inner reducer, which decides how the value should be built up. Once you’ve called this filter function twice, you’re left with the reducer that you’ve been able to customize with both a filtering logic and the inner reducer that decides how the values should interact with the accumulation. Here we’ve got our first transducer. It’s a function that encapsulates some reducing behavior — in our case it’s the filtering logic — that lets the function consumer decide how the results should be built up by being able to supply this inner reducer.

Now that we have our filter transducer, let’s do the same thing to map and create our map transducer:

const myMap = xf => reducer => {
  return (accumulation, value) => {
 
    reducer(accumulation, xf(value))
    return accumulation
 
  }
}

Usage of transducers

Now that we understand that transducers are nothing more than functions that decorate reducers in different ways. They enable natural composition, since they all return reducers with the same signature. Let’s see how we can use them. First, we need to create our own transduce function to be able to use transducers, just like reduce function using reducers. This is how we can define the transduce function:

const transduce = (xf, reducer, seed, collection) => {
 
  const transformedReducer = xf(reducer);
  let accumulation = seed;
 
  for (const value of collection) {
    accumulation = transformedReducer(accumulation, value);
 
  }
  return accumulation;
 
}

And let’s use `compose` function from Ramda.

import { compose } from 'ramda'
const toUpper = str => str.toUpperCase();
const isVowel = char
   => ['a','e','i','o','u','y'].includes(char.toLowerCase());
 
transduce(
 
  compose(map(toUpper), filter(isVowel)),
  (str, char) => str + char,
 
  '',
  'peter',
 
); // ‘EE’

Here I am not going to explain why we implement transduce function like this and how we can improve it as our goal for this post is to understand the fundamental concept of transducers. If you are interested in this topic there are a few JavaScript libraries you can explore. Please check out [transducers.js]( https://github.com/jlongster/transducers.js?files=1 ) or [ramda.js]( https://ramdajs.com ) for more information about how you can use transducers in a performant way.

Conclusion:

Transducers are a great technique to deal with large datasets. Having a fundamental understanding of transducers enables you to work on large datasets in an efficient way.