> import Control.Monad
> cartesian xs ys =
> 	liftM2 pair xs ys
> 	where pair a b = (a, b)

$ cartesian [1,2,3] [4,5,6]
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Consider my imperative brain just eaten by a monad. I had come to understand monads to be something like a way to string computations together so that they would occur in order. For example:

> printme z = do
> 	print "One"
> 	print "Two"
> 	print $ "Many " ++ z

May the Count and XKCD forgive me, this does just what you’d expect:

$ printme "ah ah ah"
"One"
"Two"
"Many ah ah ah"

Now consider this doozy from the Monad wiki article [1]:

>  a = do x <- [3..4]
> 	[1..2]
> 	return (x, 42)

What do you suppose this does? Straight away it appears that the [1..2] does nothing right? Regardless of the meaning of the x <- [3..4] … right? It’s not so:

$ a
[(3,42),(3,42),(4,42),(4,42)]

Cue confusion.

Let’s simplify that example a bit:

> b = do x <- [3..4]
> 	return (x, 42)

$ b
[(3,42),(4,42)]

Mmm hmm, yeah. x <- [3..4] is really doing something weird here. According to the wiki article [1] the do notation is really just sugar for this:

> a2 = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))

Ok, combine that with the definition:

instance Monad [] where
	m >>= f  = concatMap f m
	return x = [x]
	fail s   = []

(Wait, List is a monad? Yup.)

The article then helpfully goes on to show that replacing >>= with concatMap produces just the list we saw for a. Which is to say, when you use lists in monads you are mapping the values over the remainer of the monad: ala foreach.

To illustrate we have a cartesian product:

> cartesian0 xs ys = do		-- given a list of xs and ys
> 	x <- xs			-- for each x
> 	y <- ys			--   for each y
> 	return $ (x, y)		--     append the tuple (x, y)

On that same page though we have the definition for liftM2 which looks an awful lot like what we just wrote for cartesian0:

liftM2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftM2 op mx my = do
	x <- mx
	y <- my
	return (op x y)

Thus the definition from the top:

cartesian xs ys =
	liftM2 pair xs ys
	where pair a b = (a, b)

But the fun doesn’t stop there! Looks like a pretty slick way to perform a computation that typically would require an accumulator eh? Tada! I give you list comprehensions in disguise. Or rather list comprehensions are monads in disguise [2].

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