Skip to content

Instantly share code, notes, and snippets.

@ptaoussanis
Last active December 8, 2024 03:24
Show Gist options
  • Save ptaoussanis/e537bd8ffdc943bbbce7 to your computer and use it in GitHub Desktop.
Save ptaoussanis/e537bd8ffdc943bbbce7 to your computer and use it in GitHub Desktop.
Quick recap/commentary: Clojure transducers
(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)
)
@dkinzer
Copy link

dkinzer commented May 4, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment