What are transducers? Using transducers is easy enough—but how do they work underneath the hood?
This article explores transducers by ignoring transducers. Instead we will examine two ordinary functions,
filter. We’ll play with them and scrutinize them. And we’ll marvel at the power of higher-order functions as we apply abstractions. And perhaps, if we’re lucky, we’ll bump into transducers along the way.
And since we ignore transducers, you won’t need to know what transducers are to follow along. If you don’t know Clojure or a Lisp, this quick primer may help.
Power of reduce
You are probably familiar with
filter, and know that we can combine them together, like this:
A key insight, however, is that
filter can be defined using
reduce. Let’s implement the expression
(map inc (range 10)) in terms of
map-inc-reducer’s explicit use of
inc as its transformer. What if we extract that out and let the user pass in whatever function they want? We can define a new function that takes a transforming function like
inc and returns a new function.
map-reducer are called higher-order functions because they accept functions and return functions. Let’s play around:
Let’s also implement the expression
(filter even? '(1 2 3 4 5 6 7 8 9 10)) in terms of
Again, notice that
filter-even-reducer explicitly uses
even? as its predicate. As before, let’s extract that out and let the user pass in whatever they want.
We can even compose
The expression above is equivalent (ignoring vectors versus lists) to the expression below.
We see that with higher-order functions, we are able to define
filter in terms of
Both versions, however, required intermediate vectors—one for map and one for filter. One important property of transducers is that they should employ only one collection regardless of the number of transformations. How can we accomplish that?
Another step in abstraction
filter-reducer. Here they are again:
What do you observe?
conj is used in both of them. Why? What’s so special about it? Can we use other functions in place of
Well, notice that
input can be of any type. If
conj would not work here;
(conj 10 1) throws an error. Instead of
conj, we would want something like
(+ 10 1) makes sense.
We can say that
+ are both reducing functions. Reducing functions have the type
result, input -> result; they take a result and an input, and returns a new result. For example:
Now, instead of always using
filter-reducer, what if we let the user pass in whatever reducing function they want?
This will result in another higher-order function that takes our map’s transform function and filter’s predicate function, as usual. But we now will return a function that accepts a reducing function. Let’s use the names
filtering for our new functions.
And now let’s use them as before:
We see here that we can choose the reducing function. In this case, we choose
Arriving at transducers
Take note of the functions
((mapping inc) conj) and
((filtering even?) conj). Their types are
result, input -> result. We can test this:
This means that
((mapping inc) conj) and
((filtering even?) conj) are also reducing functions, just like
So what happens if we compose these two functions like this:
This is also a function. But what is its type? Go on, evaluate it.
It turns out, this function also has the type
result, input -> result. It is also a reducing function. This means that we can use it via
This is a bit messy, so let’s clean it up by using
comp instead. Recall that
(comp a b c d) returns the function
Here’s the cleaned up version, using
And what about something more complex:
But we were talking about transducers. Where are our transducers?
It turns out,
filtering are transducer-returning functions. The functions
(filtering even?) and
xform are the very transducers we were looking for.
Transducers are functions that accept a reducing function and return a reducing function. For example, the function
(mapping inc) is a transducer because it accepts a reducing function like
conj, and returns another reducing function, as we observed above. As Rich Hickey pointed out in Transducers are coming, transducers have the type
(result, input -> result) -> (result, input -> result)
Also observe that no intermediate collections are created when we evaluate
(reduce (xform conj)  (range 10)), other than the initial vector. This satisfies our goal of not allocating intermediate collections.
A more intuitive understanding
It may be difficult to understand why the
xform transducer works because it’s quite complicated. Let’s try to get a better understanding. Here’s
xform as before:
Say we invoke this composed function by passing in some reducing function, perhaps our favorite,
conj. This would be passed to the transducer
(mapping inc), and we would have
((mapping inc) conj). We know that this returns another reducing function. This new reducing function is then passed into the function
(mapping square), which is another transducer. Naturally, this returns another reducing function. And we do this all the way to the first transducer in our composition,
This means that when we give a reducing function to
(xform conj), we get back a function that will apply the left-most reducing function first, then down the stack until the last reducing function,
conj, is applied to the current result and input.
Imagine this transducer is being used in some reduce function, and we have so far collected in our results the vector
[1 5 17]. Say the current input in question is
12 is even, it will pass the first filter. Instead of terminating early and returning the current
result, the first filter will call its reducing function, passing in
[1 5 17] and
12. In this case, the reducing function is the “rest” of the transformation, which is the second filter
#(< % 10). Since
12 fails the second filter, the third reducing function is not called, and the result-so-far
[1 5 17] is returned.
But if the input in question is
6, it would pass both filters and arrive at the mapping transforms, which will transform
37. We then pass this input to the final reducing function,
conj, which will join
[1 5 17] with the new value
Being able to compose transducers is important. We see that it’s quite simple to do, and that ordinary functions power all of it.
Transducers in core.async
Another major selling point of transducers is that a transducer can work across core.async channels. For example, we should be able to take our
xform transducer and use it to filter and transform items in a channel.
Using Clojure’s transducer library:
(defn square [x] (* x x)) (def xform (comp (filter even?) (filter #(< % 10)) (map square) (map inc))) (def my-chan (async/chan 1 xform)) ; Waiting for an item to print... (async/take! my-chan println) (async/put! my-chan 3) ; nothing printed to screen, since 3 is not even (async/put! my-chan 4) ; "17" printed to screen, since 4 is even and less than 10
How do transducers work across core.async channels?
First, note that channel buffers are linked lists underneath (in fact,
java.util.LinkedLists). When you put an item into a channel, the internal helper method
add! is called to add your item into the buffer.
But if a transducer
xform is supplied, core.async will use
add! as the reducing function passed into
This means that any item put into a channel will first be transformed by our transducer. And if the transducer filters out an item (e.g. due to
(filter even?)), then the final reducing function
add! is never called. Thus the item is never added to the channel’s buffer and no takers ever see it.
The pertinent code can be found in the core.async sources, here.
We’ve come a long ways. We started with regular
filter and observed how they can be implemented using
reduce. We then abstracted our reducing functions until we found ourselves with transducer-building functions,
By building, analyzing and using transducers, I hope that you gained a better understanding of how they work. They are, after all, just functions.
If you’re interested in learning more, I encourage you to tackle the problems below. Solutions can be found here.
transduce helper function
Right now, our use of
reduce is a bit clunky. Write a function
transduce that will allow us to use transducers like this:
The Caesar Cipher
In our examples above, we used
+ as reducing functions. Let’s write a more complex one.
Given a string, use transducers to:
- Filter out vowels and non-ASCII characters
- Filter out upper-case characters
- Rotate all remaining characters via a Caesar cipher,
- And reduce the rotated characters into a map counting the number of occurrences of each character.
mapcatting, a function that returns a
mapcat (no transducers):
The transducer should work like this:
taking, a function that returns a
Note that you may need to keep some state for this one.