Learn Clojure transducers by implementing them!

transducers.clj

(ns transducers
  "Learn transducers by implementing them."
  (:refer-clojure :exclude [map filter transduce sequence]))

(comment
  "Let's forget, for the sake of this experiment, about laziness in Clojure.
  We can implement eager versions of Clojure's `map` and `filter` functions as follows:")

(defn map
  [f coll]
  (reduce (fn [acc x]
            (conj acc (f x)))
          []
          coll))

(defn filter
  [pred coll]
  (reduce (fn [acc x]
            (if (pred x)
              (conj acc x)
              acc))
          []
          coll))

(comment

  (map inc (range 5))
  ;; => [1 2 3 4 5]

  (filter even? (range 5))
  ;; => [2 4]

  "Now, let's abstract out the reducing operations
  to implement single-arity versions of `map` and `filter`
  that return transducers.

  We'll call these functions `mapping` and `filtering` respectively."

  )

(defn mapping [f]
  (fn [reducing-fn]
    (fn [acc x]
      (reducing-fn acc (f x)))))

(defn filtering [pred]
  (fn [reducing-fn]
    (fn [acc x]
      (if (pred x)
        (reducing-fn acc x)
        acc))))

(comment

  "Let's call `mapping` with `inc` to get a transducer:"

  (mapping inc)
  ;; => (fn [reducing-fn]
  ;;      (fn [acc x]
  ;;        (reducing-fn acc (inc x))))

  "This is what a transducer looks like beneath the surface.

  Transducers take a reducing fn as input,
  and return a reducing fn as output.

  Reducing fns take an accumulator and value as inputs,
  and return the updated accumulator. 

  An example of a reducing fn is `conj`:"

  (conj [1 2] 3)
  ;; => [1 2 3]

  "Let's see what happens if we pass `conj` as the reducing-fn to our transducer:"

  ((mapping inc) conj)
  ;; => (fn [acc x]
  ;;      (conj acc (inc x)))

  "This can be used along with `reduce` to map over a function:"

  (let [transducer (mapping inc)
        reducing-fn (transducer conj)]
    (reduce reducing-fn
            []
            (range 5)))
  ;; => [1 2 3 4 5]

  "Now, we can implement Clojure's `transduce` function:"

  )

(defn transduce
  [transducer combining-fn init coll]
  (let [reducing-fn (transducer combining-fn)]
    (reduce reducing-fn
            init
            coll)))

(comment

  "and use it as such:"

  (transduce (mapping inc)
             conj
             []
             (range 5))
  ;; => [1 2 3 4 5]

  "We can use this to implement
  an eager version of Clojure's `sequence`:"

  )

(defn sequence
  [transducer coll]
  (transduce transducer conj [] coll))

(comment

  "and use it as such:"

  (sequence (mapping inc) (range 5))
  ;; => [1 2 3 4 5]

  )

(comment "We can chain transducers together using `comp`:")

(def tx
  (comp (mapping inc)
        (filtering even?)))

(comment "Surprisingly, `comp` works left-to-right when chaining transducers:")

(assert (= (sequence tx (range 10))
           
           (->> (range 10)
                (map inc)
                (filter even?))
           
           [2 4 6 8 10]))

(comment

  "To understand how this works, let's expand the expression:"

  (tx conj)

  ;; => (let [mx (mapping inc)
  ;;          fx (filtering even?)]
  ;;      ((comp mx fx) conj))
  ;;
  ;; => (let [mx (mapping inc)
  ;;          fx (filtering even?)]
  ;;      (mx (fx conj)))
  ;;
  ;; => (let [mx (mapping inc)]
  ;;      (mx (fn [acc x]
  ;;            (if (even? x)
  ;;              (conj acc x)
  ;;              acc))))
  ;;
  ;; => ((fn [reducing-fn]
  ;;       (fn [acc x]
  ;;         (reducing-fn acc (inc x))))
  ;;     (fn [acc x]
  ;;       (if (even? x)
  ;;         (conj acc x)
  ;;         acc)))
  ;;
  ;; => (fn [acc x]
  ;;      (let [reducing-fn (fn [acc x]
  ;;                          (if (even? x)
  ;;                            (conj acc x)
  ;;                            acc))]
  ;;        (reducing-fn acc (inc x))))
  ;;
  ;; => (fn [acc x]
  ;;      ((fn [acc x]
  ;;         (if (even? x)
  ;;           (conj acc x)
  ;;           acc)) acc (inc x)))
  ;;
  ;; => (fn [acc x]
  ;;      (let [acc acc
  ;;            x   (inc x)]
  ;;        (if (even? x)
  ;;          (conj acc x)
  ;;          acc)))

  "As we can see, the final reducing fn:
   - first does the mapping logic
   - then does the filtering logic
   - and finally updates the accumulator"

  "Play around with this file in a REPL to get a better feel!")