Transducers

I recently stumbled when using transducers. It was mainly because I still treated them as a simple partial application of their full counterparts. I knew that this conception was wrong, but it had gotten me everywhere I wanted so far. The bit that made me stumble, can be summarized as follows:

(into

  []

  (comp

    (map inc) 

    (filter odd?))

  (range 10))

The corresponding partial application.

((comp

  (partial map inc)

   (partial filter odd?))

 (range 10))

If you think of transducers as partial application, you would expect a different result as (filter odd?) would be a applied before (map inc) . So it was time to properly understand transducers.

The following examples are to a big part adapted from Timothy Baldridge's Transducer Intro. To begin with let's start with the observation that many standard functions such as map and filter can be implemented via reduce.

(defn -map [f vs]

  (reduce

    (fn [acc v]

      (conj acc (f v)))

    []

    vs))

(defn -filter [p vs]

  (reduce

    (fn [acc v]

      (if (p v)

        (conj acc v)

        acc))

    []

    vs))

(->>

  (range 10)

  (-map inc)

  (-filter odd?))

You will realize, being an avid Clojure follower, that there are still a couple of things complected 😉. The first being the redundancy of reduce . Let's pull that logic out.

(defn -mapping [f]

  (fn [acc v]

    (conj acc (f v))))

(reduce (-mapping inc) [] (range 10))

The second assumption we are currently making is that our accumulated collection is conjoinable. Let's use another level of functions to get rid of that assumption. job is just something that creates a new accumulated value from an accumulator and a new value.

(defn -mapping [f]

  (fn [job]

    (fn [acc v]

      (job acc (f v)))))

The reason we do not put job into the signature of -mapping is that we might not want to complect our mapping logic with the logic of the underlying datastructure. This enables us to completely separate the logic of the data manipulation from the pipeline logic.

(def rfn (-mapping inc)) ;; data manipulation

(reduce (rfn conj) [] (range 10)) ;; pipeline

Let's also just write it for filter .

(defn -filtering [p]

  (fn [job]

    (fn [acc v]

      (if (p v)

        (job acc v)

        acc))))

Now comes the tricky part. Can we still compose -mapping and -filtering ?

(def rfn (comp

           (-filtering odd?)

           (-mapping inc)))

(reduce (rfn conj) [] (range 10))

Yes we can. Both transducers expect a job and the job just takes an accumulator and a value. This can be conj or some a function like (fn [acc v] (conj acc (inc v))) .

Coming back to our original problem: To understand why transducers work the other way around with comp, let's first write down the above example a bit more explicitly.

(reduce ((-filtering odd?) ((-mapping inc) conj)) [] (range 10))

The reason that one can think of comp with transducers more of a ->> is that the job gets injected backwards. In the above example the inner function of -mapping (the result of ((-mapping inc) conj)) ) gets passed as a job to the outer function of -filtering but this mapping-job gets applied inside the filtering job (inner function of -filtering ), hence the reason comp kind of works left to right for tranducers (or at least that's what I am thinking of when composing them).

Normally the term job is replaced by xf for xtransform in Clojure documentation and tutorials.