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?

user_8475054 · Answer

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.

user_67579 · Answer

The list instance of the Monad typeclass models nondeterminism: you can see each var <- someList as a for loop like in Python.

The do notation is desugared to [2,4 .. n] >>= (\evenValue -> [1, 3 .. n] >>= (\oddValue -> return (evenValue, oddValue))), so this is equivalent to something in Python like:

    result = []
    for evenValue in range(2, n, 2):
        for oddValue in range(1, n, 2):
            result.append((evenValue, oddValue))

or with list comprehension:

    result = [
        (evenValue, oddValue)
        for evenValue in range(2, n, 2)
        for oddValue in range(1, n, 2)
    ]

This works since for instance Monad [], the expression [2,4 .. n] >>= (\evenValue -> [1, 3 .. n] >>= (\oddValue -> return (evenValue, oddValue))) is thus equivalent to:

concatMap (\evenValue -> [1, 3 .. n] >>= (\oddValue -> return (evenValue, oddValue))) [2,4 .. n]

and thus:

concatMap (\evenValue -> concatMap (\oddValue -> [(evenValue, oddValue)]) [1, 3 .. n]) [2,4 .. n]

But do notation is not "hardwired" to IO: IO is just an instance of Monad that is implemented in such way that one IO action will run before the second one. For lists, it thus is implemented in an equivalent way as spanning Python for loops.

iteration with the list monad

2 Answers