4 ms·

This sounds something like transducers in Clojure, I’d be curious to see how they compare! Fascinating to see similar ideas emerging in various places. (It’s po

This sounds something like transducers in Clojure, I’d be curious to see how they compare! Fascinating to see similar ideas emerging in various places. (It’s possible Clojure borrowed some concepts here as I know Rich Hickey often discusses how Haskell has solved a particular problem when discussing a Clojure approach.)

dwohnitmok 5y ago
This is different from transducers in Clojure (note how `dept` and `salary` show up in multiple levels despite not being manually threaded through). This is much more similar to the way SQL syntax works. Transducers in Haskell (and really in any language, including in Clojure) are functions of the form `a -> List b` (yes this is a fully polymorphic transducer despite the use of `List`; it can be applied to concrete data structures as well as e.g. streams of the form found in core.async, I can explain more if you're interested). I actually think the design of transducers is a bit of a wart in Clojure. Clojure usually goes for the least powerful abstraction (so e.g. data < higher-order functions < macros), but for some reason when designing transducers decided to move away from the simple `List` based approach and instead do a Church encoding of the list to end up with a higher-order function. I wonder if it was performance related (although I'd be slightly surprised to see a higher-order function performing better)? One of these days I hope to see a library expressing the alternative form of transducers since I find those much much easier to understand and write from scratch without pre-existing transducer generating functions.
- patrickthebold 5y ago
  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.

dwohnitmok 5y ago

This is different from transducers in Clojure (note how `dept` and `salary` show up in multiple levels despite not being manually threaded through). This is much more similar to the way SQL syntax works. Transducers in Haskell (and really in any language, including in Clojure) are functions of the form `a -> List b` (yes this is a fully polymorphic transducer despite the use of `List`; it can be applied to concrete data structures as well as e.g. streams of the form found in core.async, I can explain more if you're interested). I actually think the design of transducers is a bit of a wart in Clojure. Clojure usually goes for the least powerful abstraction (so e.g. data < higher-order functions < macros), but for some reason when designing transducers decided to move away from the simple `List` based approach and instead do a Church encoding of the list to end up with a higher-order function. I wonder if it was performance related (although I'd be slightly surprised to see a higher-order function performing better)? One of these days I hope to see a library expressing the alternative form of transducers since I find those much much easier to understand and write from scratch without pre-existing transducer generating functions.

patrickthebold 5y ago
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.