ptaoussanis/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)
)
	(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)
	)