Transducer: Composition, Abstraction, Performance

Higher-order functions like map, fold, filter are indispensable in any functional program. With their flexibility, they are the tool of choice for operations on collections of all kinds. However, their scope of application is not limited to classic lists or vectors. In this article, we examine more fundamental properties of these operations and take a particular look at so-called transducers in the Clojure programming language.

Additionally, we will see how we can achieve not only very good reusability but also higher performance with the help of meaningful abstraction.

Everything is a fold

Those who have engaged with functional programming in the past may already be familiar with this statement. If you haven‘t had the opportunity yet (or want to refresh your memory), let‘s first look at a variant of the usual definitions of map and filter. (Note: All examples are written in Clojure, so from this point on we‘ll call fold by its Clojure name reduce):

(defn map
"Takes a function f and applies it to every element of xs."
[f xs]
(if (empty? xs)
xs
(cons (f (first xs)) (map f (rest xs)))))

(defn filter
"Takes a predicate pred and returns a list with all elements of xs that
satisfy pred."
[pred xs]
(if (empty? xs)
xs
(if (pred (first xs))
(cons (first xs) (filter pred (rest xs)))
(filter pred (rest xs)))))

Many definitions can be found like this in various standard libraries. As the heading of this section already reveals, both functions can also be defined via fold (or rather reduce). The signature of reduce, expressed in Haskell notation, looks like this: (b -> a -> b) -> b -> [a] -> b (specialized for lists in this case).

(defn mapping
"Takes a function f and returns a function. The returned function takes a
collection acc and an element x and appends x applied to f to the end of
acc."
[f]
(fn [acc x] (conj acc (f x))))

(defn map
"Takes a function f and applies it to every element of xs."
[f xs]
(reduce (mapping f) [] xs))

(defn filtering
"Takes a predicate pred and returns a function. The returned function takes
a collection acc and an element x and appends x to the end of acc if it
satisfies pred."
[pred]
(fn [acc x] (if (pred x) (conj acc x) acc)))

(defn filter
"Takes a predicate pred and returns a list with all elements of xs that
satisfy pred."
[pred xs]
(reduce (filtering pred) [] xs))

If our programs consisted exclusively of list processing, we could stop here, satisfied. However, something catches the eye: apart from the call to conj, the definitions of mapping and filtering tell us nothing about them working „only“ on collections!

From Collections to Processes

We have established that the connection to collections in our mapping and filtering functions exists only through conj. Now let‘s go one step further and see what happens when we abstract over conj. For this, it‘s helpful to think not of lists but of sequences of steps. mapping and filtering take on the role of „process modifications“: they receive a step and deliver a modified version of this step. So let‘s define a version of our functions parameterized over this „step“:

(defn mapping
[f]
(fn [step]
(fn [acc x] (step acc (f x)))))

(defn map
[f xs]
(reduce ((mapping f) conj) [] xs))

(defn filtering
[pred]
(fn [step]
(fn [acc x] (if (pred x) (step acc x) acc))))

(defn filter
[pred xs]
(reduce ((filtering pred) conj) [] acc))

Looking at the resulting definitions of mapping and filtering, we notice that the data structure on which they now operate is determined by the step parameter. This means we are no longer dependent on classic collections, but can (as we will see later) work with more or less arbitrary data structures and process them using mapping and filtering. However, one consideration for this step is still outstanding: while lists and vectors make it easy to think about a „beginning“ and an „end,“ which we use in map and filter, it‘s different with data structures like streams or signals. Instead of relying on the data structure, we take a different path:

1. Our transformers (mapping, filtering) should have a concept of „beginning“ and „end“ by themselves.
2. We expect from our step function not only that it is binary, but also that when called with no or one argument, it produces a „null“ value. Examples in Clojure would be (conj) => [], (conj [1]) => [1] or (+) => 0, (+ 1) => 1, etc.

We‘ll only address point 1 here. First, we‘ll propose an implementation of mapping and filtering. In the code example below, we make use of Clojure‘s syntax for „arity overloading.“ This means we can offer multiple implementations in one function for different numbers of arguments (more on this at Clojure - Functional Programming). Clojure will choose the corresponding implementation depending on the number of arguments passed.

(defn mapping
[f]
(fn [step]
(fn
([] (step)) ; 1.
([acc] (step acc)) ; 2.
([acc x] (step acc (f x))) ; 3.
)))

(defn filtering
[pred]
(fn [step]
(fn
([] (step))
([acc] (step acc))
([acc x] (if (pred x)
(step acc x)
acc)))))

At first glance, this may look somewhat unintuitive, but it‘s quickly explained using the example of mapping. The numbering here corresponds to the numbers in the code example above.

1. This case covers the „beginning“ of a process. Nothing has been calculated yet and there is no „next“ calculation. In this case, we want a „neutral“ element from our step function with which we can kick off the calculation.
2. Here we signal the „end“ of a process. No more elements are coming, so we take the last step with the already available „result.“
3. Finally, there‘s our case that processes the current result and an element together.

These functions are now parameterized to such an extent that we can express somewhat arbitrary processes with them and, probably more importantly, execute (or compose) multiple such process modifications in sequence! What does this look like in reality?

Process Modifiers

In the following, we give two examples of how all this helps us in the real world and when we might prefer this approach to regular chaining of list operations.

In both examples, we deal with the following problem: The semester is over and the professor wants to know how good the average performance of their master‘s students was in the exercise sessions. Using Clojure-Spec, we define some sample data. The first four lines define the „shape“ of our data. For example, ::title is a value that satisfies the string?-predicate; in the fifth line, we specify ::exercise as a map with the keys defined above. The output of sample has been prettified here a bit; the actual result would probably look somewhat more obviously random. Those who want to learn more about Spec can do so in an older blog article (German language only).

(ns my.namespace
(:require [clojure.spec.alpha :as s]
[clojure.spec.gen.alpha :as sgen]))

(s/def ::title string?)
(s/def ::student string?)
(s/def ::points (set (range 31)))
(s/def ::degree #{::msc ::bsc})
(s/def ::exercise (s/keys :req [::title ::student ::points ::degree]))

;; `sample` takes a generator for our `spec` and returns some random data that
;; matches this spec.
(sgen/sample (s/gen ::exercise))
;; =>
;; [{::name "Marco"
;;   ::title "Exercise 1"
;;   ::points 29
;;   ::degree ::msc}
;;  {::name "Mathias"
;;   ::title "Exercise 1"
;;   ::points 28
;;   ::degree ::bsc}
;;  ...]

Back to our task. This could be solved with regular list functions, for example, like this:

(defn sum-of-msc
[exercises]
(reduce + 0 (->> exercises
(filter #(= ::msc (::degree %)))
(map ::handins))))

Applied to a list of exercises, it gives us the correct result. However, there is a problem: Each call to filter, map, and reduce computes a new list! With large amounts of data, this can, as we‘ll see shortly, certainly lead to problems.

Next, we implement the same functionality expressed via our newly defined operators.

The first step will be a slightly modified version of reduce named reduce-with. This works very similarly to reduce, except that in addition to the reduction function (here step), it expects a parameter xf, which represents a composition of our functions.

(defn reduce-with
"Takes a function composed of process modifications xf, a step function, an
initial value and a sequence of operations. Applies xf with a step to every x
in xs."
[xf step init xs]
(let [f (xf step)]
(f (reduce f init xs))))

Inside the function, we call reduce as usual. However, the composition function xf is used as the reduction function, which is specialized for evaluation via the step parameter (itself a function) and bound to f. Then reduction occurs and the result is called once more with f to produce a final result. But what must xf look like? This function, quite analogously to sum-of-msc above, is also a composition of filtering and mapping. We call it xform here (a convention in the Clojure world).

;; Compose two process modificators into one.
(def xform
(comp (filtering #(= ::msc (::degree %)))
(mapping ::points)))

You may rightly wonder why the order of calls to filtering and mapping doesn‘t change, since regular composition (as with Clojures comp function) is evaluated „from right to left,“ but the threading in our sum-of-msc happens „from left to right“ (or top to bottom). At this point, the complete answer would exceed the scope. For the moment, let‘s just note that the composition of this type of function also evaluates „from right to left.“ You can easily find this out by completely reducing the composition of the functions by hand once.

(defn sum-of-msc-2
[exercises]
(reduce-with xform + 0 exercises))

This solution also delivers the correct result, also revealing a major speedup:

(let [exercises (sgen/sample (s/gen ::exercises) 1000)]  ; generate a random sample of 1000 exercises
(= (time (sum-of-msc exercises))
(time (sum-of-msc-2 exercises))))
;; => true
;; "Elapsed time: 407.378092 msecs"
;; "Elapsed time: 2.144632 msecs"

Upon closer inspection, the reason becomes obvious: Instead of computing a new list for each step, the processes are executed sequentially for each element. This saves us long intermediate results and gains us throughput.

Note: Obviously, the timing varies a lot by the actual kind of inputs we generate. Also, time is not really intended to be used as a measuring tool. However, the tendency that the transducer-version is vastly faster than the ‚standard‘ implementation still stands, even over repeated observations.

This concept is so practical that it is now part of the Clojure standard library under the name transducer. Many functions are already set up for use as transducers (including the well-known map, filter, mapcat, …). Our function reduce-with is defined there as transduce.

More Than Lists

Finally, the promised second example. The problem is the same, but this time we don‘t want to use lists but channels (via clojure.core.async). Here we write all values to a channel c and observe how the same xform process modification is applicable to these very channels. We also now use the built-in function transduce, which takes over the work of sum-of-msc-2.

(ns my.namespace
(:require
[clojure.core.async :as async]
[clojure.spec.alpha :as s]
[clojure.spec.gen.alpha :as sgen]))

(let [exercises (sgen/sample (s/gen ::exercises))
;; Create a channel using the xform defined above.
c (async/chan 1 xform)]
;; Put all our elements onto the channel.
(async/go (async/onto-chan c exercises))
(let [chan-res (loop [;; Read one element from the channel.
n (async/<!! c)
res 0]
(if-not n
res
(recur (async/<!! c)  ; Read the next element from the channel.
(+ res n)  ; Accumulate the result.
)))
list-res (transduce xform + 0 exercises)]
(= chan-res list-res)))
;; => true

Here we first put all elements into the channel (onto-channel). Then we read step by step from this channel until no more elements are present in it (<!!). As we see from the result, our xform does exactly the same here as it did with lists. Since our xform doesn‘t care what data structure it operates on (as long as it provides the infrastructure mentioned above), it can be reused without any changes and without problems!

Conclusion

Conclusion Transducers are the natural continuation of widely used list functions. In this article, we engaged with consistent abstraction and learned the concept of transducer along the way. Not only do transducers give us a powerful description of data transformations that is purely based on function composition and can be used in many ways, but they also bring crucial performance improvements.“