transducers.clj

## transducers.clj
(comment ; Fun with transducers, v2

  ;; Still haven't found a brief + approachable overview of Clojure 1.7's new
  ;; transducers in the particular way I would have preferred myself - so here goes:

  ;;;; Definitions
  ;; Looking at the `reduce` docstring, we can define a 'reducing-fn' as:
  (fn reducing-fn ([]) ([accumulation next-input])) -> new-accumulation
  ;; (The `[]` arity is actually optional; it's only used when calling
  ;; `reduce` w/o an init-accumulator).

  ;; We choose to define a 'transducing-fn' as:
  (fn transducing-fn [reducing-fn]) -> new-reducing-fn

  ;; If you're familiar with Ring middleware, a transducer is a lot like
  ;; reducing-fn middleware:

  (fn ring-handler    [ring-req])     -> ring-resp
  (fn ring-middleware [ring-handler]) -> new-ring-handler
  ;; Compare:
  (fn reducing-fn    ([]) ([accumulation next-input])) -> new-accumulation
  (fn transducing-fn [reducing-fn])                    -> new-reducing-fn

  ;;;; Quick observations:
  ;; 1. A transducer is just a fn.
  ;; 2. It's a lot like reducing-fn middleware, and composes just like middleware.
  ;; 3. This doesn't sound very impressive so far, which makes it easy to miss
  ;;    how big of a deal transducers actually are.

  ;; In fact numerous, major benefits fall out of this simple definition.
  ;; Transducers (transducing-fns plus a few utils) give us:
  ;; * Performance:
  ;;   * Can reduce w/o incurring any sequence construction costs.
  ;;   * Can map composed operations w/o incurring >1 sequence construction cost.
  ;;   * Efficient filtering + early termination.
  ;;   * All the benefits of 'Reducers' (parallel fork-join, etc.).
  ;;
  ;; * Convenience:
  ;;   * Easy composition through standard fn `comp` and threading, etc.
  ;;   * Easy construction through single-arity `map`, `filter`, etc.
  ;;   * Entirely eliminates need for special/extra core.async channel transform
  ;;     fns (`map<`, etc.).
  ;;   * Transducer-fns can use internal state to easily build powerful
  ;;     operations (e.g. see `dedupe` source).
  ;;   * Laziness iff you want it.
  ;;
  ;; * Conceptual:
  ;;   * Elegantly & flexibly unifies concepts like:
  ;;     * Reducing   - (ordered-seq    -> accumulated-val).
  ;;     * Mapping    - (ordered-seq    -> new-ordered-seq).
  ;;     * 'Reducers' - (unordered-coll -> accumulated-val).
  ;;     * Laziness.
  ;;     * Process composition.
  ;;   * Transducers are just fns defined in a particular way and which can be
  ;;     fed to some transducer utils. No voodoo, just a clever idea.

  ;;;; Transducer API
  ;;; The following all return transducing-fns (note absence of any colls):
  (map f)
  (filter f)
  (remove f)
  (take n)
  (take-while pred)
  (drop n)
  (drop-while pred)
  (take-nth n)
  (replace smap)
  (into to xform from)
  (partition-by f)
  (partition-all f1)
  (keep f)
  (keep-indexed f)
  (flatmap f) ; new, like `mapcat` (deprecated)
  (mapcat f) ; upcoming
  (dedupe f) ; new
  (random-sample prob) ; new
  ;; or you can just write your own (recall that transducing-fns are just fns)

  ;;; And these utils consume transducing-fns (note colls for consuming):
  (into to xform from)
  (iteration xform coll)        ; new
  (transduce xform f coll)      ; new, like `reduce`
  (transduce xform f init coll) ; new, like `reduce`
  (sequence xform coll)         ; like (lazy) single-coll `map`
  (sequence xform & colls)      ; like (lazy) multi-coll `map`


  ;;;; A minor wrinkle
  ;; Going back to our original definition:
  (fn reducing-fn    ([]) ([accumulation next-input])) -> new-accumulation
  (fn transducing-fn [reducing-fn])                    -> new-reducing-fn

  ;; I omitted a detail which Rich helped clarify.
  ;; `transduce` _actually_ expects a reducing-fn modified to also accept a new
  ;; `[accumumulation]` arity:
  (fn transducer-ready-reducing-fn
    ([]) ; Recall that this arity is optional (only needed when no init-accumulator given)
    ([accumulation]) ; <- This is the new arity to support transducing
    ([accumulation next-input])
    )

  ;; Clojure 1.7-alpha1's `transduce` _automatically_ adds the extra arity
  ;; given a regular reducing-fn, but later versions will require that you take
  ;; care of this yourself (the extra flexibility is helpful, but something
  ;; outside the scope of this short overview). A utility called `completing`
  ;; is being added to Clojure >1.7-alpha1 which helps wrap a regular reducing-fn
  ;; to give it this extra arity.

  ;;;; Homework
  ;; This is the identity transducing-fn:
  (defn identity-transducing-fn
    [reducing-fn] ; A 'completed' reducing fn (i.e. with an `[accumulation]` arity)
    (fn new-reducing-fn
      ([] (reducing-fn)) ; Only called/necessary when no init-accumulator given
      ([accumulation] (reducing-fn accumulation))
      ([accumulation new-input]
         (reducing-fn accumulation new-input))))

  (comment
    (sequence identity-transducing-fn '(1 2 3 4)) ; -> '(1 2 3 4)
    )

  ;; I found it helpful to compare this to the definition of the standard
  ;; transducing-fns. `(filter pred)` and `(dedupe)` are simple so good starting
  ;; points. Here's `(filter pred)`:
  (defn filter-transducing-fn [pred]
    (fn [reducing-fn] ; Like Ring middleware takes a handler
      (fn new-reducing-fn ; Like Ring middleware returns a new-handler
        ([] (reducing-fn))
        ([accumulation] (reducing-fn accumulation))
        ([accumulation input]
           (if (pred input) ; Only change from identity-transducing-fn
             (reducing-fn accumulation input)
             accumulation)))))

  (comment
    (sequence (filter-transducing-fn even?) '(1 2 3 4)) ; -> '(2 4)
    )

  ;; Hope this was useful to someone. Corrections/comments welcome!
  ;; Happy hacking, cheers! :-)
  ;; Peter (https://github.com/ptaoussanis)
)