Monads

class Applicative_ t => Monad_ (t :: * -> *) where
    andThen :: t a -> (a -> t b) -> t b

Laws (in addition to those for Functor_ and Applicative_):

1. Left identity:
   pure a `andThen` f === f a
2. Right identity:
   ma `andThen` pure === ma
3. Associativity: (ma `andThen` f) `andThen` g === ma `andThen` (\x -> f x `andThen` g)

Maybe

Recall andThenMaybe:

instance Monad_ Maybe where
 -- andThen :: Maybe a -> (a -> Maybe b) -> Maybe b
    andThen (Just a) f = f a
    andThen _        _ = Nothing

Lists

instance Monad_ [] where
 -- andThen :: [a] -> (a -> [b]) -> [b]
 -- andThen xs f = concatMap f xs
    andThen      = flip concatMap

Infix Operator

Another name for andThen is an operator pronounced "bind":

(>>=) :: Monad_ m => m a -> (a -> m b) -> m b
(>>=) = andThen

Additional Operators

(>>) :: Monad_ m => m a -> m b -> m b
ma >> mb = ma >>= \_ -> mb

(=<<) :: Monad_ m => (a -> m b) -> m a -> m b
(=<<) = flip (>>=)

(<=<) :: Monad_ m => (b -> m c) -> (a -> m b) -> a -> m c
f <=< g = \a -> g a >>= f

(>=>) :: Monad_ m => (a -> m b) -> (b -> m c) -> a -> m c
(>=>) = flip (<=<)

The first operator above doesn't actually require (>>=):

(*>) :: Applicative_ t => t a -> t b -> t b
ta *> tb = curry snd <$> ta <*> tb

(>>) :: Monad_ m => m a -> m b -> m b
(>>) = (*>)

Alternative Characterization

Notice that, in the version below, there is an additional member called join. Each of the two members can be derived in terms of the other; think about how to do so, and then check the default definitions in Monad_.hs.

class Applicative_ t => Monad_ (t :: * -> *) where
    andThen :: t a -> (a -> t b) -> t b
    join :: t (t a) -> t a

The characterization via join can be thought of as saying Monad_s are fancy types t such that values that are twice as fancy (t (t a)) are no better than just fancy (t a).

Errors

Recall sibling.

class Monad_ t => MonadPlus_ t where
    guardFalse :: t ()
    
    guard :: Bool -> t ()
    guard True  = pure ()
    guard False = guardFalse

The Maybe and list types have natural ways to encode errors:

instance MonadPlus_ Maybe where
 -- guardFalse :: Maybe ()
    guardFalse = Nothing

instance MonadPlus_ [] where
 -- guardFalse :: [()]
    guardFalse = []

From Monad_ to Monad

class Applicative m => Monad m where

 -- fmap  ::   (a -> b) -> m a -> m b    -- from Functor
 -- (<*>) :: f (a -> b) -> m a -> m b    -- from Applicative
 -- pure  :: m -> m a                    -- from Applicative

    (>>=) :: m a -> (a -> m b) -> m b    -- Monad_.andThen

    return :: m -> m a
    return = pure

The sequencing operation (>>=) is pronounced "bind". The alternative characterization, via join, is provided by the library function Control.Monad.join.

The return member is defined to be pure. This is a vestige of previous versions of Haskell. The Monad class had been defined long before Applicative was identified and defined (sometime around 2008). When Applicative was added, the Monad class was not changed to include Applicative as a superclass constraint, in order to avoid breaking changes.

Starting with version 7.10 in 2005, however, the superclass constraint was added, but return was kept around (with default implementation pure).

We'll talk about the differences between MonadPlus_ and MonadPlus later.

(Monad also includes a member called fail :: String -> m a that we will not talk about it. Just beware that you may see fail if looking at some legacy code. In a future version of Haskell, fail will be moved out of Monad into another class.)

Do-notation

Although the syntax looks imperative, do-notation is just syntactic sugar for a sequence of binds.

A do-block takes the form

do { doThing_0; ...; doThing_n; returnExp }

where returnExp :: M T (for some particular type M in the Monad class and for some type T), and where each doThing_i is of the form (the type M is the same as for returnExp):

doThing ::=
  | let p_i = e_i       if e_i :: T_i,   then p_i :: T_i
  | p_i <- e_i          if e_i :: M T_i, then p_i :: T_i
  | e_i                 if e_i :: M T_i

The do-block gets desugared as follows:

[[ let p = e, doThings ]]  ===  let p = e in [[ doThings ]]
[[    p <- e, doThings ]]  ===  e >>= (\p -> [[ doThings ]])
[[         e, doThings ]]  ===  e >> [[ doThings ]]
[[           returnExp ]]  ===  returnExp

Based on this translation, we can understand the required types for each kind of doThing; the actions are "stitched together" by nested calls to (>>=). The entire translated expression is assigned the type of returnExp :: M T.

For example:

greatgrandfather :: Person -> Maybe Person

greatgrandfather p = do     -- greatgrandfather p =
  fp   <- pure p            --   pure   p   >>= \fp ->
  ffp  <- father fp         --   father fp  >>= \ffp ->
  fffp <- father ffp        --   father ffp >>= \fffp ->
  pure fffp                 --   pure fffp

sibling :: Person -> Person -> Maybe ()

sibling x y = do            -- sibling x y =
  guard $ x /= y            --   (guard $ x /= y) >>
  fx <- father x            --   father x         >>= \fx ->
  fy <- father y            --   father y         >>= \fy ->
  guard $ fx == fy          --   guard $ fx == fy

Compare this to the desugaring of do-notation for I/O we saw earlier — IO is just one instance of Monad, and its (primitive) implementation happens to perform side effects.

List Comprehensions

Recall the translation of list comprehensions [ expression | things ] from before.

We can now understand list comprehensions as a variation of a do-block (for the [] instance of Monad and MonadPlus), where boolean filter predicates get translated to guards:

[[ let x = e, things ]]  ===  let x = e in [[ things ]]

[[    x <- e, things ]]  ===  e >>= (\x -> [[ things ]])
                         ===  flip concatMap e (\x -> [[ things ]])

[[         e, things ]]  ===  guard e >> [[ things ]]
                         ===  (if e == False then guardFalse else pure ())
                                >> [[ things ]]
                         ===  flip concatMap
                                (if e == False then guardFalse else pure ())
                                (\_ -> [[ things ]])
                         ===  flip concatMap
                                (if e == False then [] else [()])
                                (\_ -> [[ things ]])

[[                   ]]  ===  pure expression
                         ===  [expression]

For example, recall the smallPairs function from before, now defined with a do-block rather than a list comprehension:

smallPairs :: (Ord a, Num a) => [a] -> [a] -> [(a, a)]
smallPairs xs ys =
  do
    x <- xs
    y <- ys
    let sum = x + y
    guard $ sum <= 5
    pure (x, y)

Free Instances

If you know that you will make T a Monad, can implement the Monad instance first...

instance Monad T where
  return   = ...
  mx >>= f = ...

... and then define free Functor and Applicative instances with the following boilerplate definitions:

instance Functor T where
  fmap f x = pure f <*> x

instance Applicative T where
  pure  = return
  (<*>) = ap

Or, if you're feeling really cheeky:

instance Functor     T where {fmap f x = pure f <*> x}
instance Applicative T where {pure = return; (<*>) = ap}

Functor and Applicative are superclasses of Monad, but Haskell allows them to be defined "out of order" like this. Think about how to implement ap (and then look it up in the library implementation).

Thus, pure (a.k.a return) and (>>=) are essentially a "minimal complete definition" for the classes Functor, Applicative, and Monad, taken together.

Roadmap (Redux)

Here's a summary of the Functor, Applicative, and Monad classes:

class Functor m where
    fmap :: (a -> b) -> m a -> m b

class Functor m => Applicative m where
 -- fmap  ::   (a -> b) -> m a -> m b     -- from Functor
    (<$>) :: m (a -> b) -> m a -> m b

    pure :: a -> m a

class Applicative m => Monad m where
 -- fmap  ::   (a -> b)   -> m a -> m b   -- from Functor
 -- (<$>) :: m (a -> b)   -> m a -> m b   -- from Applicative
 -- (<<=) :: m (a -> m b) -> m a -> m b   -- flip (>>=)

    (>>=) :: m a -> m (a -> m b) -> m b

 -- pure   :: a -> m a                    -- from Applicative
    return :: a -> m a
    return =  pure

class Monad m => MonadPlus m where
    guard :: Bool -> m ()

Source Files

• Monad_.hs