So I needed to write code to calculate the Cartesian product of two lists, and I happened to be using Haskell since I was writing a tiny prototype of tree kernels*.

That’s easy to do imperatively (Python):

acc = []
for x in xs:
  for y in ys:
    acc.append((x,y))

Or with a list comprehension (Haskell):

cartesian (xs,ys) = [(x,y) | x <- xs, y <- ys]

But Python and Haskell’s list comprehensions both put the expression first and the generators afterwards, like math notation. I prefer the way Scala and C#/F# do it, with the generators first and the expression afterward. Normally I wouldn’t worry about it much, but I was reading the Wikipedia page on using monads and I found a real example of using the List monad with do notation. This is rare. Usually, the List monad is described in papers right between the Maybe monad and IO monad, sort of in passing, so the examples were subpar and never really made sense to me.

So now I know that it’s trivial to turn the above list comprehension around to use do notation.

cartesian (xs,ys) = do { x <- xs; y <- ys; return (x,y) }

Syntactically, it looks a little noisier to me, but that’s probably because I don’t like braces, semi-colons or return (and if you’re used to other languages, the do/return pair looks weird compared to the normal for/yield). I do like having the generators show up first. Semantically, there is no change in the result, only the type, which now allows you to pass other kinds of things besides lists:

*Main> cartesian ([1..4], [1..2])
[(1,1),(1,2),(2,1),(2,2),(3,1),(3,2),(4,1),(4,2)]  -- normal, with lists
*Main> cartesian (Just 4, Just 2)  -- Maybe monad
Just (4,2)
*Main> cartesian (Nothing, Just 4)  -- oh no! Nothing! Abort! Abort!
Nothing

So do gives you automatic flattening for lists, just like list comprehensions. For Maybe (which are much like nullable types), you get automatic null propagation–if either xs or ys is Nothing, then you don’t get your (x,y) answer–you get Nothing instead.

Incidentally, here is a generalised Cartesian product, although it may be kind of slow since it’s recursive. It’s called cross because that’s the wrong name I normally use.

cross [] = [[]]
cross (l:ls) = [x:rest | x <- l, rest <- cross ls]