Skip to content

Instantly share code, notes, and snippets.

@fogus

fogus/transducers.clj

Forked from ptaoussanis/transducers.clj
Last active August 29, 2015 14:06
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save fogus/f3dbdf5e51139a94d891 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save fogus/f3dbdf5e51139a94d891 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @ptaoussanis ptaoussanis revised this gist Sep 4, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -89,7 +89,7 @@
    (fn transducing-fn [reducing-fn]) -> new-reducing-fn

    ;; I omitted a detail which Rich helped clarify.
    ;; `transduce` _actually_ expects a reducing-fn like so:
    ;; `transduce` _actually_ expects a reducing-fn with 3 (not 2) arities:
    (fn reducing-fn*
    ([])
    ([accumulation]) ; <- This is new (`reduce` would never use this)
  2. @ptaoussanis ptaoussanis revised this gist Sep 4, 2014. 1 changed file with 18 additions and 3 deletions.
    21 changes: 18 additions & 3 deletions transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -113,12 +113,27 @@
    ([accumulation new-input]
    (reducing-fn accumulation new-input))))

    (comment (sequence identity-transducing-fn '(1 2 3 4)) ; -> '(1 2 3 4)
    )
    (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.
    ;; 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
    ;;; 'complete' reducing-fns have 3 arities:
    ([] (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! :-)
  3. @ptaoussanis ptaoussanis revised this gist Sep 4, 2014. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -53,7 +53,7 @@
    ;; fed to some transducer utils. No voodoo, just a clever idea.

    ;;;; Transducer API
    ;;; The following all return transducing-fns:
    ;;; The following all return transducing-fns (note absence of any colls):
    (map f)
    (filter f)
    (remove f)
    @@ -74,7 +74,7 @@
    (random-sample prob) ; new
    ;; or you can just write your own (recall that transducing-fns are just fns)

    ;;; And these utils consume transducing-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`
  4. @ptaoussanis ptaoussanis revised this gist Sep 4, 2014. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -72,10 +72,11 @@
    (mapcat f) ; upcoming
    (dedupe f) ; new
    (random-sample prob) ; new
    (iteration xform coll) ; new
    ;; or you can just write your own (recall that transducing-fns are just fns)

    ;;; And these utils consume transducing-fns:
    (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`
  5. @ptaoussanis ptaoussanis revised this gist Sep 4, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -91,7 +91,7 @@
    ;; `transduce` _actually_ expects a reducing-fn like so:
    (fn reducing-fn*
    ([])
    ([accumulation]) ; <- This is new
    ([accumulation]) ; <- This is new (`reduce` would never use this)
    ([accumulation next-input])
    )

  6. @ptaoussanis ptaoussanis revised this gist Sep 4, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -112,7 +112,7 @@
    ([accumulation new-input]
    (reducing-fn accumulation new-input))))

    (comment (sequence identity-transducer '(1 2 3 4)) ; -> '(1 2 3 4)
    (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
  7. @ptaoussanis ptaoussanis revised this gist Sep 4, 2014. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -107,7 +107,6 @@
    (defn identity-transducing-fn
    [reducing-fn] ; A 'completed' reducing fn (i.e. with 3 arities)
    (fn new-reducing-fn
    ;; Remember reducing-fns need 3 arities:
    ([] (reducing-fn))
    ([accumulation] (reducing-fn accumulation))
    ([accumulation new-input]
  8. @ptaoussanis ptaoussanis revised this gist Sep 4, 2014. 1 changed file with 126 additions and 89 deletions.
    215 changes: 126 additions & 89 deletions transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -1,89 +1,126 @@
    ;; 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:

    ;;; Transducers recap
    ;; * (fn reducer-fn [] [accumulation] [accumulation next-input]) -> val [1].
    ;; * (fn transducer-fn [reducer-fn]) -> new-reducer-fn.
    ;; * So a transducer-fn is a reducer-fn middleware[2], and composes like it.
    ;; * All (numerous!) benefits[4] fall out of this simple +
    ;; not-particularly-impressive-looking[3] definition.
    ;;
    ;; [1] Exactly as per `reduce` docstring. Note 3 possible arities.
    ;; [2] Compare: (fn ring-handler-fn [ring-req]) -> ring-resp,
    ;; (fn ring-middleware-fn [ring-handler]) -> new-ring-handler.
    ;; [3] It's surprisingly easy to miss how big of a deal transducers are.
    ;; [4] Benefits include:
    ;; * Performance:
    ;; * Can reduce w/o incurring any sequence construction costs.
    ;; * Can map composed operations w/o incurring >1 sequence construction cost.
    ;; * Highly efficient filtering + early termination.
    ;; * All the (terrific) benefits of 'Reducers' (parallel fork-join, etc.).
    ;;
    ;; * Convenience:
    ;; * Easy composition through threading, standard fn `comp`, 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.
    ;; * A transducer is just a regular fn with a particular definition used in
    ;; a particular way + some supporting utils (notably `sequence` and
    ;; `transduce`). No complex voodoo, just a clever idea.
    ;;
    ;; * Conceptual:
    ;; * Elegantly & flexibly unifies concepts like:
    ;; * reducing (ordered-seq -> val),
    ;; * mapping (ordered-seq -> transformed-ordered-seq),
    ;; * Reducers (unordered-coll -> val),
    ;; * laziness,
    ;; * process composition.


    ;;;; Transducers API
    ;;; These all return transducers (remember the definition above!)
    (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
    (dedupe f) ; new
    (random-sample prob) ; new

    ;;; And these are utilities (note that they actually take colls)
    (flatmap f coll) ; new, like mapcat (mapcat arity wasn't conducive to adding transducer support)
    (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`


    ;;;; Finally, the identity transducer
    (defn identity-transducer [reducer-fn]
    (fn new-reducer-fn
    ;; Remember reducer-fns need 3 arities:
    ([] (reducer-fn))
    ([accumulation] accumulation)
    ([accumulation new-input]
    (reducer-fn accumulation new-input))))

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

    ;;; Homework
    ;; I found it handy to start with the identity transducer above then
    ;; comparing to (filter f), (take n), etc.

    ;; Hope this was useful to someone, 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[1]:
    (fn reducing-fn ([]) ([accumulation next-input])) -> new-accumulation

    ;; 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:
    (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
    (iteration xform coll) ; new
    ;; or you can just write your own (recall that transducing-fns are just fns)

    ;;; And these utils consume transducing-fns:
    (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 like so:
    (fn reducing-fn*
    ([])
    ([accumulation]) ; <- This is new
    ([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 3 arities)
    (fn new-reducing-fn
    ;; Remember reducing-fns need 3 arities:
    ([] (reducing-fn))
    ([accumulation] (reducing-fn accumulation))
    ([accumulation new-input]
    (reducing-fn accumulation new-input))))

    (comment (sequence identity-transducer '(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.

    ;; Hope this was useful to someone. Corrections/comments welcome!
    ;; Happy hacking, cheers! :-)
    ;; Peter (https://github.com/ptaoussanis)
    )
  9. @ptaoussanis ptaoussanis revised this gist Sep 3, 2014. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -65,8 +65,8 @@
    (iteration xform coll) ; new
    (transduce xform f coll) ; new, like reduce
    (transduce xform f init coll) ; new, like reduce
    (sequence xform coll) ; like lazy-seq
    (sequence xform & colls) ; like lazy-seq
    (sequence xform coll) ; like (lazy) single-coll `map`
    (sequence xform & colls) ; like (lazy) multi-coll `map`


    ;;;; Finally, the identity transducer
  10. @ptaoussanis ptaoussanis created this gist Sep 3, 2014.
    89 changes: 89 additions & 0 deletions transducers.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,89 @@
    ;; 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:

    ;;; Transducers recap
    ;; * (fn reducer-fn [] [accumulation] [accumulation next-input]) -> val [1].
    ;; * (fn transducer-fn [reducer-fn]) -> new-reducer-fn.
    ;; * So a transducer-fn is a reducer-fn middleware[2], and composes like it.
    ;; * All (numerous!) benefits[4] fall out of this simple +
    ;; not-particularly-impressive-looking[3] definition.
    ;;
    ;; [1] Exactly as per `reduce` docstring. Note 3 possible arities.
    ;; [2] Compare: (fn ring-handler-fn [ring-req]) -> ring-resp,
    ;; (fn ring-middleware-fn [ring-handler]) -> new-ring-handler.
    ;; [3] It's surprisingly easy to miss how big of a deal transducers are.
    ;; [4] Benefits include:
    ;; * Performance:
    ;; * Can reduce w/o incurring any sequence construction costs.
    ;; * Can map composed operations w/o incurring >1 sequence construction cost.
    ;; * Highly efficient filtering + early termination.
    ;; * All the (terrific) benefits of 'Reducers' (parallel fork-join, etc.).
    ;;
    ;; * Convenience:
    ;; * Easy composition through threading, standard fn `comp`, 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.
    ;; * A transducer is just a regular fn with a particular definition used in
    ;; a particular way + some supporting utils (notably `sequence` and
    ;; `transduce`). No complex voodoo, just a clever idea.
    ;;
    ;; * Conceptual:
    ;; * Elegantly & flexibly unifies concepts like:
    ;; * reducing (ordered-seq -> val),
    ;; * mapping (ordered-seq -> transformed-ordered-seq),
    ;; * Reducers (unordered-coll -> val),
    ;; * laziness,
    ;; * process composition.


    ;;;; Transducers API
    ;;; These all return transducers (remember the definition above!)
    (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
    (dedupe f) ; new
    (random-sample prob) ; new

    ;;; And these are utilities (note that they actually take colls)
    (flatmap f coll) ; new, like mapcat (mapcat arity wasn't conducive to adding transducer support)
    (iteration xform coll) ; new
    (transduce xform f coll) ; new, like reduce
    (transduce xform f init coll) ; new, like reduce
    (sequence xform coll) ; like lazy-seq
    (sequence xform & colls) ; like lazy-seq


    ;;;; Finally, the identity transducer
    (defn identity-transducer [reducer-fn]
    (fn new-reducer-fn
    ;; Remember reducer-fns need 3 arities:
    ([] (reducer-fn))
    ([accumulation] accumulation)
    ([accumulation new-input]
    (reducer-fn accumulation new-input))))

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

    ;;; Homework
    ;; I found it handy to start with the identity transducer above then
    ;; comparing to (filter f), (take n), etc.

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