Using monads for trivial tasks like list manipulation?

Question

Whenever I read about Monad example, they always present IO as a case study.

Are there any examples of monads doing list manipulation which somebody could present? I aprpeciate this could be overkill, but I am interested if monads can present advantages over regular list manipulation techniques.

Answer 1

The big secret to the list monad in Haskell is that list comprehensions are syntactic sugar for do blocks. Any time you write a list comprehension, you could have written it using a do block instead, which uses the list monad instance.

A simple example

Let's say you want to take two lists, and return their cartesian product (that is, the list of (x,y) for every combination of x from the first list and y from the second list).

You can do that with a list comprehension:

ghci> [(x,y) | x <- [1,2], y <- [3,4]] -- [(1,3),(1,4),(2,3),(2,4)]

The list comprehension is syntactic sugar for this do block:

zs = do x <- [1,2]
        y <- [3,4]
        return (x,y)

which in turn is syntactic sugar for

zs = [1,2] >>= \x -> [3,4] >>= \y -> return (x,y)

A more complicated example

That example doesn't really demonstrate the power of monads, though, because you could easily write it without relying on the fact that lists have a Monad instance. For example, if we only use the Applicative instance:

ghci> import Control.Applicative
ghci> (,) <$> [1,2] <*> [3,4] -- [(1,3),(1,4),(2,3),(2,4)]

Now let's say you take every element of a list of positive integers, and replicate it as many times as itself (so e.g. f [1,2,3] = [1,2,2,3,3,3] for example). Who knows why you'd want to do that, but it is easy:

ghci> let f xs = [ y | x <- xs, y <- replicate x x ]
ghci> f [1,2,3] -- [1,2,2,3,3,3]

That's just syntactic sugar for this:

f xs = do x <- xs
          y <- replicate x x
          return y

which in turn is syntactic sugar for

f xs = xs >>= \x -> replicate x x >>= \y -> return y

This time we can't write that just using the applicative instance. The key difference is that we took the output from the first bind (x) and made the rest of the block depend on it (y <- replicate x x).

Answer 2

A classic example of using the list monad to cleverly write a "simple" list utility function is this:

import Control.Monad (filterM)

-- | Compute all subsets of the elements of a list.
powerSet :: [a] -> [[a]]
powerSet = filterM (\x -> [True, False])

The type of filterM is Monad m => (a -> m Bool) -> [a] -> m [a]. In the context of the list monad, this is a nondeterministic list filter: a filter operation that takes a nondeterministic predicate that returns a list of alternative answers. The result of filterM is in turn a list of alternative possible results.

Or in simpler language, filterM (\x -> [True, False]) means: for each element of the list, I want both to keep it and throw it away. filterM figures out all possible combinations of doing this for each list element.