Lambda Island

Transducers are a Clojure feature allowing you to write code that is efficient, reusable, and composable. They have been around for several years, landing first in Clojure 1.8, but even some experienced Clojure programmers are not yet reaping the benefits of their use. In this episode we’ll look at the problems that Transducers solve, and how you use them in practice.

Transcript

Transducers have a reputation of being complicated. I think this is unfair. Sure, writing your own transducers isn’t trivial, but I can demonstrate how to use them in under a minute.

Suppose I need all odd numbers from zero to twenty. I can do this with straightforward Clojure using filter

(filter odd? (range 20))
;;=> (1 3 5 7 9 11 13 15 17 19 ...)

You can think of filter as performing three steps. It unpacks the input collection, grabbing each element in turn, it then does its actual job of applying the predicate to test if the element should be filtered or not, and finally it adds the element to the output collection.

+---------------+   +-----------------+   +---------------+
| Unpack input  |==>| Check predicate |==>| Create output |
|  collection   |   |                 |   |  collection   |
+---------------+   +-----------------+   +---------------+

Now I’ll do the exact same thing with a transducer, I first change the call to filter to only take a single argument. When you call filter this way it returns a “transducer” which filters odd numbers. Pass the transducer and the collection argument to sequence, and you get the same result as before. A lazy sequence of all odd values in the given range.

(sequence (filter odd?) (range 20))
;;=> (1 3 5 7 9 11 13 15 17 19)

So filter has two versions, there’s the regular two-arity one which returns a collection, and one that only takes a predicate, and returns a “transducer”, but what is a transducer?

If you look at it you can see that it’s just a function, it’s a particular kind of multi-arity function that follows certain rules, but you don’t need to know all those details to be able to use them. All you need to know is that (filter odd?) encapsulates the ability to filter out odd values. It’s a neat self-contained building block. It doesn’t do anything on its own, instead you plug it into some other operation to do the work.

(filter odd?)
;;=> #function[clojure.core/filter/fn--5610]

sequence is one such operation, it takes an input collection, runs it through the transducer, and returns a lazy sequence of the result.

filter no longer knows or care about the input or output collection, it’s strictly focused on its core business: filtering values. The details of iterating over the input collection, and building up the output, are delegated to sequence.

+---------------+   +-----------------+   +---------------+
| Unpack input  |==>| Check predicate |==>| Create output |
|  collection   |   |                 |   |  collection   |
+---------------+   +-----------------+   +----+----------+
      ʌ                      ʌ                 ʌ
      |                      |                 |
      +------+-------------- | ----------------+
            /                |
   (sequence                 |
     (filter odd?) ----------+
     20)

Creating transducers generally follows the same pattern: you use collection functions from clojure.core, but leave off the final collection argument. All the typical collection operators like map, drop, take-while, or partition-by can return a transducer.

(map inc)                                      ;;=> #function[clojure.core/map/fn--5583]
(drop 5)                                       ;;=> #function[clojure.core/drop/fn--5642]
(take-while (partial > 23))                    ;;=> #function[clojure.core/take-while/fn--5634]
(partition-by #(Math/floor (/ % 7)))           ;;=> #function[clojure.core/partition-by/fn--8154]

There are also a few special functions which return a transducer without taking any arguments. These are (dedupe) and (distinct). They are functions instead of constants because they are stateful.

(dedupe)     ;;=> #function[clojure.core/dedupe/fn--7256]
(distinct)   ;;=> #function[clojure.core/distinct/fn--5297]

Finally there’s cat which is a transducer that concatenates sequences. cat is already itself a transducer, you don’t need to call it, just use the var directly wherever you would put a transducer.

cat
;;=> #function[clojure.core/cat]

(into [] cat (map range (range 5)))
;;=> [0 0 1 0 1 2 0 1 2 3]

What’s beautiful about the design of transducers is that you can stack them like legos using good old function composition, comp.

The result is once again a transducer. This way you can build up a complex operation consisting of several steps, and since the result is just a function you can pass it around, or store it for later usage.

One thing you do need to be aware of: normally with comp the first function is called last, so functions are actually run in reverse order. With transducers its the other way around: the resulting operation will call each transducer in source order, just like with a threading operator.

(comp
 (map inc)
 (drop 5)
 (take-while (partial > 23)))
;;=> #function[clojure.core/comp/fn--5529]

But unlike with a threading operator, the resulting operation is first class, it is itself a value. I can pass it around or assign it to a var, and then use it when needed.

(def complex-operation (comp
                        (map inc)
                        (drop 5)
                        (take-while (partial > 23))))

(sequence complex-operation (range))
;;=> (6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)

I could have done this with a threading operator as well, but There’s a functional difference between the threaded and transducer versions. When you thread these calls, then each of them will create a new sequence, which then forms the input for the next one. Those intermediate sequences are allocated, consumed, and garbage collected over and over again.

The transducer version processes the collection in a single pass, only building up a new sequence for the final result. There are no short-lived intermediate collections, which can be a big win for performance.

(->> (range)
     (map inc)
     (drop 5)
     (take-while (partial > 23)))
;;=> (6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)

Now that you know how to create and combine transducers, let’s look at some more ways you can use them.

sequence is fine for when all you need is a lazy sequence, but if you need a specific collection type like a set, vector, or map, then you can use into instead.

You probably already know the two-argument version of into, with a destination and a source collection. If you put a transducer in between then it’ll transform your source collection while building up the destination.

(into #{} (range 10))
;;=> #{0 7 1 4 6 3 2 9 5 8}

(into #{} (map inc) (range 10))
;;=> #{7 1 4 6 3 2 9 5 10 8}

This leads to some useful idioms, for instance you can transform sequences into maps by mapping over a function that returns key-value pairs, and using a map as the target collection.

(into {}
      (map (fn [i]
             [i (* i i)]))
      (range 10))
;;=> {0 0, 7 49, 1 1, 4 16, 6 36, 3 9, 2 4, 9 81, 5 25, 8 64}

It’s also a great opportunity to employ the lovely juxt function, the pinnacle of functional programming joy. Maybe throw in a comp or a partial while you’re at it.

This mapping from tea type to the length of the name clearly shows the superiority of Wulong Tea.

(into {}
      (map (juxt identity (comp count str))
      [:green :black :wulong])
;;=> {:green 6, :black 6, :wulong 7}

So far we’ve transformed collections into collections, but sometimes the final result you’re after isn’t a collection at all. Let’s consider this bit of code for a moment. The details don’t matter too much, but do notice that it ends with a call to (reduce +), so the result is just a single number.

As mentioned before doing it this way will create an intermediate collection for each transformation step. I deliberately used a pretty big collection here to demonstrate that those milleconds do add up.

(->> (range 1e7)
     (filter odd?)
     (map (partial bit-xor 42))
     (filter #(= 0 (mod % 11)))
     (remove #(= 2r1100 (bit-and % 2r1100)))
     (reduce +))
;;=> 1704542045459
;; "Elapsed time: 678.467931 msecs"

The transducer version of reduce is called transduce. You first pass it the transducer. I’m taking the exact transformation steps as before, and combining them with comp. After that comes the “reducing function”, + in this case, the same one you would pass to reduce, and then the input collection.

The result is the same, but this code is literally twice as fast as the threaded version. This shouldn’t be too surprising by now. The threaded version allocates four intermediate collections, which are then immediately used and discarded. The transduce function does none of that, it just runs over the input in a single pass, immediately calculating the result.

(transduce (comp
             (filter odd?)
             (map (partial bit-xor 42))
             (filter #(= 0 (mod % 11)))
             (remove #(= 2r1100 (bit-and % 2r1100))))
            +
            (range 1e7))

;; "Elapsed time: 339.195512 msecs"

These are the function signatures of transduce, you can pass it a starting value as with reduce, or just let it use the first item of the collection as the starting value.

The transducer argument is called xform here, which you read as “cross form”, because data is ran “across” the transducer. You’ll come across this name more often when looking at Clojure’s docs.

(transduce xform f coll)
(transduce xform f init coll)

There’s one more “transducing context” you should know about, and that’s inside a core.async channel. Core.async is Clojure’s implementation of “communicating sequential processes” or CSP, it allows you to set up channels for communicating between threads, including lightweight threads known as “go-blocks”.

Let me require clojure.core.async first, referring just what we need to create a channel, put some values onto it, and read them back.

This channel will be used to process log messages. The first argument to chan is an optional buffer size, I’ll give it a buffer size of 10 to prevent it from blocking. As a second argument you may put in a transducer. All values coming across the channel will be passed through this transducer. The one I have here remove all :debug messages.

Now put some values on the channel… and then read them out again. The debug message is gone.

Here you can see why transducers are truly remarkable. In this case there is no input or output collection, there are just values coming over a channel, and yet you can use these exact same transducers.

(require '[clojure.core.async :refer [chan >!! <!!]])

(def log-chan (chan 10 (remove #(= :debug (:level %)))))

(>!! log-chan {:level :warn, :message "this is a warning"})
(>!! log-chan {:level :debug, :message "this is a debug message"})
(>!! log-chan {:level :info, :message "this is informational"})

(prn (<!! log-chan))
(prn (<!! log-chan))

;;=> {:level :warn, :message "this is a warning"}
;;=> {:level :info, :message "this is informational"}

I hope you’ve become convinced of the usefulness of transducers. I promise once you start adding them to your toolbox you’ll find uses for them everywhere. I can’t count the times I found that code was considerably cleaned up by switching it to transducers. The extra performance and flexibility are just icing on the cake.