3 ms·

It amazes me that Haskell takes my Python hack and actually allows it to be expressed quite naturally! I'm curious what the semantics are for the interleaving o

by brilee 10y ago

It amazes me that Haskell takes my Python hack and actually allows it to be expressed quite naturally! I'm curious what the semantics are for the interleaving of do and guard - would you say that Haskell will compile that code to the equivalent nested for loops, with the same short-circuiting as in the Python version? Or is there something fancier going on?

conistonwater 10y ago
There isn't any magic going on, but remember that Haskell's lists are lazy: to write a truly equivalent version in Python would be a little tricky because you'd have to deal with generators. But the conversion from do+guard to list comprehensions is really simple (see the definition in source at https://hackage.haskell.org/package/base-4.9.0.0/docs/src/GHC.Base.html#line-748 https://hackage.haskell.org/package/base-4.9.0.0/docs/src/GH... and use the way the do-notation desugars into applications of (>>=) and (>>)), the definition of guard itself is similarly trivial: https://hackage.haskell.org/package/base-4.9.0.0/docs/src/Control.Monad.html#guard https://hackage.haskell.org/package/base-4.9.0.0/docs/src/Co...). It's so much easier to see all this by just working out a small example for yourself with pen and paper. So these two are equivalent, and the list comprehension version is very close to what nested loops (read it from left to right) would give you, except for the laziness. do x <- [1, 2, 3]; guard (f x); y <- [1, 2, 3]; guard (g x y); z <- [1, 2, 3]; guard (h x y z); return (x, y, z) [(x, y, z) | x <- [1, 2, 3], f x, y <- [1, 2, 3], g x y, z <- [1, 2, 3], h x y z] for x in [1, 2, 3] { if (f(x)) { for y in [1, 2, 3] { if (g(x,y)) { for z in [1, 2, 3] { if (h(x,y,z)) { yield((x, y, z)) }}}}}} -- "pseudocode" The guard uses the following idea: guard True = [()] guard False = [] So _ <- guard True is a noop, while _ <- guard False short-circuits the list comprehension the way "continue" would (just like "for x in [] { ... }"), so guard (f x) becomes the test f x in the list comprehension.
wz1000 10y ago
> It amazes me that Haskell takes my Python hack and actually allows it to be expressed quite naturally! This isn't an accident. Python's list comprehensions were modeled on Haskell's list comprehensions, which were in turn modeled on the much more general concepts of monads. Haskell's do notation provides a nice syntactic sugar for monadic code. Since lists form a monad, such code is quite naturally expressed using do notation. Haskell's list comprehensions can be directly translated to do notation [x+y | x <- [1..10], y <- [1..10], x+y<5] can be translated into do x <- [1..10] y <- [1..10] guard (x+y<5) return (x+y) which is syntactic sugar for [1..10] >>= (\x -> [1..10] >>= (\y -> guard (x+y<5) >> return (x+y))) where (>>=) is the monadic bind operator.
- ky3 10y ago
  > Python's list comprehensions were modeled on Haskell's list comprehensions, which were in turn modeled on the much more general concepts of monads. It's true that Python borrowed the concept from Haskell. But Haskell in turn took the concept from set theory, not category theory. List comprehensions are modeled after set comprehensions. Here's an example that uses set-builder notation [0] to define the set of Pythagorean triples with sides bounded by 10: { (x,y,z) | x,y,z \in {1,2,...,10}, x^2 + y^2 = z^2 } In Haskell that becomes let u=[1..10] in [ (x,y,z) | x<-u,y<-u,z<-u, x^2 + y^2 = z^2 ] The creators of Haskell worked hard to make sure the syntax was a spitting image of set theory. For a motivation behind the creation of Haskell was to use it to as a lightweight calculator / computer algebra system (sans heavy algebra) to teach set theory to students. List comprehensions have been around since the dawn of Haskell. It was around even before Haskell, viz. in Miranda circa mid-80s. Moggi's work on PL monads was only published in 1991. I think you've mixed up monad comprehensions--which came much later--which is the observation that this notation and concept can be generalized to monads other than lists. Monad comprehensions segue into topos theory, understood as a monadic generalization of set theory, quite nicely. Hopefully, the next 700 monad tutorials will give more visibility to topos theory. [0] https://en.wikipedia.org/wiki/Set-builder_notation https://en.wikipedia.org/wiki/Set-builder_notation

by brilee 10y ago

conistonwater 10y ago

There isn't any magic going on, but remember that Haskell's lists are lazy: to write a truly equivalent version in Python would be a little tricky because you'd have to deal with generators. But the conversion from do+guard to list comprehensions is really simple (see the definition in source at https://hackage.haskell.org/package/base-4.9.0.0/docs/src/GHC.Base.html#line-748 https://hackage.haskell.org/package/base-4.9.0.0/docs/src/GH... and use the way the do-notation desugars into applications of (>>=) and (>>)), the definition of guard itself is similarly trivial: https://hackage.haskell.org/package/base-4.9.0.0/docs/src/Control.Monad.html#guard https://hackage.haskell.org/package/base-4.9.0.0/docs/src/Co...). It's so much easier to see all this by just working out a small example for yourself with pen and paper. So these two are equivalent, and the list comprehension version is very close to what nested loops (read it from left to right) would give you, except for the laziness. do x <- [1, 2, 3]; guard (f x); y <- [1, 2, 3]; guard (g x y); z <- [1, 2, 3]; guard (h x y z); return (x, y, z) [(x, y, z) | x <- [1, 2, 3], f x, y <- [1, 2, 3], g x y, z <- [1, 2, 3], h x y z] for x in [1, 2, 3] { if (f(x)) { for y in [1, 2, 3] { if (g(x,y)) { for z in [1, 2, 3] { if (h(x,y,z)) { yield((x, y, z)) }}}}}} -- "pseudocode" The guard uses the following idea: guard True = [()] guard False = [] So _ <- guard True is a noop, while _ <- guard False short-circuits the list comprehension the way "continue" would (just like "for x in [] { ... }"), so guard (f x) becomes the test f x in the list comprehension.

wz1000 10y ago

> It amazes me that Haskell takes my Python hack and actually allows it to be expressed quite naturally! This isn't an accident. Python's list comprehensions were modeled on Haskell's list comprehensions, which were in turn modeled on the much more general concepts of monads. Haskell's do notation provides a nice syntactic sugar for monadic code. Since lists form a monad, such code is quite naturally expressed using do notation. Haskell's list comprehensions can be directly translated to do notation [x+y | x <- [1..10], y <- [1..10], x+y<5] can be translated into do x <- [1..10] y <- [1..10] guard (x+y<5) return (x+y) which is syntactic sugar for [1..10] >>= (\x -> [1..10] >>= (\y -> guard (x+y<5) >> return (x+y))) where (>>=) is the monadic bind operator.

ky3 10y ago
> Python's list comprehensions were modeled on Haskell's list comprehensions, which were in turn modeled on the much more general concepts of monads. It's true that Python borrowed the concept from Haskell. But Haskell in turn took the concept from set theory, not category theory. List comprehensions are modeled after set comprehensions. Here's an example that uses set-builder notation [0] to define the set of Pythagorean triples with sides bounded by 10: { (x,y,z) | x,y,z \in {1,2,...,10}, x^2 + y^2 = z^2 } In Haskell that becomes let u=[1..10] in [ (x,y,z) | x<-u,y<-u,z<-u, x^2 + y^2 = z^2 ] The creators of Haskell worked hard to make sure the syntax was a spitting image of set theory. For a motivation behind the creation of Haskell was to use it to as a lightweight calculator / computer algebra system (sans heavy algebra) to teach set theory to students. List comprehensions have been around since the dawn of Haskell. It was around even before Haskell, viz. in Miranda circa mid-80s. Moggi's work on PL monads was only published in 1991. I think you've mixed up monad comprehensions--which came much later--which is the observation that this notation and concept can be generalized to monads other than lists. Monad comprehensions segue into topos theory, understood as a monadic generalization of set theory, quite nicely. Hopefully, the next 700 monad tutorials will give more visibility to topos theory. [0] https://en.wikipedia.org/wiki/Set-builder_notation https://en.wikipedia.org/wiki/Set-builder_notation