iteration with the list monad

Question

I'm having trouble understanding how the iterative behavior of the list monad can be derived from its definition.

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

Discussions I've read seem to pass over the question of how >>= creates a control structure, as shown most clearly with do notation:

allEvenOdds :: Int -> [(Int,Int)]
allEvenOdds n = do
  evenValue <- [2,4 .. n]               
  oddValue <- [1,3 .. n]                
  return (evenValue,oddValue)

Is this built in to Haskell, the way I assume the IO monad's interface to actual i/o is?

Answer 1

There's nothing built-in, everything is a simple consequence of the Monad instance you quoted (and, since this example uses do notation, how that desugars to uses of the >>= operator):

allEvenOdds n = do
  evenValue <- [2,4 .. n]               
  oddValue <- [1,3 .. n]                
  return (evenValue,oddValue)

-- desugaring the do notation
allEvenOdds n =
  [2,4 .. n] >>= \evenValue ->
  [1,3 .. n] >>= \oddValue ->
  return (evenValue, oddValue)

-- using the list instance of Monad to replace >>= and return
allEvenOdds n =
  concatMap (\evenValue ->
    concatMap (\oddValue -> [(evenvalue, oddValue)]) [1,3 .. n]
  ) [2,4 .. n]

which you can hopefully easily see "iterates over" both lists and results in a list of all pairs of (even, odd) with values taken from both lists.

At a high level, we can say that the list monad results in iteration simply because concatMap, like map, executes the given function for each element of the list, so it implicitly iterates over the list.