4 ms·

I'm curious as to how your definition of transducer is the same as the standard one in clojure.

dwohnitmok 5y ago
This is one of those times where types really make some equivalences clear that look completely unrelated at runtime. The constructors for a list have the types Nil : List a Cons : a -> List a -> List a By a Church encoding (or more accurately a Boehm-Berarducci encoding) you end up with an equivalent higher order function that encodes a list of the following type: -- Boehm-Berarducci List type BBList a = forall b. b -> (b -> a -> b) -> b I'm glossing over the details here, but you can basically squint and see how the first `b` corresponds to `nil` and the second to `cons` (and the two are truly equivalent, you can have functions going from `List a -> BBList a` and `BBList a -> List a` losslessly). So what then let's plug `BBList` in for `List` in `a -> List b`. a -> List b -- BBList is equivalent to List a -> BBList b -- Expand out our definition of BBList -- We change type variables as necessary a -> forall c. c -> (c -> b -> c) -> c -- Remove a redundant forall (we can move all the way to the left) a -> c -> (c -> b -> c) -> c -- Rearrange arguments (c -> b -> c) -> c -> a -> c And voila that's a tranducer (see https://news.ycombinator.com/item?id=8144385 https://news.ycombinator.com/item?id=8144385)! Now that's how you could see at a glance from the types that they're equivalent. To understand what this means at runtime, it's helpful to think of the output list as the elements "you wish to keep" and everything not in that list as what you discard when composed with other transducers. So here's some transducers implemented in the direct list style. (defn duplicate [x] [x x]) (defn keep-if-even [x] (if (even? x) [x] [])) (defn map [f] (fn [x] [(f x)])) The crucial thing (and why these transducers are still polymorphic) is that these collections are ephemeral: they go away in the final step of something like `into`. Now composing this list-based transducers would require a special composition function (one that composes `a -> List b` with `b -> List c` to get `a -> List c`, basically `mapcat` in Clojure), but I actually regard that as a plus. It's always seemed like an accidental hack that transducers are composable with normal function composition. They compose "the wrong way" and you can't really compose them with normal functions anyways. On a performance note, one of the reasons you'd want to use transducers is to reduce collection overhead, so you probably want to use transients since these are ephemeral anyways and you probably don't want to use actual vectors or actual lists. Instead you want to use collections that are heavily optimized for zero element, one element, and two element cases (as those are by far the most common situations you'll run into). With those optimizations in place you would have almost no new object/collection creation and I suspect that this will have better performance than the current higher order function-based implementation and top of that it'll be far simpler. For a link that goes into greater detail about this see: https://stackoverflow.com/questions/26653829/how-is-a-transducer-different-from-a-partially-applied-function https://stackoverflow.com/questions/26653829/how-is-a-transd... I've also glossed over some details here so let me know if you want me to elaborate anywhere. I really hope that this gets implemented at some point because current Clojure transducers seem like a wart in the language.
- patrickthebold 5y ago
  This is great. I've always been fascinated by transducers.
- funcDropShadow 5y ago
  This use of a church encoding to generalize over strict and lazy iterations of almost arbitrary data structures and streams has been constructed and described by Oleg Kiselyov [1] long before transducers and many Haskell implementations . This page is a treasure trove of computer science theory and their applications in functional programming. [1]: http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.h... and http://okmij.org/ftp/Streams.html http://okmij.org/ftp/Streams.html
  - dwohnitmok 5y ago
    Oleg is great. In this case we're actually going the opposite direction (going back to a concrete data structure). His stream fusion stuff is really cool, but I don't know of any popular libraries that have incorporated unfortunately. I think the Scala fs2 stream library was interested in trying to implement some of the ideas some years back, but I think they ended up not having the time or energy.

This is one of those times where types really make some equivalences clear that look completely unrelated at runtime. The constructors for a list have the types Nil : List a Cons : a -> List a -> List a By a Church encoding (or more accurately a Boehm-Berarducci encoding) you end up with an equivalent higher order function that encodes a list of the following type: -- Boehm-Berarducci List type BBList a = forall b. b -> (b -> a -> b) -> b I'm glossing over the details here, but you can basically squint and see how the first `b` corresponds to `nil` and the second to `cons` (and the two are truly equivalent, you can have functions going from `List a -> BBList a` and `BBList a -> List a` losslessly). So what then let's plug `BBList` in for `List` in `a -> List b`. a -> List b -- BBList is equivalent to List a -> BBList b -- Expand out our definition of BBList -- We change type variables as necessary a -> forall c. c -> (c -> b -> c) -> c -- Remove a redundant forall (we can move all the way to the left) a -> c -> (c -> b -> c) -> c -- Rearrange arguments (c -> b -> c) -> c -> a -> c And voila that's a tranducer (see https://news.ycombinator.com/item?id=8144385 https://news.ycombinator.com/item?id=8144385)! Now that's how you could see at a glance from the types that they're equivalent. To understand what this means at runtime, it's helpful to think of the output list as the elements "you wish to keep" and everything not in that list as what you discard when composed with other transducers. So here's some transducers implemented in the direct list style. (defn duplicate [x] [x x]) (defn keep-if-even [x] (if (even? x) [x] [])) (defn map [f] (fn [x] [(f x)])) The crucial thing (and why these transducers are still polymorphic) is that these collections are ephemeral: they go away in the final step of something like `into`. Now composing this list-based transducers would require a special composition function (one that composes `a -> List b` with `b -> List c` to get `a -> List c`, basically `mapcat` in Clojure), but I actually regard that as a plus. It's always seemed like an accidental hack that transducers are composable with normal function composition. They compose "the wrong way" and you can't really compose them with normal functions anyways. On a performance note, one of the reasons you'd want to use transducers is to reduce collection overhead, so you probably want to use transients since these are ephemeral anyways and you probably don't want to use actual vectors or actual lists. Instead you want to use collections that are heavily optimized for zero element, one element, and two element cases (as those are by far the most common situations you'll run into). With those optimizations in place you would have almost no new object/collection creation and I suspect that this will have better performance than the current higher order function-based implementation and top of that it'll be far simpler. For a link that goes into greater detail about this see: https://stackoverflow.com/questions/26653829/how-is-a-transducer-different-from-a-partially-applied-function https://stackoverflow.com/questions/26653829/how-is-a-transd... I've also glossed over some details here so let me know if you want me to elaborate anywhere. I really hope that this gets implemented at some point because current Clojure transducers seem like a wart in the language.

patrickthebold 5y ago
This is great. I've always been fascinated by transducers.
funcDropShadow 5y ago
This use of a church encoding to generalize over strict and lazy iterations of almost arbitrary data structures and streams has been constructed and described by Oleg Kiselyov [1] long before transducers and many Haskell implementations . This page is a treasure trove of computer science theory and their applications in functional programming. [1]: http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.h... and http://okmij.org/ftp/Streams.html http://okmij.org/ftp/Streams.html
- dwohnitmok 5y ago
  Oleg is great. In this case we're actually going the opposite direction (going back to a concrete data structure). His stream fusion stuff is really cool, but I don't know of any popular libraries that have incorporated unfortunately. I think the Scala fs2 stream library was interested in trying to implement some of the ideas some years back, but I think they ended up not having the time or energy.