Lambda Island

Clojure allows processing data in a way that is composable, reusable, and performs well, all through the power of Transducers. Episode 38 provided a general overview of what’s in the box, the transducers and transducing contexts provided by clojure.core. This episode digs deeper into the internals of transducers and reducing functions, and looks at some powerful libraries for real-world data processing and statistics.

Transcript

This episode digs deeper into the topics explored in episode 38 about Transducers. If you’re not yet comfortable using and composing Clojure’s built-in transducers with into and transduce, then check out episode 38 first.

But before we get to the topic du jour, we need to take a step back and look at the humble reduce function. While transducers are a relatively new addition to Clojure, their design is largely based on reduce, which has been part of clojure.core from the very beginning.

At its simplest reduce “reduces” a collection to a single value. An example would be to reduce a collection of numbers to their sum.

(reduce + [1 2 3 4]) ;;=> 10

Reduce optionally takes a starting value, but if you leave it out it uses the first item of the collection as the starting point.

(reduce + 100 [1 2 3]) ;;=> 106

Let’s unpack this a bit. reduce takes a two argument “step function”. The first argument to the step function is called the “accumulator”, since this is where bit by bit the final result accumulates. The second argument is fed each item of the input, one by one.

reduce applies the step function step by step, first to the starting value and the first item in the collection, then to the result so far and the second item, and so on, until the collection is fully consumed and a result is returned.

(reduce (fn [acc x]
          (+ acc x))
        0
        [1 2 3])
;;=> 6

With reductions you can get a better appreciation of how reduce works, it returns a sequence of the successive accumulator values, so you can see exactly how each intermediate value is calculated.

(reductions (fn [acc x] (+ acc x)) 0 [1 2 3 4])
;;=> (0 1 3 6 10)

The accumulator can take many forms, including rich composite types like collections. This makes it possible to express pretty much any operation over a collection with reduce. You could do the equivalent of a map, or a filter, using only reduce.

In this case the accumulator is a collection, that gradually accumulates computed values, mapping a vector of numbers to their squared values.

(reduce (fn [acc x]
          (conj acc (* x x)))
        []
        [1 2 3])
;;=> [1 4 9]

Similarly you can reimplement Clojure’s into function as reduce conj, since this is exactly what into does, just continously applying conj.

(defn my-into [target src]
  (reduce conj target src))

(my-into #{} [1 2 3])
;;=> #{1 3 2}

The reduce function is a staple of functional programming, but Clojure added something extra to make it even more general purpose: you can terminate the iteration early by returning a “reduced” value.

This reduce again computes a sum, but as soon as the total is greater than five, the reduction stops and the accumulator is returned.

(reduce (fn [acc x]
          (if (> acc 5)
            (reduced acc)
            (+ acc x)))
        [1 2 3 4])
;;=> 6

reduced isn’t anything magical, it merely wraps a value in a special type of object, of type clojure.lang.Reduced. If reduce notices that the step function returned such an object, then it unwraps it, and returns that result immediately.

A reduced is a reference type, like an atom or ref, meaning you can deref it to get to the value inside of it. If you’re dealing with values that could potentially be wrapped in a reduced, then you can use unreduced to make sure you’re dealing with an unwrapped value again. Using unreduced on a plain value simply returns the value.

(reduced 42)
;; => #<Reduced@4f3c2254: 42>

(type (reduced 42))
;; => clojure.lang.Reduced

@(reduced 42)
;; => 42

(unreduced (reduced 42))
;; => 42

(unreduced 42)
;; => 42

Back to the step function. It’s a powerful vehicle for describing all kinds of transformations, and you can imagine defining generic step functions and reusing them, but there are some limitations.

Sometimes the step function needs more information than just the accumulated result and the next item. Consider this example, I’d like to use reduce to prefix a list of strings with index numbers.

["wulong" "red" "black" "green"]
;;=> ["1. wulong" "2. red" "3. black" "4. green"]

You can imagine that, besides the actual result that gets built up step by step, I also need to keep track of a counter somewhere. I can do that by using a vector as the accumulator, containing the counter value, and the actual result.

The step functions destructures this vector to get to all the pieces, and then returns again a two element vector as the new accumulator, containing with the incremented index counter, and the result vector, with an extra string conj’ed onto it.

In the end I add a call to second, since I’m not interested in the count, only in the result.

(second
 (reduce (fn [[idx res] s]
           [(inc idx) (conj res (str idx ". " s))])
         [1 []]
         ["wulong" "red" "black" "green"]))
;;=> ["1. wulong" "2. red" "3. black" "4. green"]

Using a vector or map like this is a common pattern, as it allows the step function to track multiple pieces of state, but now we’re placing an extra burden on the caller, who needs to supply a suitable initial state, and pull out the relevant bits of the final result.

Let’s pull out this step function and take a better look at it. It’s clear that it only described the very heart of a process, if a specific initial value is needed at the start, or if some finalization needs to happen on the result, then you need to capture that information in the surrounding code, easily causing duplication and mistakes.

In the end you need three pieces of information, an initial value, a step function, and a “completing” step. You can encode all of these together by turning this step function into a reducing function.

A reducing function is a generalization of the step function. It’s two-arity version is the equivalent of the step function, but it also has a zero-argument version for initialization, and a one-argument version as a final “completing” step.

(defn add-index-prefix
  ([] [1 []])
  ([acc] (second acc))
  ([[idx res] x]
   [(inc idx) (conj res (str idx ". " x))]))

So what can you do with this? Unfortunately the reduce function itself ignores the extra arities, this is where transduce comes in.

Remember that transduce is very similar to reduce, but it differs in two important ways. In the previous episode we focused on that first extra argument, called the “xform” or “transducer”, but here I’m calling it without a transducer, instead passing it the indentity function as a sort of “null-transducer”.

The second argument to transduce is a reducing function, exactly as we’ve described it, with zero, one, and two-argument implementations. So while reduce only takes a two-arity step function, transduce takes a complete reducing function.

(transduce identity add-index-prefix ["wulong" "red" "black" "green"])
;; => ["1. wulong" "2. red" "3. black" "4. green"]

It’s fun to note that some built-in functions have done this long before transduce was around, take for instance +. If you call it with zero arguments you get 0, which then forms the starting value. And if you call plus with a single argument it just returns the result, so it turns out + was a full reducing function long before it was cool.

(transduce identity + [1 2 3 4])
;;=> 10

The same is true for multiplication, but not for subtraction. The - function doesn’t have a zero-arity version. Functions like these you can work around by explicitly providing a starting value to transduce.

(-)
;;=> clojure.lang.ArityException: Wrong number of args (0) passed to: core/-

(transduce identity - [1 2 3 4])
;;=> clojure.lang.ArityException: Wrong number of args (0) passed to: core/-

(transduce identity - 0 [1 2 3 4])
;;=> 10

But why is the result 10, and not -10? Remember that at the end the reducing function is called again with a single argument, so that -10 turns again into a positive 10.

You can provide a separate “completing” step using completing from clojure.core. You give it your step function, and a function with a single argument that will be called all the way at the end. If you omit the function it defaults to identity, in other words it just returns the result unchanged.

(transduce identity
           (completing -
                       (fn [res]
                         (str "Result: " res)))
           0
           [1 2 3 4])
;; => Result: -10


(transduce identity
           (completing -)
           0
           [1 2 3 4])
;; => -10

To drive this all home lets look again at the original number prefixing example. This time by using transduce you can attach the completing step to the step function with completing, so that in the end you get again the same result.

(second
 (reduce (fn [[idx res] s]
           [(inc idx) (conj res (str idx ". " s))])
         [1 []]
         ["wulong" "red" "black" "green"]))


(transduce identity
           (completing
            (fn [[idx res] s]
              [(inc idx) (conj res (str idx ". " s))])
            second)
           [1 []]
           ["wulong" "red" "black" "green"])
;; => ["1. wulong" "2. red" "3. black" "4. green"]

So what does all of this have to do with transducers? Listen up, because this is the big reveal of this episode, a transducer is nothing but a function which takes a reducing function as its input, and returns a new reducing function.

Let me say that again because this is important: a transducer is a function that turns one reducing function into another reducing function.

If you’ve ever come across the middleware pattern, for instance in a Ring application, then you’ll recognize this as middleware. Transducers are middleware for reducing functions.

Mind… blown?

Transducer :: rf -> rf

So the general shape of a transducer is like this: it’s a function which takes a single argument, a reducing function, and returns a function with one, two, and three argument arities.

Notice how in each of the three arities this function calls the reducing function it was given, you can think of it as calling the next reducing function in the chain.

(fn [rf]
  (fn
    ([] (rf))
    ([acc] (rf acc))
    ([acc x] (rf acc x))))

This also explains why transducers compose with a simple comp, if function A maps rf to rf, and function B maps rf to rf, then composing A after B also maps from rf to rf. It really is an elegant design.

;; A :: rf -> rf
;; B :: rf -> rf
;;=>
;; (comp A B) :: rf -> rf

You now know enough to start writing your own transducers, but before you start coding I should give you some words of warning. There are quite a lot of things to watch out for when writing real world transducers, as Christophe Grand found out when he created the xforms library. Christophe did a great talk at ClojureD 2017 about all the things that you will get wrong, so before creating your own transducers at least watch that talk, I’ll link to it in the show notes.

The good news is that combining existing transducers can be done without issue, and with the extra transducers and transducing contexts that xform provides you really have a lot of power at your fingertips.

Let’s look at some of the things that xforms can do for you. You have to think of these functions as building blocks, they each do a small thing, but it’s their composability that makes them so great.

There are several new transducer contexts, for instance count takes a transducer and a collection, and counts how many items are left after applying the transducer. some returns the first non-nil item.

Keep in mind that these functions don’t need to realize the resulting collection, they directly compute their result with minimal overhead.

(require '[net.cgrand.xforms :as x])

(x/count (filter #(= 0 (mod % 3))) (range 1 20))
;; => 6

(x/some (filter #(= 0 (mod % 3))) (range 1 20))
;; => 3

x/str has two uses, it forms a transducing context which concatenates strings, which I’ve used here with Clojure’s built-in map and interpose transducers.

You can also x/str stand-alone as a string concatenating transducer. In this case the result contains just a single item.

(x/str (comp (map str/upper-case)
             (interpose "-"))
       ["foo" "bar" "baz"])
;;=> "FOO-BAR-BAZ"


(into [] x/str ["foo" "bar" "baz"])
;;=> ["foobarbaz"]

There are several more of these transducers that produce a single item stream, chief among them is x/reduce. Like transduce but unlike clojure.core/reduce, this also calls the initialisation and completion steps. It’s an extremely useful function because it allows you to treat arbitrary reducing functions as transducers, which are more readily composable.

(into [] (x/reduce +) [3 7 5])
;; => [15]

x/count, which I already demonstrated as a transducing context, can also be used as a transducer by itself.

(into [] x/count [1 2 3])
;; => [3]

You might notice a pattern here, a lot of xforms is clojure.core functions reimagined as transducers, or transducer contexts, or both.

Clojure’s into function got reimplemented, but this time with the previously missing single-arity version, returning a transducer.

(into [] (x/into #{}) [1 2 3])
;; => [#{1 3 2}]

These single-result transducers are especially useful when combined with by-key, perhaps my favorite xforms function. by-key is one of several functions that not only return a transducer, but also take a transducer as one of their arguments.

The by-key transducer outputs pairs, so it’s commonly used with into to get the output as a map.

The first argument is a key function, used to group input items. Here we’ll group these maps by their :color. The last argument is a transducer that is used to process each group, so the result is a map where the input items are grouped in vectors by the value of their :color key.

(into {}
      (x/by-key :color (x/into []))
      [{:color :blue, :size 1}, {:color :red, :size 2}, {:color :blue, :size 3}])
;;=> {:blue [{:color :blue, :size 1} {:color :blue, :size 3}],
;;     :red [{:color :red, :size 2}]}

In between the key function and the transducer you can provide a value function, now instead of collecting the complete items, you get only the :size values.

(into {}
      (x/by-key :color :size (x/into []))
      [{:color :blue, :size 1}, {:color :red, :size 2}, {:color :blue, :size 3}])
;;=> {:blue [1 3], :red [2]}

But the result doesn’t have to be a collection, by changing the transducer you could get the maximum size for each, or the total size. You could even nest calls to by-key to get complex roll-ups.

(into {}
      (x/by-key :color :size x/max)
      [{:color :blue, :size 1}, {:color :red, :size 2}, {:color :blue, :size 3}])
;; => {:blue 3, :red 2}

(into {}
      (x/by-key :color :size (x/reduce +))
      [{:color :blue, :size 1}, {:color :red, :size 2}, {:color :blue, :size 3}])
;; => {:blue 4, :red 2}

There’s so much gold in this library, I’d need a whole other episode just to scratch the surface, but I’ve created sample code that you can go through, that demonstrates the whole API.

Before wrapping up this episode I’d like to introduce you to one more library called Redux. While xforms is like a swiss army knife for transducers, Redux is a utility belt for working with reducing functions. It’s just a handful of functions, lets go over them.

The first of these is post-complete, which adds some additional completion logic. Note that this differs from clojure.core’s completing function. completing turns a step function into a full multi-arity reducing function. post-complete assumes you already have a reducing function, and will call the original completion step, before doing the extra processing.

(transduce identity
           (redux/post-complete
            + (fn [x] {:result x}))
           [1 2 3])

The complement to post-complete is pre-step, it does exactly what it says, apply a function to the input value before each step.

(transduce identity
           (redux/pre-step + :width)
           [{:width 10} {:width 20}])
;;=> 30

fuse is like a reducing version of juxt, it takes several reducing functions, and returns a reducing function that performs both at the same time.

(transduce identity
           (redux/fuse {:sum + :product *})
           [1 2 3 4])
;;=> {:sum 10, :product 24}

I should mention that xforms contains similar functionality for reducers called transjuxt, which can be either a transducing context, or a transducer returning a single collection. Both fuse and transjuxt can take either a vector or a map, depending on whether you want to label the composite values or not.

(x/transjuxt [x/min x/max (x/reduce +)] [1 10 100])
;;=> [1 100 111]

(x/transjuxt {:min x/min
              :max x/max
              :sum (x/reduce +)}
             [1 10 100])
;;=> {:min 1, :max 100, :sum 111}

;; Can also be used as a single-result transducer

(sequence (x/transjuxt [(x/reduce +) (x/reduce *)]) [1 4 9])

I’ll stop here with my exposition of these libraries, lest I start sounding like reading a dictionary out loud. In future installments you’ll see more ways of how to use these APIs in context. Still, you need to start somewhere, there is merit in actually studying what’s in the box, so you know what tools are at your disposal when you start solving problems.

In preparation of this episode I went through both xforms and redux with a handy REPL, seeing if I could come up with an example for each function. I can highly encourage doing this exercise, or you can start with reading through my notes, I’ll link to them below.

As I wrap up this episode, I think it’s worthwhile to take a step back, and think about why we use transducers in the first place. After all, the things I showed you could also have been accomplished with clojure’s trusty old map, reduce, and other collection functions. This can create the impression that transducers are just a lot of busywork, a fancy way of doing the same thing, just with a more complicated API.

One counterargument to this is that transducers perform better. They allow calculating in a single pass what otherwise would have taken many passes over the data, significantly saving on memory allocation, and thus putting a lot less pressure on the garbage collector.

This is all true, but it’s really just the icing on the cake. The real reason to use transducers is because they are composable, and allow for reuse in different contexts. You can build up and test your transformations step by step on the REPL, and once you are ready, ship them to production, to be used across core.async channels, or across an entire Apache Spark cluster using the Powderkeg library.

The examples in this episode have been rather trivial, because I had to get these core concepts across first, but Clojure is increasingly used for real world data processing and analysis. I’ll show you how to get into the exciting world of data science in the next episode!

Show Notes

browse source code

Summary

;; step-function (use with clojure.core/reduce)
(fn [acc x]
  ,,,)

;; Reducing function (use with transduce, xforms/reduce)
(fn
  ([] init)
  ([acc] completion)
  ([acc x]
   ...step...))

;; Transducer
(fn [rf]
  (fn
    ([] (rf))
    ([acc] (rf acc))
    ([acc x] (rf acc x) ...)))

xforms and redux samples

As preparation for this episode I went through the Xforms and Redux APIs, and wrote out some examples and notes for each function in there. This could be a great resource for getting more familiar with these libs. I also encourage you to do this exercise yourself, it’s very instructive.

Links

Libraries

Videos:

Inside Transducers