[HN Gopher] Transducer: Composition, abstraction, performance (2...
___________________________________________________________________
Transducer: Composition, abstraction, performance (2018)
Author : defmarco
Score : 100 points
Date : 2025-11-04 10:32 UTC (4 days ago)
(HTM) web link (funktionale-programmierung.de)
(TXT) w3m dump (funktionale-programmierung.de)
| dwohnitmok wrote:
| This is maybe as good a time as any to discuss the usual
| alternative presentation of transducers that I find is a far
| gentler introduction.
|
| A transducer is simply a function of the form `a -> List<b>`. Yes
| this is fully polymorphic, i.e. it holds even for transducers
| that only operate over just lists.
|
| In this case `mapping` is just
|
| This lens views a transducer through the lens of the `eduction`
| function as a more souped up `map`. Whereas with a normal `map`
| you only get to use a function `a -> b`, which means you can't
| change the underlying structure, with `eduction` you get to use
| `a -> List<b>` (again a transducer), where you "keep" any
| elements that are in the output list and you "discard" any
| elements not in the output list.
|
| So e.g. `mapping` would be: (defn mapping [f]
| (fn [x] [(f x)]))
|
| or in Python def mapping(f): return
| lambda x: [f(x)]
|
| and `filtering` would be: (defn filtering [f]
| (fn [x] [if (f x) [x] []]))
|
| or in Python def filtering(f):
| return lambda x: [x] if f(x) else []
|
| In my opinion way clearer and easier!
|
| For more details on the full equivalence see
| https://news.ycombinator.com/item?id=27778423
|
| The current presentation of transducers has always felt like a
| wart in Clojure.
| lispybanana wrote:
| Nicely done.
| jodleif wrote:
| Did you mean list<a> -> b? To my mind a transducer is a
| tranform + reducer
| dwohnitmok wrote:
| No I meant `a -> List<b>`. This is because a list is itself a
| fold (which is a reducer with an additional base case).
| lgrapenthin wrote:
| A transducer transforms a reducing function. Its signature is
| rfn->rfn. The resulting rfn can then be used to reduce/fold
| from any collection/stream type into any other
| collection/stream type.
|
| I don't see what your functions have to do with that.
| dwohnitmok wrote:
| (HN is going to collapse this comment because the code makes
| it too long).
|
| My functions are exactly equivalent to transducers.
|
| My link in the original comment goes over it at a more
| theoretical level.
|
| But if you want runnable code, I've included Clojure below
| that translates between the two representations (there's some
| annoying multi-arity stuff I haven't handled very rigorously,
| but that's mainly an artifact of the complection in the
| traditional Clojure representation of transducers and goes
| away when you think of them as just `a -> List<b>`).
|
| There's a line in the original article that the author
| doesn't go far enough on. "Everything is a fold." Yes more
| than that, folding is not just a function over a list, a fold
| _is_ a list and vice versa (this holds for any algebraic
| datatype). Transducers are just one example of this, where
| Clojure has decided to turn a concrete data structure into a
| higher order function (wrongly I believe; although I haven 't
| gone to the effort of truly specializing all my functions to
| verify my suspicions that you can actually get even better
| performance with the concrete data representation as long as
| you use specialized data containers with specialized behavior
| for the zero and one element cases). (defn
| tmap "Map transducer" [f] (fn [x] [(f
| x)])) (defn tfilter "Filter transducer"
| [f] (fn [x] (if (f x) [x] []))) (defn
| ttake "Take n elements" [n] (let
| [n-state (volatile! n)] (fn [x]
| (let [current-n @n-state] (if (pos? current-n)
| (do (vswap! n-state dec) [x]) [])))))
| (defn simple-transducer->core-transducer [simple-
| transducer] (fn [rf] (fn
| ([] (rf)) ([result] (rf result))
| ([result input] (reduce rf result (simple-
| transducer input)))))) (defn core-
| transducer->simple-transducer [core-transducer]
| (fn [x] ((core-transducer #(cons %2 %1))
| [] x))) (defn catcomp ([f g] (fn
| [x] (mapcat g (f x)))) ([f g & fs] (reduce
| catcomp (catcomp f g) fs))) (def example-simple-
| transducer (catcomp (tmap inc)
| (tfilter even?) (tmap inc) (ttake 2)))
| (defn example-simple-transducer-manual [x]
| (->> ((tmap inc) x) (mapcat (tfilter even?))
| (mapcat (tmap inc)) ;; Stateful transducers are
| hard to work with manually ;; You have to define
| it outside of the function to maintain the state
| ;; This is true for traditional transducers as well
| ;; (mapcat (ttake 2)) )) (def
| example-core-transducer (comp (map inc)
| (filter even?) (map inc) (take 2)))
| ;; Yields [3 5] (into [] (simple-transducer->core-
| transducer example-simple-transducer) [1 2 3 4 5])
| ;; Also yields [3 5] (into [] example-core-transducer
| [1 2 3 4 5]) ;; Yields [3] (simple-
| transducer 1) ;; Also yields [3] ((core-
| transducer->simple-transducer example-core-transducer) 1)
| roenxi wrote:
| A popular noob error in Clojure is to get really, really excited
| about using reduce and trying to use it to replace for loops.
| Maybe someone wants to sum up every other odd number and they
| build some horrible reducer to do that which manages its own
| state in the reduction object. It leads to ugly code. Reduce and
| it's colleague map are most powerful when the underlying
| collection could have been be shuffled and it wouldn't matter
| much - or at least where the state to be managed in the reduce is
| trivial.
|
| So something to note about transduce is that it looks a lot like
| reduce but suddenly the examples [0] start being more complex
| functions where some elements of the collection get removed,
| order matters and state begins to appear during the fold.
| Functions like `take`, `filter`, `partition`, `interpose`,
| `dedupe`, etc, etc.
|
| As with many things in the functional world ( _cough_ monads) I
| feel the explanations don 't make a lot of sense before meeting
| the problem they solve in the wild. As with a lot of Clojure's
| better parts transducers are a state management tool.
|
| [0] https://clojure.org/reference/transducers
| jwr wrote:
| Transducers are IMHO one of the most under-appreciated features
| of Clojure. If you want a really good intro, watch Rich Hickey's
| talk about transducers:
| https://www.youtube.com/watch?v=6mTbuzafcII (Rich is an excellent
| speaker and most of his talks are really worth watching, even if
| you don't use Clojure).
|
| The thing about transducers is that once you start using them,
| the abstractions click in your mind and you start using them more
| and more in your code. Many things our software does can be
| looked at as pipelines, and transducers let you write composable
| functions and put them together into pipelines. As you see more
| pipelines in your code, you will write those composable functions
| and reuse them in various places.
|
| Experienced Clojure programmers will rarely use loops, for me
| transducers are the #1 choice whenever I have to process a
| collection of any kind.
|
| Their efficiency (no intermediate collections!) is a nice bonus
| -- you get both high-level composable code _and_ efficiency,
| which is incredible.
|
| One thing I dislike about transducers is when I need a stateful
| one: these are hard to understand and _very_ difficult to write.
| I rarely do this, except when I _really_ want to stick to the
| transducer abstraction and I have a couple of hours to spend on a
| puzzle. But you rarely need to write your own stateful
| transducers, usually the built-in ones are enough (things like
| take /drop).
| bjoli wrote:
| I wrote srfi-171, which inplements transducers for scheme:
| https://srfi.schemers.org/srfi-171/srfi-171.html
|
| It starting to be quite some time ago, but I can answer some
| questions if you have any.
___________________________________________________________________
(page generated 2025-11-08 23:02 UTC)