interleave-xform.clj

;; Interleave transducer. Like the normal interleave, but suitable for transduce. 
;; See inlined notes for details. Example at the bottom. If you are interested in this
;; and other similar explorations in and around the standard library, please check my
;; book: https://livebook.manning.com/#!/book/clojure-standard-library/chapter-32/v-10/1

(defn interleave-xform                      ; <1>
  [coll]
  (fn [rf]
    (let [fillers (volatile! (seq coll))]   ; <2>
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
         (if-let [[filler] @fillers]        ; <3>
           (let [step (rf result input)]
             (if (reduced? step)            ; <4>
               step
               (do
                 (vswap! fillers next)      ; <5>
                 (rf result filler))))
           (reduced result)))))))           ; <6>

;; <1> "interleave-xform" is modeled on the same semantic of the interleave function in the standard library: 
;; it interleaves elements until the end of the shortest sequence. The custom transducer contains all the
;; relevant arities. It first returns a function of "rf" the reducing function and this one returns a 
;; function of the typical transducers shape: 3-arities dedicated to initializing the reduction, ending the 
;; reduction and the reducing step respectively.

;; <2> "interleave-xform" assumes the interleaving is coming from a collection passed while creating the transducer.
;; The other is the transducing collection. We need to keep track of the rest of sequence every time an element 
;; is used for interleaving, so the remaining is stored in a volatile! instance.

;; <3> During the reducing step we verify to have at least one more element to interleave before allowing 
;; the reduction. Note the use of if-let and destructuring on the first element of the content of the volatile instance.

;; <4> As any good transducer "citizen", we need to check if another transducer along the chain has required 
;; the end of the reduction. In that case we obey without propagating any further reducing step.

;; <5> If instead we are not at the end of the reduction and we have more elements to interleave, we can proceed 
;; to update our volatile state with the rest of the interleaving collection and propagate another step down 
;; to other transducer using the "filler" element instead. Note that at this point, this is the second time 
;; we invoke "rf": the first one for the normal reducing step, the second one for an additional reducing step 
;; for the interleaving.

;; <6> In case we don't have any more items to interleave, we need to end the reduction using reduced. 
;; This prevents "nil" elements to appear in the final output, exactly the same as normal "interleave".

;; Here's an example of interleave used to implement Egyptian multiplication, a simple algorithm to 
;; multiply two numbers (https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication):

(defn egypt-mult [x y]
  (transduce
    (comp
      (interleave-xform (iterate #(* % 2) y))
      (partition-all 2)
      (take-while #(pos? (first %)))
      (filter #(odd? (first %)))
      (map second))
    +
    (iterate #(quot % 2) x)))

(egypt-mult 4 5)
;; 20