Clojure Transducers
Tags: clojure, transducers
Published: 2020-01-02 01:16:49

With a personal life that gets in the way of writing, I've been on a short hiatus, but I do plan to return to my overall story. In the meantime, I was playing with [Clojure transducers](https://clojure.org/reference/transducers) last night and thought I'd write some notes.

## Sudoku
During a discussion on query algebra for graph databases with a friend, he mentioned [constraint propagation](https://en.wikipedia.org/wiki/Local_consistency) and pointed me at [Peter Norvig's Sudoku Solver](https://norvig.com/sudoku.html). I'm a little rusty on Python so I worked my way through it, which was a fun thing to do over my New Year break.

As an advocate of [Functional Programming](https://en.wikipedia.org/wiki/Functional_programming#Pure_functions) (FP), the statefulness of the solution made me feel particularly uncomfortable, though it did not look to be too tied to the solution. I was tempted to rewrite it in more familiar terms until I saw that the post includes a link to [Justin Kramer's Clojure version](https://jkkramer.wordpress.com/2011/03/29/clojure-python-side-by-side/) (thank you, Justin!).

## Short Circuits
As a sometimes-lazy functional language, Clojure has many operations for processing sequences of data. Using these as much as possible is idiomatic for Clojure, as it tends to isolate concerns (reducing the likelihood of bugs), creates abstractions that are favorable for refactoring, and on occasion gives libraries the latitude to improve performance. So I often look for opportunities to use sequence processing, even when the implementation may be less obvious. That doesn't mean I would necessarily do this in production code, but the exploration is pedagogical, and occasionally leads me to new insights.

One aspect of Norvig's code is that it terminates processing early when it discovers an inconsistency in the data (e.g. 7 may be the only option left for this square, but it is already used elsewhere in the same column). This allows the algorithm to move to the next possibility. To do this, instead of returning an updated data structure from the search functions, Norvig's code returns the value `False`. (Cue the howls from advocates of statically typed languages. After all, he doesn't even use an [Option](https://en.wikipedia.org/wiki/Option_type) monad! 😉).

In general, Clojure's sequence processing does not have an option to terminate early. Of course, exceptions can always be thrown, but this is not really appropriate for handling expected data, and it is definitely not "good form" for FP.

In Justin's case, he wrote a function called [`reduce-true`](https://gist.github.com/jkk/891288#file-sudoku-clj-L138) which performs the usual operation of `reduce`, but terminates early whenever the result becomes a false value (`false` or `nil`). This function uses a `loop`/`recur` construct, which is straightforward to follow. This is exactly how I've always done such things in the past.

But this phrase "terminates early" is one that is specifically referenced by Clojure Transducers. This made me wonder if there was something I should consider here.

## Transducers
[Clojure Transducers](https://clojure.org/reference/transducers) are a mechanism introduced in Clojure 1.7. From the [changelog in 2014](https://github.com/clojure/clojure/commit/334c526a0731b8c84b634e76d36857d94692db9f#diff-6aedba0e8644f6fb36eebae1c1885f7d):
> Transducers is a new way to decouple algorithmic transformations from their application in different contexts. Transducers are functions that transform reducing functions to build up a "recipe" for transformation.

The transducers mechanism supplies the "separation of concerns" that I mentioned earlier and results in [several benefits](https://clojure.org/guides/faq#transducers_vs_seqs), most especially in performance when data goes through multiple transformations. But the thing that always stood out for me is that transducers can process a sequence to contain more or fewer elements than the initial sequence. This is a requirement that keeps coming up for me, and to date, I have been avoiding using transducers to fill this gap.

### Multiple Elements
The main place where standard `map` operations let me down is where a single value in an input sequence may result in multiple values in the output sequence. Consider an example of a modified [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz). For an input sequence of:
`[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]`

Then the output should be:
`[1, 2, :fizz, 4, :buzz, :fizz, 7, 8, :fizz, :buzz, 11, :fizz, 13, 14, :fizz, :buzz, 16]`

The numbers smaller than 15 can all be managed with a simple condition-based function:
```clojure
(defn fizzbuzz1 [x]
  (condp #(zero? (mod %2 %1)) x
    3 :fizz
    5 :buzz
    x))
(map fizzbuzz1 (range 1 15))
```
`=> (1 2 :fizz 4 :buzz :fizz 7 8 :fizz :buzz 11 :fizz 13 14)`

But what about the case for 15? We can't just return 2 values, as this will result in a pair object in the result stream:
```clojure
(defn fizzbuzz2 [x]
  (condp #(zero? (mod %2 %1)) x
    15 [:fizz :buzz]
    3 :fizz
    5 :buzz
    x))
(map fizzbuzz2 (range 1 17))
```
`=> (1 2 :fizz 4 :buzz :fizz 7 8 :fizz :buzz 11 :fizz 13 14 [:fizz :buzz] 16)`

One approach is to use a loop instead, note that the test for 15 could be avoided, but I'm keeping it in place to parallel the above function:
```clojure
(loop [[n & ns] (range 1 17) result []]
  (if-not n
    result
    (let [appended (fizzbuzz2 n)
          result (if (sequential? appended)
                   (into result appended)
                   (conj result appended))]
      (recur ns result))))
```
`=> (1 2 :fizz 4 :buzz :fizz 7 8 :fizz :buzz 11 :fizz 13 14 :fizz :buzz 16)`

This works, but it mixes the mechanism (the `loop`/`recur`) with the specific operation that we want. It also has a specific test for the datatype being returned, to determine how to add the data.

We can fix the second issue, by using the same datatype (a vector) for everything. This wraps scalars as a single-element vector...
```clojure
(defn fizzbuzz3 [x]
  (condp #(zero? (mod %2 %1)) x
    15 [:fizz :buzz]
    3 [:fizz]
    5 [:buzz]
    [x]))
(loop [[n & ns] (range 1 17) result []]
  (if-not n
    result
    (recur ns (into result (fizzbuzz3 n)))))
```
But with consistent return types, we can now go one better with the `fizzbuzz` function and skip the test for 15:
```clojure
(defn fizzbuzz4 [x]
  (or
    (seq
      (cond-> []
        (zero? (mod x 3)) (conj :fizz)
        (zero? (mod x 5)) (conj :buzz)))
    [x]))
(loop [[n & ns] (range 1 17) result []]
  (if-not n
    result
    (recur ns (into result (fizzbuzz3 n)))))
```
Finally, we can revisit the mechanism, which is the `loop`, and consider the `map` operation again. If we just look a the simple application of this operation, we get the intermediate structure:
```clojure
(map fizzbuzz4 (range 1 17))
```
`=> ([1] [2] (:fizz) [4] (:buzz) (:fizz) [7] [8] (:fizz) (:buzz) [11] (:fizz) [13] [14] (:fizz :buzz) [16])`

This sequence of sequences can be joined into a single sequence with `mapcat`:
```clojure
(mapcat fizzbuzz4 (range 1 17))
```
`=> (1 2 :fizz 4 :buzz :fizz 7 8 :fizz :buzz 11 :fizz 13 14 :fizz :buzz 16)`

This does better than the previous iterations:
- `fizzbuzz4` only tests for divisibility by 3 and 5, and automatically handles 15.
- There is little consideration of the mechanism for processing the list and building the result.

The only thing that may be of concern here is that all results for the `fizzbuzz4` function are sequences, even when the result is a single value. This creates a minor overhead and is also exposing something of how the data is joined in the `mapcat` operation. Nevertheless, this works well, and it is the approach that I have used numerous times in the past.

### Transducer Approach
Since transducers can output multiple values in a sequence for a given input element, is this something that we can use here?

To reiterate the documentation for transducers, a transducer is just an operation that returns a function with 3 arities. These follow the pattern we see in a `reduce` operation. Indeed, the transducer function is given a reducing function to create a context for the multiple arity function to use:
```clojure
(fn [reducing-function]
  (fn
   ([] ...)               ;; initialize
   ([result] ...)         ;; completion
   ([result input] ...))) ;; step
```
The _initialize_ function gets called first and is used for any initialization required. If initialization starts without an initial value, then the reducing function would be called with no arguments here. This reducing function varies according to the use of the transducer, but it can be provided directly for the `transduce` function.

e.g. if the code that calls the transducer was provided the `+` function for reduction as in:
`(transduce xf + [1 2 3 4])`
Then the `init` function would call `(+)` (which is 0). If the `xf` function is `identity`, then this will give the same result as:
`(reduce + [1 2 3 4])`

The _step_ function is where the work happens. It processes the `input` argument and chooses whether or not to append to the `result` argument.

Finally, the _completion_ function flushes any data and provides the final result.

#### Step
The _step_ function takes the current `result` and the next element to be processed. If the transducer is a filter, then it may choose to not add something to the result. If the transducer adds multiple elements (as in the FizzBuzz example above), then all of these can be added to the result here.

While learning about building a transducer, I was curious about what had been accumulated in the `result` already. This depends entirely on the type of operation that is being done with the transducer.
- If it is called with `sequence` then the `result` will be `nil`, and the reducing function will buffer the data, as a lazy sequence.
- If `(into [] ...)` is used, then a `TransientVector` is created and populated.
- If `transduce` is called, then the initial value for the result is either provided or will be the result of calling the 0-arity form of the reducing function.
- If the transducer is called via `eduction`, then the result will depend on the way that the iterator is called. Printing to repl will provide a `result` of `nil`. Calling via `reduce` will have a `result` of the data being reduced into.

In other worse, there is no guarantee of what kind of result will be provided, nor on the reduction function that will be used to interact with it. These values must be considered opaque.

If we want to know what has been added to the `result` already, then the appropriate way to do it is with state of our own. For instance, the [`dedupe` transducer](https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L7655) uses a **volatile** value to save the last thing appended.

### Take 2
Mixing in the operation of `fizzbuzz4` with the transducer operation, we get:
```clojure
(defn fizzbuzz*
  []
  (fn [rf]
    (fn
      ([] (rf))
      ([result] (rf result))
      ([result input]
       (let [fb (cond-> []
                  (zero? (mod input 3)) (conj :fizz)
                  (zero? (mod input 5)) (conj :buzz))]
         (if (seq fb)
           (reduce rf result fb)
           (rf result input)))))))
```
It would be possible to use the existing `fizzbuzz4` function and reduce the returned value into the result, but this approach avoids the creation of that wrapping vector.

The first few lines of this transducer are all boilerplate, which is always an unfortunate thing, but it is not too onerous here. The interesting work all occurs in the final 2-arity function. First of all, the `fb` value is set to an empty vector which is then appended to if the input is divisible by 3 and/or 5. If this `fb` vector is not empty, then each of the values are put into the result with the reducing function (via `reduce`), or else the reducing function is used to add the current input number.

How can this be used? Like any other reducer, it can be `comp`-ed into a transducer pipeline, or else it can be given to a function that provides a transducer context:
```clojure
(transduce (fizzbuzz*) conj [] (range 1 17))
(into [] (fizzbuzz*) (range 1 17))
(sequence (fizzbuzz*) (range 1 17))
(eduction (fizzbuzz*) (range 1 17))
```
The first 2 will provide a vector with the correct output, the third (`sequence`) will create a lazy sequence, and the final one (`eduction`) will create an object that can be iterated on. All of them will result in the desired seq.

## Truncating Results
Recall that I started this because I wanted to create a reduction operation that terminated early. So how is that managed?

Transducers can terminate early by calling `reduced` on the result being returned from the step function. This indicates to the calling process that it must not process any more data, and call the _completion_ function.

Let's return to Justin's [reduce-true](https://gist.github.com/jkk/891288#file-sudoku-clj-L138) function. This operates just like a `reduce` operation, unless the reduction function returns a false value at any point, in which case it will immediately return that value with no further processing.

To do this we need to know what data the reducing function generates before adding it to the result, since we are not able to look at the result value. We also don't know what the reducing function will look like, since different contexts can use a different function.

I decided to opt for the approach used by `dedupe` which keeps some state using a _volatile_ value. This gives us the option of checking the result when invoking the user-supplied function and setting an exit flag if it is nil. When this happens, the step function can use `reduced` on the result to indicate the end of the reduction.

So this is my approach:
```clojure
(defn reduce-true
 [f val coll]
 (let [end (volatile! false)
       terminating (fn [rf]
                     (fn
                       ([] (rf))
                       ([result] (rf result))
                       ([result input]
                        (let [nxt (rf result input)]
                          (if @end
                           (reduced nxt)
                           nxt)))))
       ff (fn
           ([a] a)
           ([a b]
            (let [r (f a b)]
              (when-not r (vreset! end true))
              r)))]
  (transduce terminating ff val coll)))
```
The first line of the `let` creates the termination flag and initializes it to `false`. The `terminating` value is then set to our terminating transducer.

We can see here that the _step_ function gets the result of calling the reducing function, and then checks the flag to determine if the final result needs to have `reduced` called or not. If this `reduced` function gets called, then the process will finish.

Next, we can see that the user-supplied reducing function is wrapped in a function called `ff` that will set this `exit` flag if the user-supplied function ever returns a false value. A single arity function is also provided for cleanup, though this is just a no-op.

With this transducer set up, we can now do a terminating reduction using `transduce`, starting with the user-supplied `val` and processing the provided collection `coll`.

## Wrap Up
Is this better?

For the provided example, I would say no. Justin's `reduce-true` function is clearer in operation, despite revealing the mechanism for processing the collection. Given that the `loop`/`recur` construct of this function has no construction overhead, then there won't be any performance benefit either.

An approach like this transducer-based function may be more flexible and integrate with other transducers a little better (if the function returns the transducer directly and does not call `transduce` itself). But for the provided application there isn't any benefit.

However, I now have a better idea of where things go when building my own transducer. When I first started playing with this, I was focused on the `transduce` function, which gave me the wrong idea of what the reduction function would be and the datatype of the `result` arguments. Writing this post helped me fill in some of the edges of my knowledge that I hadn't realized were lacking.

So now I know how to avoid `mapcat` and how to create early-terminating sequence processing. That's a little more about transducers than I was comfortable with when I started. 🙂


Happy New Decade everyone!