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.