Clojure's Transducers and Reducers

clojure-transduce-reduce.md

Transducers and Reducers

Notes and examples of Transducers and Reducers

Reducers

• Used on collections

• Eager evaluation only. (not lazy)

• The operation(s) and the input are no longer tied together

     
(r/map zero?)

;=> #<reducers$map$fn__2527 clojure.core.reducers$map$fn__2527@7201f000>

(let [map-zero? (r/map zero?)
      inputs [0 1 0 1 0 1]]
  (reduce conj [] (map-zero? inputs)))

;=> [true false true false true false]

• Can be combined into a single function for better performance. (composable)

(def zero?-and-not-false 
  (comp 
   (r/filter true?)
   (r/map zero?)))     

;=> #'user/zero?-and-not-false

(reduce conj [] (zero?-and-not-false [0 1 0 1 0 1]))

[true true true]

Transducers

• Can be used in ClojureScript

• Function C is the reducing function

• Function B calls Function C

• Function A creates Function B

• (A C) -> B

(defn a [c]  
  (fn b    
    ([] (c))    
    ([coll] (c coll))    
    ([coll input] (c coll input))))
	  
;=> #'user/a

(transduce a + [1 2 3])

;=> 6    

• Doesn't care about the input type

• Transducers seem to be faster than reducers

     
     (dotimes [n 5] (time (r/reduce + 0 [1 2 3])))
     
     "Elapsed time: 0.23142 msecs"
     "Elapsed time: 0.047252 msecs"
     "Elapsed time: 0.043944 msecs"
     "Elapsed time: 0.062372 msecs"
     "Elapsed time: 0.05938 msecs"

     ;=> nil
     
     (dotimes [n 5] (time (transduce a + 0 [1 2 3])))
     
     "Elapsed time: 0.1257 msecs"
     "Elapsed time: 0.026548 msecs"
     "Elapsed time: 0.018166 msecs"
     "Elapsed time: 0.031276 msecs"
     "Elapsed time: 0.024773 msecs"
     
     ;=> nil

• Collection fns of previous Clojure versions are now optionally Transducers

(let [*2 #(* % 2)
      *4 #(* % 4)]
  
  (def weird-composition       
    (comp 
     (filter even?)
     (map *2)
     (map *4))))

;=> #'user/weird-composition

(into [] weird-composition [1 2 3 4])

;=> [16 32]

• For lazy transformations you must use sequence

(def star-wrap
  (map #(str "*" % "*")))

;=> #'user/star-wrap

(into [] star-wrap [1 2 3])

;=> ["*1*" "*2*" "*3*"]

(sequence star-wrap [1 2 3])

;=> ("*1*" "*2*" "*3*")

(type (into [] star-wrap [1 2 3]))

;=> clojure.lang.PersistentVector

(type (sequence star-wrap [1 2 3]))

;=> clojure.lang.LazyTransformer

Two comments, based on looking at the HEAD Clojure codebase.

Eagerness

I think that reducers are not eager per se, but many times that you think you have a reducer, you actually are getting a folder. For example, from reducers.clj:

(defcurried map
  "Applies f to every value in the reduction of coll. Foldable."
  {:added "1.5"}
  [f coll]
  (folder coll
   (fn [f1]
     (rfn [f1 k]
          ([ret k v]
             (f1 ret (f k v)))))))

returns a folder while

(defcurried take-while
  "Ends the reduction of coll when (pred val) returns logical false."
  {:added "1.5"}
  [pred coll]
  (reducer coll
   (fn [f1]
     (rfn [f1 k]
          ([ret k v]
             (if (pred k v)
               (f1 ret k v)
               (reduced ret)))))))

returns a reducer, and the reducer's coll-reduce just defers to the collection's coll-reduce:

(defn reducer
  {:added "1.5"}
  ([coll xf]
     (reify
      clojure.core.protocols/CollReduce
      (coll-reduce [this f1]
                   (clojure.core.protocols/coll-reduce this f1 (f1)))
      (coll-reduce [_ f1 init]
                   (clojure.core.protocols/coll-reduce coll (xf f1) init)))))

while folder implements CollFold as well:

(defn folder
  {:added "1.5"}
  ([coll xf]
     (reify
      clojure.core.protocols/CollReduce
      (coll-reduce [_ f1]
                   (clojure.core.protocols/coll-reduce coll (xf f1) (f1)))
      (coll-reduce [_ f1 init]
                   (clojure.core.protocols/coll-reduce coll (xf f1) init))

      CollFold
      (coll-fold [_ n combinef reducef]
                 (coll-fold coll n combinef (xf reducef))))))

Not defining it for itself, reducer's coll-fold will be inherited from Object, where it is defined as

 Object
 (coll-fold
  [coll n combinef reducef]
  ;;can't fold, single reduce
  (reduce reducef (combinef) coll))

In summary, I believe that fold will be eager when and only when operating on folders, while every other combination will be only as eager as the underlying collection.

transduce vs reduce

Regarding the speediness of core/transduce vs r/reduce and core/reduce,
this seems to follow from a definition that
makes use of java implementations of reduce, as specified by the IReduce interface:

(defn transduce
  ([xform f coll] (transduce xform f (f) coll))
  ([xform f init coll]
     (let [f (xform f)
           ret (if (instance? clojure.lang.IReduce coll)
                 (.reduce ^clojure.lang.IReduce coll f init)
                 (clojure.core.protocols/coll-reduce coll f init))]
       (f ret))))

In PersistentList.java, we find:

public Object reduce(IFn f, Object start) {
    Object ret = f.invoke(start, first());
    for(ISeq s = next(); s != null; s = s.next())
        ret = f.invoke(ret, s.first());
    return ret;
}

Honestly, I can't reason out the logic here, but for some reason transduce ends up using Java implementations of .reduce, while reduce uses Clojure implementations of coll-reduce.