transduce

;; First, define a transducer for producing the first ten odd numbers:
(def xf (comp (filter odd?) (take 10)))

;; We can then apply this transducer in different ways using transduce.

;; Get the numbers as a sequence:

(transduce xf conj (range))
;;=> [1 3 5 7 9 11 13 15 17 19]

;; Or sum them:

(transduce xf + (range))
;; => 100

;; ... with an initializer:

(transduce xf + 17 (range))
;; => 117

;; Or concatenate them to a string:

(transduce xf str (range))
;; => "135791113151719"

;; .. with an initializer:

(transduce xf str "..." (range))
;; => "...135791113151719"

;; When studying Korean, I had notes with mixture of Korean and
;; English and I wanted to filter out any English. 

(def example (str "I will write an autobiography(자서전) later\n"
                  "(저는) 나중에 자서전을 쓸 거에요"))

;; Here's a transducer to filter out english characters

(defn filter-out-english 
  "filter out english characters in a string"
  []
  (filter (fn [c] 
            (let [i (int c)] 
              (not (or (and (>= i 65) (<= i 90)) 
                       (and (>= i 97) (<= i 122))))))))

;; Here's a transducer to help deal with extra spaces and newlines.
;; Notice the mapcat ensures that the output will always be the same
;; shape as the input

(defn trim-chars [c n]
  "Ensure exactly n characters c in a row. For example, squash
  multiple spaces into single space or expand newlines into 2
  newlines"
  (comp (partition-by #{c})
        (mapcat #(if (= c (first %)) (repeat n c) %))))


;; put it all together, we filter out english characters, replace
;; multiple spaces with single space, and ensure each line is double
;; spaced (two line breaks between each line)
(def xf (comp (filter-out-english) 
              (trim-chars \space 1)
              (trim-chars \newline 2)))

(apply str (transduce xf conj example))
;; => " (자서전) \n\n(저는) 나중에 자서전을 쓸 거에요"

;; transduce with the identity transform is equivalent to reduce,
;; in the following way:
(transduce identity f sample)
(f (reduce f (f) sample))

;; For example, we can define a reducing function and then use it:
(defn conj-second
  ([]
   [])
  ([result]
   result)
  ([result [x y]]
   (conj result y)))

(def sample [[1 :a] [2 :b] [3 :c]])

(transduce identity conj-second sample)
;;=>[:a :b :c]
(conj-second (reduce conj-second (conj-second) sample))
;;=>[:a :b :c]

;; Let's prove the point with printing:
(defn conj-second
  ([]
   (println "0") [])
  ([result]
   (println "1") result)
  ([result [x y]]
   (println "2") (conj result y)))

;; Then the following both print 0 2 2 2 1
(transduce identity conj-second sample)
(conj-second (reduce conj-second (conj-second) sample))

;;; BUILD A STATEFULL TRANSDUCER

;; Make a transducer that accumulates a sequence when pred is truthy and
;; returns individual values when pred is falsy.
;;
;; For example when pred is odd?, partition
;;
;;    [1 1 1 2 2 3 3 3]
;;    
;; into
;; 
;;    [[1 1 1] [2] [2] [3 3 3]]
;;

(defn accumulate-when [pred]
  ;; A transducer takes a reducer function and returns a reducer function.
  (fn [rf]
    ;; State (an accumulator) which is closed over by the reducer function.
    (let [acc (java.util.ArrayList.)]
      (fn
        ;; Arity 0 (state initializer). In this step we can initialize `acc`
        ;; based on the returned valued of (rf), but here, as it is usually the
        ;; case, this is not needed.
        ([] (rf))
        
        ;; Arity 1 (completer). Called after the reducing process has ended (if
        ;; ever). In this step local state must be cleaned and residual reducing
        ;; step may be performed. `result` is an unreduced value (see reduced
        ;; and unreduced).
        ([result]
         (let [result (if (.isEmpty acc)
                        ;; No residual state. Simply return the result.
                        result
                        ;; Need to clear the residual state and perform one last
                        ;; reducing step on the so far accumulated values.
                        (let [v (vec (.toArray acc))]
                          (.clear acc)
                          ;; This step might return a completed value (i.g. on
                          ;; which reduced? gives true). We need to deref it
                          ;; with `unreduced` in order to supply it to rf.
                          (unreduced (rf result v))))]
           ;; Nested rf call. Must happen once!
           (rf result)))
        
        ;; Arity 2 (reducer). This is where the main work happens.
        ([result input]
         (if (pred input)
           ;; When pred is truthy, accumulate and don't call the nested reducer.
           (do
             (.add acc input)
             result)
           ;; When pred is falsy, call nested reducer (possibly twice).
           (if (.isEmpty acc)
             ;; When accumulator is empty, reduce with a singleton.
             (rf result [input])
             (let [v (vec (.toArray acc))]
               (.clear acc)
               ;; First reduce on the accumulated sequence.
               (let [ret (rf result v)]
                 (if (reduced? ret)
                   ;; If sequence is completed, no more reductions
                   ret
                   ;; else, reduce once more with the current (falsy) input.
                   (rf ret [input])))))))))))

(def x [1 1 1 2 2 3 3 3])

;; Step through with the debugger in order to gain a better understanding of the
;; involved steps.

(transduce (accumulate-when odd?) conj x)
;; user> [[1 1 1] [2] [2] [3 3 3]]

(transduce (comp (take 4) (accumulate-when odd?)) conj x)
;; user> [[1 1 1] [2]]

(transduce (comp (accumulate-when odd?) (take 3)) conj x)
;; user> [[1 1 1] [2] [2]]

(transduce (comp (accumulate-when odd?) (take 4)) conj x)
;; user> [[1 1 1] [2] [2] [3 3 3]]

;; Clojure core statefull transducers are partition-by, partition-all, take,
;; drop, drop-while, take-nth, distinct, interpose, map-indexed and
;; keep-indexed.

(transduce
 (partition-by identity)
 (fn
   ;; init - returns initial value for accumulator, called when no init is given to transduce
   ([] [])
   ;; completion - returns the final result, take the final accumulated value, called once there are no more elements to process
   ([acc] acc)
   ;; step - do whatever you want on each element, returns accumulated state and takes accumulated state from before and new element
   ([acc e] (conj acc e)))
 '()
 [1 1 1 2 2 3 3 4 4 5 6 7 7])

;; => ([7 7] [6] [5] [4 4] [3 3] [2 2] [1 1 1])

;; These two forms are equivalent:

(reduce ((map inc) conj) [] '(1 2 3 4 5))
;; => [2 3 4 5 6]

(transduce (map inc) conj [] '(1 2 3 4 5))
;; => [2 3 4 5 6]

;; Which shows how transduce works: it applies the transducer to the reducing
;; function, and reduces the collection with that

;; But n.b. this example masks the fact that transduce does call f an extra
;; time for "completion", because arity-1 conj = identity.