Everything Reduced: Transducers in Javascript
Ever used lodash to deal with “Collections” or “Lists”? Ever had to chain a whole bunch of list-y, collection-y operations together? Great! Stop it.
Oh… don’t actually stop, lodash is great! But stop for a moment, and let’s see if we can build up the guts of almost all of that collection/list functionality, replace the .chain().op().op().op().value() syntax with something more pointfee and functional, and learn about a powerful abstraction we’ve been missing out on while we’re at it: transducers.
As usual, we’ll get to all that in exactly the roundabout way that befits really understanding something. And we can start by contemplating the glory of what you can do with a just single, simple operation: reduce.
If we’re talking about Arrays, then Array.reduce is an operation that can take any iterable (i.e. often an Array but really anything that can give you a set of values in order) and give you some output or any type (sky’s the limit, including a new Array!) based on running a particular function over each item.
Here’s a quick recap of how your basic reduce operation works:
The really important bit there is accFn. I’ve talked before about the power of boiling code down to simple, pure, unary functions (one input, one output). But the thing labeled accFn is a slightly different beast: it describes how two things (in the form of two arguments) can be combined into one result. When the basic type of the first argument is the same thing as the type of the result, we have ourselves what we can justly call a reducing function.
(a, b) → a or, in curried notation: a → b → a
It’s important that the first argument and the output are similar (and almost always that means: they are of the same type) precisely because reduce is built to pipe that output right into the first argument of the same function again on the next loop, this time pairing it with the next item. That can only reliably work over multiple iterations if the end result is always the same.
Indeed, working over a list of things by using reducing function is, in some ways, still pretty similar to using compose: it’s as if a single callback could be repeated over and over as many times as there were items in a list, pre-filled with each individual item in turn (taking us back to the land of unary functions where compose makes sense). Here, for instance, is a simple reduce operation artificially modeled as a composition:
When some starting point is passed into the completed composition function there, it just flows through the pre-configured chain to generate the final, accumulated result we expect. Building your own actual version of reduce isn’t that hard, but we can save that for later: this time around we’re just getting a sense of what it can DO.
Speaking of which, you may have heard that almost any core iterative operation like mapping and filtering can be expressed in terms of reducing alone. It’s true! Let’s see exactly how that’s done, and where it takes us:
Here, we’ve simply created helper functions called mapper and filterer so that we can very explicitly express what it really means to map or filter over an Array. In each case, we can specify a custom transformer function (for mapping one value to another) or custom value-testing function (for filtering out values) and the result is a new function with the exact signature/arity of the final reducing function that we need to pass to reduce.
When we map, the transformer function gets each item in turn, modifies it somehow, and then adds that onto the accumulator to build up a new Array. When we filter, we’re merely deciding whether each item deserves to be added to the final, accumulated result at all. The transformer and test functions by themselves are deliberately pure and simple: they “know” nothing about the larger context they’re being used in. It’s the form of the reducing function that actually hooks them up such that they “map” or “filter.”
Seeing things expressed in this way is quite exciting, but we can go even further. We could, for instance, combine filtering and mapping into a single construct:
Now we can run both operations at once with only a single loop through the Array!
But as we look at mapperfilterer a bit more closely, it’s really not very flexible: what if what we really wanted was to filter the original values, not the transformed ones? Whelp, we have to rewrite mapperfilterer to test first, then transform, and maybe even call the flipped function filterermapper or something stupid.
Even if we were that stupid though, we’re not done being stupid yet because… well, what if we wanted to filter the original values, then map, and then filter again, but with the transformed values? Now we’re really in a pickle. filterermapperfilterer? Ug.
But it’s worse still. We’ve baked Array.prototype.concat into this whole mess. What if we wanted to sum up a list of numbers instead? Or end up with a particular Object in the end, not an Array? There are lots of possible ways to “accumulate” a final result. Reduce is, essentially, an operation that is capable of iteratively transforming one type of thing into another. We need to expose that power, not restrict it.
So, back to the drawing board. Remember how nice & clean it was that each of our transforming/testing functions were super simple? Well, what we really need is a way to separate out all of the bits and pieces of this grand operation into fundamental parts so that we can mix and match as we please.
We’ll start with that baked-in concat operation. Let’s make it so that we can also specify concat or sum or whatever operation you please whenever you want to define a particular process of mapping or filtering:
Now we have functions that take a function, then return another function that then also takes a function, and then finally returns… a function… which we then intend to pass to… a reduce function. Er… well, I’ll admit that it all sounds a bit intimidating (even horrifying) when described that way. And yet… it’s actually pretty intelligible when used: there’s more flexibility and less magic. That, and we’re not quite done yet.
Because there’s something here that should strike you as very suspicious: the (vague) type-signatures of our “resultifiers” sum and concat. They’re both functions that take two arguments and then return a single result. Which is something we just talked about not so long ago. Aren’t those both… well… reducing functions?
Indeed they are, all by themselves:
Ok, but aren’t our mapping and filtering operations also ultimately returning reducing functions?
Yep: after first choosing a particular mapping or filtering logic, they each accept any reducing function and then return a new one, just with that mapping or filtering logic wrapped around it. We can unofficially think of that process as looking sort of like this:
(result → a → result:a) → (result → b → result:ab)
That is, we’ve transformed one sort of reducing function into another. We’ve transformed some reduces. We’ve… transduced!
Ok, so that’s nice and all, but so what? We’ve come an awful long way just to define a cutesy term, no?
Well, here’s the magic part: if the inputs and outputs of a transducer are the same sort of thing (a reducing function), that means we can take the output of any one and use it as the input of any other, right? And we can do that as many times as we want, in any order we want.
Which is all to say that transducers compose. Which is to say that just by fixing the “baked in concat” problem we’ve already achieved our original goal: the ability to map and filter (with specific mapping and filtering operations we can choose upfront and out in the open) as we please… in any order we please.
Holy buckets! Now, without a lick of imperative code or intermediate variables, we can spell out that we want to divide each item by three, and then, before moving on to the next item or adding it to the final result (by using concat in this case, but now we can easily sub in some other core reducing function if we want: it’s all explicit!), we can test to make sure it’s an integer. compose(aMapFn, aFilterFn) or compose(aFilterFn, anotherFilterFn, aMapFn, aThirdFilterFn), whatever!
And it all just works. It only loops through the Array once. It’s built out of tiny, intelligible parts that are individually easy to describe and reason about. And it’s immensely flexible: if we want to implement other sorts of transformations or filters, we can just add them into the composition chain.
All transducers really do is describe how a particular reducing function, no matter how complex, will be used (or, as we’ll see: not used) to create a final result. And that “description” is, itself, expressed as a reducing function that either some other transducer OR a final reduce operation can consume.
Better yet, transducers don’t “need to know” anything about what particular thing the inner reducing function they’re given actually does. That separation of concerns is especially important when, say, the reducing function created by a filtering transducer decides to return the unaltered accumulator value instead of ever using the reducing function that it was given. By doing so, it can essentially ignore all the other operations deeper in the chain, skipping right over to the next iteration. That’s remarkably efficient, especially when we’re working over huge lists and expensive transformations.
I’ll cover some of those other transformations, and some exciting use cases, in the next article. But, before we close out this one… we need to talk through the most peculiar feature of transducer composition: the order in which we must list transducers when we compose them.
We intuitively know that different orderings here can lead to different results (increment then filter vs filter then increment), so it’s important that we get this right. And indeed, composition runs right to left, right? Definitely. Always. So you might well assume that if we want to first increment all values in a list and then filter out any values that got too large, we’d compose(filteringOp, mappingOp).
And yet, the order that your list of composed transducers will actually run is left to right (same thing with Lenses, actually!) So it’s actually compose(mappingOp, filteringOp) that you want instead.
Why? Well… what do we actually pass into the composed chain of transducers? A reducing function of course: in the example case, concat.
In that case, according to the logic of composition (right=inner to left=outer) the last, rightmost function in the composition chain (filteringOp) is indeed the one that receives this concat function, just like how the rightmost function in a composition receives a value. But it then returns a function to the next step in the chain, not a value. So, working leftwards, the next link in our chain, mapping, gets that reducing function (exactly what was it was expecting): a filtering one that itself will use concat to return a result when passed an accumulator and an item. The mapping transducer will now, in turn, use the completed filtering reducing function (the one that now wraps concat) in some particular way to produce a result when it is passed an accumulator and an item.
Thus, when the final reduce operation runs and is first handed actual values (the accumulator and the item), the mapping operation was the last and outermost wrapper. So the mapping operation runs first.
There’s nothing weird or special about transducers (or Lenses) that makes them work this way. Composition is working as expected: it’s just a question of what is being composed, and what the 100% logical and expected structure of the resulting function is. We can see the same sort of thing even with the simplest possible case of composing functions that each return functions together:
Compare that to the case when we’re just composing simple functions: a value runs through each in turn, without any cascading configuration:
To put it all another way: in ordinary composition, functions enclose each other and then an initial value given to the innermost function explodes outwards, transforming the value at each layer. But here, the composition isn’t one of functions that return values, but of functions that return functions. So the initial outwards explosion, the thing that happens when compose is actually used, is actually an explosion of configuration. Then, when the full, multi-layered reducing function is run (repeatedly, I might add, since it’s a sort of callback function), the values are set to implode, working inwards. The dominoes are lined up right to left (the usual order of composition) and then knocked down left to right.
Phew.
We’ll look at some neat applications and more complex things in the next article.
In the meantime, as with Lenses, there are already a bunch of great, full-featured libraries out there that can help you, well, transduce, as well as larger functional libraries like Ramda.js which incorporate transducers into many of their api methods. The boilerplate we’ve built here has the virtue of being clean and simple (any tiny enough to incorporate into your work without any larger dependencies), but there are lots of other enhancements/subtleties to consider.
