Haskell Language Monads List Monad


The lists form a monad. They have a monad instantiation equivalent to this one:

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

We can use them to emulate non-determinism in our computations. When we use xs >>= f, the function f :: a -> [b] is mapped over the list xs, obtaining a list of lists of results of each application of f over each element of xs, and all the lists of results are then concatenated into one list of all the results. As an example, we compute a sum of two non-deterministic numbers using do-notation, the sum being represented by list of sums of all pairs of integers from two lists, each list representing all possible values of a non-deterministic number:

sumnd xs ys = do
  x <- xs
  y <- ys
  return (x + y)

Or equivalently, using liftM2 in Control.Monad:

sumnd = liftM2 (+)

we obtain:

> sumnd [1,2,3] [0,10]