Last active
December 8, 2024 03:24
-
-
Save ptaoussanis/e537bd8ffdc943bbbce7 to your computer and use it in GitHub Desktop.
Quick recap/commentary: Clojure transducers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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) | |
) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
into
doesn't return an xform on line 68; https://gist.github.com/ptaoussanis/e537bd8ffdc943bbbce7#file-transducers-clj-L68