4 ms·

Haskell's comprehension syntax is very powerful and quite a bit more general than what is described here. It can both be generalized to arbitrary monads throug

Haskell's comprehension syntax is very powerful and quite a bit more general than what is described here. It can both be generalized to arbitrary monads through `MonadComprehension` and has extended syntax that brings in basic SQL operators (such as grouping and sorting) through `TransformListComp` as well as zipping through `ParallelListComp`. The links are respectively https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/monad_comprehensions.html https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/mona..., https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/generalised_list_comprehensions.html https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/gene..., and https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/parallel_list_comprehensions.html https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/para.... And what's more is that all three of these play very nicely with each other, so that you can write SQL-like syntax to deal with say an arbitrary, side-effectful stream rather than a finite data structure. That means you can write something like (to take the example from the `TransformListComp` docs) output = [ (the dept, sum salary) | (name, dept, salary) <- employees , then group by dept using groupWith , then sortWith by (sum salary) , then take 5 ] where `employees` is e.g. a paginated HTTP endpoint that you're hitting. It can make for some very nice code.

mbauman 5y ago
Conversely, Julia's comprehension syntax is very powerful and quite a bit more general than what is described here — but in a different way. - They're not list comprehensions, they're one-dimensional vector comprehensions. And they seamlessly extend to multidimensional array comprehensions. - Just drop the square brackets and instead of a dense array you get a lazy generator!
- anyfoo 5y ago
  Correct me if I'm wrong, but doesn't them being Monad comprehensions in Haskell automatically mean that Haskell's "list" comprehensions can be all of those things as well, and more? As well as the language's laziness by default that pretty much encompasses the generator aspect in general anyways. (Although I'm not really trying to pit anything against each other here, they are different languages with different requirements.)
  - mbauman 5y ago
    See the cousin discussion below on multidimensional arrays in Haskell.
mapgrep 5y ago
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.

mbauman 5y ago

Conversely, Julia's comprehension syntax is very powerful and quite a bit more general than what is described here — but in a different way. - They're not list comprehensions, they're one-dimensional vector comprehensions. And they seamlessly extend to multidimensional array comprehensions. - Just drop the square brackets and instead of a dense array you get a lazy generator!

anyfoo 5y ago
Correct me if I'm wrong, but doesn't them being Monad comprehensions in Haskell automatically mean that Haskell's "list" comprehensions can be all of those things as well, and more? As well as the language's laziness by default that pretty much encompasses the generator aspect in general anyways. (Although I'm not really trying to pit anything against each other here, they are different languages with different requirements.)
- mbauman 5y ago
  See the cousin discussion below on multidimensional arrays in Haskell.

mapgrep 5y ago

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.