Haskell Monad – How does Monad on list work?

Wadler, School of Haskell, LYAH, HaskellWiki, Quora and many more describe the list monad.

Compare:

• (=<<) :: Monad m => (a -> m b) -> m a -> m b for lists with
• concatMap :: (a -> [b]) -> [a] -> [b] for m = [].

The regular (>>=) bind operator has the arguments flipped, but is otherwise just an infix concatMap.

Or quite simply my confusion seems to stem from not understanding how this statement actually works:

(>>|) xs f = [ y | x <- xs, y <- f x ]

Since list comprehensions are equivalent to the Monad instance for lists, this definition is kind of cheating. You’re basically saying that something is a Monadd in the way that it’s a Monad, so you’re left with two problems: Understanding list comprehensions, and still understanding Monad.

List comprehensions can be de-sugared for a better understanding:

• Removing syntactic sugar: List comprehension in Haskell

In your case, the statement could be written in a number of other ways:

• Using do-notation:

  (>>|) xs f = do x <- xs
                  y <- f x
                  return y
  

• De-sugared into using the (>>=) operator:

  (>>|) xs f = xs >>= \x ->
               f x >>= \y ->
               return y
  

• This can be shortened (one rewrite per line):

    (>>|) xs f = xs >>= \x -> f x >>= \y -> return y -- eta-reduction
  ≡ (>>|) xs f = xs >>= \x -> f x >>= return         -- monad identity
  ≡ (>>|) xs f = xs >>= \x -> f x                    -- eta-reduction
  ≡ (>>|) xs f = xs >>= f                            -- prefix operator
  ≡ (>>|) xs f = (>>=) xs f                          -- point-free
  ≡ (>>|) = (>>=)
  

So from using list comprehensions, you haven’t really declared a new definition, you’re just relying on the existing one. If you wanted, you could instead define your instance Monadd [] without relying on existing Monad instances or list comprehensions:

• Using concatMap:

  instance Monadd [] where
    (>>|) xs f = concatMap f xs
  

• Spelling that out a little more:

  instance Monadd [] where
    (>>|) xs f = concat (map f xs)
  

• Spelling that out even more:

  instance Monadd [] where
    (>>|) [] f = []
    (>>|) (x:xs) f = let ys = f x in ys ++ ((>>|) xs f)
  

The Monadd type class should have something similar to return. I’m not sure why it’s missing.