📝Transducers

tags

Clojure

source

“Transducers” by Rich Hickey - YouTube

The idea of transducer is to decouple transformation algorithm from data structure, so that a complex algorithm can be represented as a transducer and then it can be applied to lists, vectors, channels (CSP), observables and what’s not.

Essentially, that is the solution for N×M problem where N algorithms need to be applied to M data structures. e.g., implementing map, filter, take, drop for each new data structure. You implement transduce for each data structure and get the rest for free.

Transducers are an abstraction over reduce.

(defn mapl [f coll]
  (reduce (fn [r x] (conj r (f x)))
          [] coll))

(defn filterl [pred coll]
  (reduce (fn [r x] (if (pred x) (conj r x) r))
          [] coll))

(defn mapcatl [f coll]
  (reduce (fn [r x] (reduce conj r (f x)))
          [] coll))

Move outer reduce call to transduce function, take conj as parameter (rename to step).

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

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

(def cat
  (fn [step]
    (fn [r x] (reduce step r x))))
(defn mapcatting [f]
  (comp (mapping f) cat))

That’s the main idea.

comp works naturally on transducers, but the order might seem backwards.

;; take all even numbers and divide by 2
(comp
 (filter even?)
 (mapping #(% / 2)))

That happens because transducers are function that take step as argument. So each transducer takes previous transducer and wraps it. The bottom step is conj (or what is needed for the data structure). The stack is as follows: filter(mapping(conj)).

Besides that, Clojure adds two more arities: 0 arguments for initialization, 1 arguments for completion. They must exist but in most cases they just call the underlying transducer.

(defn filter [pred]
  (fn [rf]
    (fn
      ([] (rf))
      ([result] (rf result))
      ([result input] (if (pred input) (rf result input) result)))))

Transducers can be stateful:

(defn dropping-while [pred]
  (fn [step]
    (let [dv (volatile! true)]
      (fn [r x]
        (let [drop? @dv]
          (if (and drop? (pred x))
            r
            (do
              (vreset! dv false)
              (step r x))))))))

Once transducer is applied to a process, transducer yields another (potentially stateful) process, which should not be aliased.