Table of Contents

• How composing transducers is like the ->> macro
• Ok so what is the problem?
• How it actually works
• Takeaways from all this
• Resources

I’ve read through quite some articles and guides regarding Clojure’s transducers, but none address in details why the behaviour of comp-ing transducers is akin to that of a thread-last (a.k.a. ->>) macro⁴.

Keep in mind that I am not going to explain how transducers work, and you should be familiar with it and its nomenclature (i.e. xform, reducing function…). I recommend the amazing article “Grokking Clojure transducers” by Eero Helenius.

How composing transducers is like the ->> macro

What I mean by “behaves like the thread-last macro” is, given an xform

(def xf                                                             
  "Example xform that filters odd numbers and then increments them."
  (comp (filter odd?) (map inc)))

if we use this in any of the functions that may take an xform as argument (e.g. into, transduce, etc), we will have a result that has filtered all of its odd values and incremented them by one. That is

(def nums
  "The best numbers."
  [0 1 2 3 4 5 6 7 8 9])

(into [] xf nums)                       ; => [2 4 6 8 10]

Now note that the result of using such xform is the same as if we had done it like:

(->> nums
     (filter odd?)
     (map inc))                         ; => [2 4 6 8 10]

Ok so what is the problem?

That sounds reasonable, right? That’s what you read on the Clojure reference for transducers, on the article I have linked before, so what’s the big deal?

It might not look like so, but that is a bit counter-intuitive if you understand how comp composes functions. You see, in Clojure, (comp f g), where f and g are functions, is the “same” as doing \(f \circ g\) in mathematics, which, if you’re not familiar with this notation, means that given an input x (of the appropriate type, though we are leaving types on the side for now), \((f \circ g)(x) = f(g(x))\), i.e., in Clojure-speak, (= ((comp f g) x) (f (g x))) ;; => true.

So, as you can see, the composition happens from right-to-left, so the function on the right-most position of the comp call is called first, and the result of calling it with the input is passed as the input to the next function to its left and so on and so forth.

Given this brief explanation of composition of functions in Clojure, lets get back to that previous xform. Let’s try and unwrap what I, intuitively – and I suppose many of you reading this – think is happening on that into execution we had setup before. Note that some of these lines aren’t valid Clojure code (namely steps 2 and 3).

(into [] xf nums)                                    ; 1
(into [] (xf nums))                                  ; 2
(into [] ((comp (filter odd?) (map inc)) nums))      ; 3
(into [] (filter odd? (map inc nums)))               ; 4
;; black magic...
(conj (conj (conj (conj (conj [] 2) 4) 6) 8) 10)     ; => [2 4 6 8 10]

A couple of things to unpack here:

1. In the final step we have calls to conj because into returns “all of the items of from-coll conjoined”, according to its docstring.
2. In step 4 we are mapping before filtering, but that’s not how it works, we should be filtering the odd numbers and then mapping on those.
3. This assumes that (map inc) (and (filter odd?), of course) returns a function similar in functionality to what

(partial map inc)

would, which looks, naming of the argument aside, like

(fn [coll] (map inc coll))

But that’s not exactly what is happening as we will see…

How it actually works

Now that we’ve stablished how comp works and the intuitive way I thought transducers did its work, we are going to explore how it actually does it.

I know, I know, it was a kinda dumb to think that it would work like that, but I couldn’t wrap my head around any other way of this playing out! It also should be obvious if you’ve read the article I first mentioned, since the author guides us into constructing our own transducer-like functions, but I knew how both ends of the spectrum worked (transducers and composition of function), I just couldn’t piece both together into a cohesive thing.

The biggest mistake of our previous attempt of uncovering how transducers compute their work was the assumption that (map inc) returns a function that takes a collection as argument. As is very well explained by Eero, it actually returns a transducer, which is a function (or closjure) that expects a reducing function and returns another reducing function.

Quick remimder that a reducing function is a function that takes the result accumulated so far as the first argument, and the next input as its second argument¹.

So, when we call (map inc), what we get is²

(fn [rf]
  (fn [result input]
    (rf result (inc input))))

Similarly, (filter odd?) would produce

(fn [rf]
  (fn [result input])
    (if (odd? input)
      (rf result input)
      result))

Notice also that both of these results expect a reducing function as an input. So, the result of calling ((map inc) conj) is roughly

(fn [result input]
  (conj result (inc input)))

Now everything seems to be falling in place right? It is also worth noting that calling (into [] xf nums) is more or less (actually they are functionally identical) the same as (reduce (xf conj) [] nums).

You can imagine composing transducers as unwrapping the outer layer, the one which expects a reducing function, modifying the behavior of the inner reducing function with whatever was passed as an input, and then wrapping it back again. This way, the transformation performed by the left-most transducers in the composition are going to be placed on the inner-most portion of the resulting transducer/reducing function.

Given all of this acquired knowledge, let’s see what exactly happens when we declare the xform as the composition of transducers, i.e. how that expands using some anonymous functions.

Let’s call M the result of (map inc), and F the result of (filter odd?).

(def F (filter odd?))
(def M (map inc))

(comp (filter odd?) (map inc))              ; 1
(fn [rf] (F (M rf)))                        ; 2

applying this to conj, a reducing function, we get

((fn [rf] (F (M rf))) conj)                 ; 3                     
(F (M conj))                                ; 4                     
(F (fn [result input] (conj result input))) ; 5                     
(fn [result input]                          ; 6                     
  (if (odd? input)                                                  
    ((fn [result' input'] (conj result' (inc input'))) result input)
    result))                                                        
(fn [result input]                          ; 7                     
  (if (odd? input)                                                  
    (conj result (inc input))                                       
    result)) 

Let us examine, step-by-step, what is going on:

1. First, notice that the first step is equivalent to (comp F M), just so we’re clear.
2. The second step doesn’t have anything new, we’re just expanding the definition of comp.
3. Steps 3 and 4 are just function application, also nothing new.
4. On step 5 things begin to get interesting. We have just expanded the definition of (map inc), just like before, by substituting rf with our argument, conj. It starts to take shape, but it still looks like the mapping is being done first.
5. Now, on the sixth step, it finally becomes clearer why the filtering is being done before the mapping. As we can see, we have just expanded the definition of (filter odd?), but that results in a reducing function that only calls the mapping if the input is odd, therefore we filter before mapping! The final step is just the simplification of the previous step to our final reducing function.

As we can see, the result of applying a reducing function to our transducer is itself another reducing function, but this time it looks a little clearer why, counter-intuitively to how composition of functions works, the transformation of the input is done left-to-right.

But you haven’t explained how the into execution before results in the correct sequence! Actually, I have! Although that is also a simplification of how it actually works. In reality, (into [] xf nums) is (in most cases³) the same as (transduce xf conj [] nums) which works the same as the reduce I presented, although the actual implementation of transduce deals with protocols and some Java interop…

Takeaways from all this

I have only scratched the surface of how transducers work (as I mentioned previously, this was done better by other people), and this article was mainly focused on how composition of transducers behaves in the opposite direction to composition of functions, but this has given me a glimpse into the elegance and cleverness of their inner workings, and it also made me go check out the code in core, which in turn made me realise that it is (for the most part) really simple and well written code! Anyone with a bit of Clojure knowledge/experience can start to navigate it and start to understand how Clojure works under the hood.

So I guess the conclusion is: kudos to the Clojure team for building such clever, simple and concise code! I guess Rich succeeded when he set to out make “simple”, easy.

Now go explore the vast world of clojure.core and maybe you’ll find some neat things to share with the world as well!

Resources

• The blog post by Rich Hickey introducing transducers.
• The official transducers reference.
• A two part walkthrough of transducers by Renzo Borgatti: part 1 and part 2
• Grokking Clojure transducers by Eero Helenius.
• Structure and Interpretation of Clojure Transducers, a workshop on transducers for re:Clojure 2021. The notes for it are available in Org-mode format.

Footnotes

¹ Its a bit more complicated than that, since reducing functions need to be able to receive a single argument as well in order to produce the initial value, if that wasn’t supplied; take conj for example, which is a reducing function since its first argument is a collection (the result accumulated so far) and its second argument is the item to be conjoined, it can be called with only the collection, that is (conj []) ;; => []. But let’s assume, from now on, that it always expects two arguments, so a reducing function is a function of signature (fn [result input] ...).

² Note that this is also an oversimplification, since transducers are expected to take either zero, one or two arguments, but that is only important when you want to create your own transducers.

³ It will only be different for Transient Data Structures, in which it does some magic and calls it with conj! instead.

⁴ Actually, after I wrote this, the workshop “Structure and Interpretation of Clojure Transducers”, by Ben Sless, was posted on the London Clojurians YouTube channel. In it, even though on the actual talk he skimped over, he does sort of the same step-by-step walk-through of the composition. I’ll also link to the presentation notes for those who don’t want to watch the full workshop (though I highly recommend if you want to have a bit more in-depth understanding of transducers as a whole).