[Haskell-cafe] Is the Haskell list comprehension just a Cartesian product machine?

[Albert Y. C. Lai]

On 2021-12-07 9:10 p.m., Galaxy Being wrote:
> If I were a teacher of high-schoolers wanting to add some theory to 
> Haskell could I explain Haskell list comprehensions as basically just a 
> Cartesian/cross product machine? Would this be accurate? And then the 
> combinatorics product rule also seems at play here. I would appreciate 
> any theoretical explanation of what a list comprehension is about.

Short answer is yes.

Level 1:

[ (x,y) | x <- [1,2], y <- [3,4,5] ]

is a cartesian product. This corroborates with that <*> for list does 
cartesian product, i.e.,

pure (,) <*> [1,2] <*> [3,4,5]

And replacing (x,y) by arbitrary f x y does not really change the story.


Level 2:

[ (x,y) | x <- [1,2], y <- [x .. x+x] ]

Do you call that a cartesian product?

I would call it a dependent cartesian product.

{1,2} x (this set depends on the 1 or 2)

On the bright side, I think high-schoolers are flexible enough to accept 
this as a kind of cartesian product, too.

This corroborates with that >>= for list does dependent cartesian 
product, i.e.,

[1,2] >>= \x -> [x .. x+x] >>= \y -> pure (x,y)

Again, replacing (x,y) by arbitrary f x y does not really change the story.


Level 3:

Will you also tell your students about this?

[ (x,y) | x <- [1,2], x > 1, y <- [x .. x+x], y < 3 ]

Some kind of wacky cartesian product that's both dependent and conditional.

This needs empty from Alternative or mzero from MonadPlus:

Define (already in Control.Monad):

guard c = if c then pure () else empty

[1,2]         >>= \x ->
guard (x > 1) >>
[x .. x+x]    >>= \y ->
guard (y < 3) >>
pure (x,y)

{1,2} x (this set depends on the 1 or 2, can be empty) x ...


Have fun.