Transducers: Supercharge your functional JavaScript

This is the first in a series of posts on functional programming in JavaScript. My goal is to make these ideas more accessible to all levels of programmers. Feedback about style, content, etc., would all be greatly appreciated.

One thing that perplexed me early on in my functional programming days was the concept of transducers. I spent a lot of time Googling and found some great articles that went deep into the theory and the underlying mechanics. However, the practical use of them still seemed a bit out of reach. In this post I'll attempt to explain transducers in a more understandable way and hopefully give you the confidence to use them in your functional JavaScript. While this article attempts to make transducers more accessible, you will need to have some basic knowledge of functional programming in JavaScript. Specifically, you should know about function composition and iterator functions like .map(), .filter(), and most importantly, .reduce(). If you are unfamiliar with these concepts, go get a grasp on them first.

NOTE: I'm using the Ramda functional programming library for most of the examples in this post. Ramda provides us with standard functions like compose() as well as provides easily composable versions of functions like map(), filter(), etc.

What is a transducer?

According to the Ramda documentation, a transducer is "a function that accepts a transformer and returns a transformer and can be composed directly." Okay, so what's a "transformer" then? The documentation goes on to define a transformer as "an object that provides a 2-arity reducing iterator function, step, 0-arity initial value function, init, and 1-arity result extraction function, result." Simple, right? No, not really. If you are just as confused as I was, keep reading.

Rather than keep you in suspense, I'll just tell you that map() and filter(), for example, are transformers. There's a lot to breakdown in that definition above, and in my opinion, it isn't very clear. So instead, let's start by explaining what a transducer actually does.

What does a transducer do?

A transducer takes an object, such as an array, and iterates through each value, manipulating them with a composition of transformer functions. Let's say we have the following array of Autobots:

javascript
let autobots = ['Optimus Prime','Bumblebee','Ironhide','Sunstreaker','Ratchet']

Now we want to filter out values that don't contain the letter 'r', then uppercase and reverse each value. We could easily do this with a simple function composition.

javascript
const R = require('ramda') // Ramda functional library

let autobots = ['Optimus Prime','Bumblebee','Ironhide','Sunstreaker','Ratchet']

// Filter for autobots that contain 'r', uppercase, then reverse
let transform = R.compose(
  R.filter(x => /r/i.test(x)),
  R.map(R.toUpper),
  R.map(R.reverse)
)

transform(autobots)
// => [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]

Or we could do this with a transducer using Ramda's transduce function:

javascript
const R = require('ramda') // Rambda functional library

let autobots = ['Optimus Prime','Bumblebee','Ironhide','Sunstreaker','Ratchet']

// Filter for autobots that contain 'r', uppercase, then reverse
let transform = R.compose(
  R.filter(x => /r/i.test(x)),
  R.map(R.toUpper),
  R.map(R.reverse)
)

// Transduce the autobots array
R.transduce(transform, R.flip(R.append), [], autobots)
// => [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]

We get the same exact result (in this situation), but something very different and very powerful is happening under the hood. In the first example, the entire list was transformed at each step. This means that we had to iterate over the list three times. However, in the second example where we used the transducer, we only had to iterate over the list once!

This makes transducers much more efficient, especially with large lists that require several transformation steps. A transducer will loop over the list and then perform all the transformations at once on each value. The transformed value is then passed back to the main reducing function.

Don't worry if you still don't quite get it. We'll dig deeper so we can really understand what's going on.

Understanding the `transduce()` function

The transduce function is really just a reduce function with an additional argument upfront. If we rewrote the reducing part using reduce, it would look like this:

javascript
R.reduce(R.flip(R.append), [], autobots)
// => [ 'Optimus Prime', 'Bumblebee', 'Ironhide', 'Sunstreaker', 'Ratchet' ]

// Or with native .reduce()
autobots.reduce(R.flip(R.append), [])

That reduce function iterates the elements of our autobots array and appends them to the accumulator. Remember that reduce takes an iterator function that receives two values (the accumulator and the current value), an initial value for the accumulator, and the list it is iterating over. In our case above, we are using R.flip(R.append), which takes an element to append to the list AND the list to append to. Since reduce sends the accumulator as the first argument (the list), we use the R.flip() function to swap the argument order. This is equivalent to:

javascript
(acc,item) => acc.concat(item)

// OR

(acc,item) => R.append(item,acc)

When we use transduce(), we are passing each item from our list into our transformation function before passing it to our reducing function. So basically, transduce is just a way for us to transform items while reducing them. We are, in fact, transducing!

Transforming our data

Let's take a closer look at our original transform function.

javascript
let transform = R.compose(
  R.filter(x => /r/i.test(x)),
  R.map(R.toUpper),
  R.map(R.reverse)
)

If you're familiar with composing functions, then this should be easy to understand. Ramda's implementation of compose is similar to other libraries' implementations. The result of each function is passed to the next function, which creates a data pipeline. You may have even noticed that with Ramda, we can pass pretty much any value directly to transform and get back a result with our transformed values. For example:

javascript
// An array
transform(['Optimus Prime','Bumblebee','Ironhide','Sunstreaker','Ratchet'])
//=> [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]

// A string
transform('Optimus Prime')
// => [ 'R' ]

// Even an object
transform({ leader: 'Optimus Prime', bodyguard: 'Ironhide', medic: 'Ratchet' })
// => { leader: 'EMIRP SUMITPO', bodyguard: 'EDIHNORI', medic: 'TEHCTAR' }

This has to with Ramda's implementation of map() and filter(), since it will automatically convert different datatypes into functors (objects that can be mapped over). While this is interesting, it still doesn't explain exactly how the data is being processed.

Let's use Ramda's tap() function to peek inside our data pipeline.

javascript
let transform = R.compose(
  R.tap(x => console.log('--------TOP---------')),
  R.tap(x => console.log('FILTER:',x)),
  R.filter(x => /r/i.test(x)),
  R.tap(x => console.log('UPPER:',x)),
  R.map(R.toUpper),
  R.tap(x => console.log('REVERSE:',x)),
  R.map(R.reverse),
  R.tap(x => console.log('-------BOTTOM-------'))
)

I've added some logging to our transform function so we can see how the data is being processed and in what order. Order matters sometimes, so it is important that we consider how our functions are used. compose() processes in reverse order (bottom-to-top or right-to-left), so if we run this function directly with our autobots array, we get the follow:

javascript
let autobots = ['Optimus Prime','Bumblebee','Ironhide','Sunstreaker','Ratchet']

transform(autobots)

// -------BOTTOM-------
// REVERSE: [ 'emirP sumitpO', 'eebelbmuB', 'edihnorI', 'rekaertsnuS', 'tehctaR' ]
// UPPER: [ 'EMIRP SUMITPO', 'EEBELBMUB', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]
// FILTER: [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]
// --------TOP---------

// => [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]

There are a couple of really interesting things to notice here. First of all, you can see that the functions in our composition were processed from bottom-to-top (or right-to-left). And second, the console logs show that each step transformed the entire list. Which means that the list was iterated over three separate times.

Now let's transduce our array with the same function and see what happens.

javascript
let autobots = ['Optimus Prime','Bumblebee','Ironhide','Sunstreaker','Ratchet']

R.transduce(transform, R.flip(R.append), [], autobots))

// --------TOP---------
// FILTER: Optimus Prime
// UPPER: Optimus Prime
// REVERSE: OPTIMUS PRIME
// -------BOTTOM-------
// --------TOP---------
// FILTER: Bumblebee
// --------TOP---------
// FILTER: Ironhide
// UPPER: Ironhide
// REVERSE: IRONHIDE
// -------BOTTOM-------
// --------TOP---------
// FILTER: Sunstreaker
// UPPER: Sunstreaker
// REVERSE: SUNSTREAKER
// -------BOTTOM-------
// --------TOP---------
// FILTER: Ratchet
// UPPER: Ratchet
// REVERSE: RATCHET
// -------BOTTOM-------

// => [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]

Whoa, that's a lot different! The functions are now processing top-to-bottom (or left-to-right). You can also see how each value in our array is being passed through all three transformers before moving on to the next value. This shows us that the list is only being iterated over one time! This means we can be hella-efficient when working with lists of all sizes. Pretty cool.

You may be asking yourself, "It can't be this easy, right?" To that I say, "it depends." If you use a library like Ramda, then you can probably start using transducers right now with your new found knowledge. However, if you'd like to learn more about the dark magic being used to conjure such sorcery, read on.

Looking under the hood

Earlier we defined a transducer as "a function that accepts a transformer and returns a transformer and can be composed directly." We now have a better understanding of transformers (e.g. map and filter), but up until this point, we've only been passing arrays into our transform function and getting an array back. That's because our transform function acts as a transformer when called directly, but when called through the transduce function, it acts as a transducer!

The transduce function passes our transform function a transformer rather than the value from the list. Let's create a new transform function with some logging so we can see what is actually going on.

javascript
let autobots = ['Optimus Prime','Bumblebee','Ironhide','Sunstreaker','Ratchet']

// Log what is passed into our transform function and what it outputs
let transform = val => {
  console.log('in:',val)
  let out = R.map(R.toUpper,val)
  console.log('out:',out)
  return out
}

// Run transform directly
transform(autobots)
// in: [ 'Optimus Prime', 'Bumblebee', 'Ironhide', 'Sunstreaker', 'Ratchet' ]
// out: [ 'OPTIMUS PRIME', 'BUMBLEBEE', 'IRONHIDE', 'SUNSTREAKER', 'RATCHET' ]

// Run through transduce
R.transduce(transform, R.flip(R.append), [], autobots)
// in: XWrap { f: [Function] }
// out: XMap { xf: XWrap { f: [Function] }, f: [Function: f1] }

As you can see, when passed directly, the input is the array and the output is an array. When passed with transduce, however, the input is an object and the output is an object. That's because there's one little thing I haven't told you yet. Ramda's implementation of map (along with many of its other transformer functions) act as transducers when you pass a transformer in the list position. This means that our transform function only acts as a transducer because of Ramda's implementation. Which is one of the reasons it is so powerful, because most of the heavy lifting is done for us.

While the input and output from transduce above look like objects (which is specific to Ramda's implementation), underneath they are technically accepting and returning transformer functions. Let's get crazy and write our own transducers to go really deep into the weeds.

Building our own transducers

One more time, a transducer is "a function that accepts a transformer and returns a transformer and can be composed directly." Let's start by writing our own transformer. Even though transformers have that lengthy definition (I'm not even going to repeat it), think of them as just reduce() functions with a specific purpose. Let's write our own map() function using reduce() as an example. map() applies the provided function to every item in the supplied list and returns the transformed list.

javascript
// Takes two arguments, a function and a list (2-arity)
let map = (fn,list) => {
  return list.reduce( // reduce the list
    (acc,item) => { // each item gets passed with an accumulator
      return acc.concat( // append to the accumulator
        fn(item) // the item is passed to the provided function
      )
    },
    [] // inital accumulator value (empty array)
  )
}

// Or without all the extra space:
let map = (fn,list) => list.reduce((acc,item) => acc.concat(fn(item)),[])

Now we can use this just like Ramda's map() function.

javascript
map(R.toUpper,autobots)
// => [ 'OPTIMUS PRIME', 'BUMBLEBEE', 'IRONHIDE', 'SUNSTREAKER', 'RATCHET' ]

Awesome! This works just as expected. Now let's turn this into a transducer. First we have to know a little bit about currying, or partially applying functions. You're probably most familiar with passing in all the arguments at the same time, like this:

javascript
let test = (arg1, arg2) => {
  console.log(arg1 + arg2)
}

However, we can apply some old school currying to this function by splitting the arguments with a fat arrow:

javascript
let test = arg1 => arg2 => {
  console.log(arg1 + arg2)
}

Now we can call this function with just one argument and it will return our second function. We can then call our second function and still use any arguments that have already been partially applied:

javascript
let fn = test('foo')
// arg2 => {
//   console.log(arg1, arg2)
// }

fn('bar')
// => foobar

// Or in one step by calling the returned function
test('foo')('bar')
// => foobar

Make sense? Great! In order for this to be a transducer, it needs to accept a transformer and return a transformer. So instead of passing our new map() function an array as the second parameter, let's pass it a transformer instead. To do this, we need to refactor our map() function with some currying. Then we need to return a transformer (remember, just a specific implementation of reduce).

javascript
let _map = fn => transformerFn => {
  return (acc, item) => transformerFn(acc, fn(item))
}

Take a minute to study the code above if you need to. Our new _map() function takes a function (like R.toUpper) as its first argument. This will then return a new function that expects one argument that is a transformer function. When we pass it a transformer function, it returns a new transformer that applies the transformer we just passed it. We now have a transducer! This also means that we can compose as many of these transducers together as we want.

Let's write our own filter() function so we can duplicate our original transform function.

javascript
let _filter = predicate => transformerFn => {
  return (acc, item) => predicate(item) ? transformerFn(acc, item) : acc
}

Here we did the same thing as our _map() function, except our first argument is a predicate that should return true or false. If the item passes the test, the transformerFn is applied, otherwise just the accumulator is returned.

Now we can refactor our transform function with our new custom transducers.

javascript
let transform = R.compose(
  _filter(x => /r/i.test(x)),
  _map(R.toUpper),
  _map(R.reverse)
)

And then call it by passing a transformer as the first argument (we'll reuse our R.flip(R.append)). Since this will return another transformer, we can pass this into a reduce() function as the iterator function and process our list:

javascript
R.reduce(transform(R.flip(R.append)),[],autobots)
// => [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]

// Or using native reduce
autobots.reduce(transform(R.flip(R.append)),[])
// => [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]

Final thoughts

If you're still reading this, congratulations! These aren't easy concepts. Before we go, there are two more things that I want to show you. First, let's refactor our initial transformer so that we can see what is getting returned from our transducer. We'll use the Rambda version for clarity.

javascript
R.transduce(transform, (acc,item) => {
  console.log('transformed:', item)
  return R.append(item,acc)
}, [], autobots))

// transformed: EMIRP SUMITPO
// transformed: EDIHNORI
// transformed: REKAERTSNUS
// transformed: TEHCTAR

// => [ 'EMIRP SUMITPO', 'EDIHNORI', 'REKAERTSNUS', 'TEHCTAR' ]

Above we replaced our R.flip(R.append) transformer with one that logs the item that is being appended to the accumulator. As you can see from this example, we are only iterating the list one time.

Second, I want to quickly address processing order of composed functions. When we used our original transform function as a transformer, the compose method processed in reverse order, as we would expect. However, when used as a transducer, it processes from the beginning. This is by design. The compose function takes each function and wraps it in the next function. For example:

javascript
compose(fn1,fn2,fn3)(x) = fn1(fn2(fn3(x)))

When called with argument x, that argument is passed into fn3, the result of which is passed into fn2, and the result of that is passed into fn1, hence the reverse order of processing.

However, when we compose transducers, we are returning functions, not values. Taking our transform function as an example, we pass our transformer into _map(R.reverse) first, which returns a transformer and passes that to _map(R.toUpper), which returns and passes a transformer to our _filter function, which returns a transformer. Now when we execute this, the returned function from _filter is called first, then _map(R.toUpper) and so on, which is the opposite of how compose appears to process functions.

This is important to keep in mind when writing transducers. A silly, but illustrative example would be when you only wanted words that start with a certain letter and then needed to reverse the word. If the order is incorrect, you may be reversing the word first before checking for the first letter (which would now be the last).

Where do we go from here?

I know this post was very long, but I hope you now have a much better understanding of what transducers are, how they work, why they work, and what you can do with them. If you'd like to learn more about transducers, definitely check out the Ramda library. Ramda also has several other functions, like take, without, countBy, etc., that all act as transducers if passed a transformer. This makes writing complex transducers much easier.

You can also check out https://clojure.org/reference/transducers for some more of the theory behind transducers.

Tags: #nodejs, #javascript, #ramda, #functional-programming, #transducers

Transducers: Supercharge your functional JavaScript