How does the List monad work in this example?

Question

The List monad has return x = [x]. So why in the following example is the result not [(["a", "b"], [2, 3])]?

> pairs a b = do { x <- a; y <- b; return (x, y)}
> pairs ["a", "b"] [2,3]
[("a",2),("a",3),("b",2),("b",3)]

Answer 1

Let us first analyze and rewrite the function pairs:

pairs a b = do { x <- a; y <- b; return (x, y)}

Here we thus have a monad. We use do as syntactical sugar. But the compiler rewrites this to:

pairs a b = a >>= (\x -> b >>= (\y -> return (x, y)))

Or in a more canonical form:

pairs a b = (>>=) a (\x -> (>>=) b (\y -> return (x, y)))

Now the list monad is defined as:

instance Monad [] where
    return x = [x]
    (>>=) xs f = concatMap f xs

So we have written:

pairs a b = concatMap (\x -> concatMap (\y -> [(x, y)]) b) a

So we thus take as input two lists a and b, and we perform a concatMap on a with as function (\x -> concatMap (\y -> [(x, y)]) b). In that function we perform another concatMap on b with as function \y -> [(x, y)].

So if we evaluate this with pairs ["a", "b"] [2,3] we get:

   pairs ["a", "b"] [2,3]
-> concatMap (\x -> concatMap (\y -> [(x, y)]) [2,3]) ["a", "b"]
-> concatMap (\y -> [("a", y)]) [2,3] ++ concatMap (\y -> [("b", y)]) [2,3]
-> [("a", 2)] ++ [("a", 3)] ++ [("b", 2)] ++ [("b", 3)]
-> [("a", 2), ("a", 3), ("b", 2), ("b", 3)]