Monads

Notice that in addition to the andThen member we motivated earlier, there is another member called join. Each of these 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).

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

  1. left id: pure a ``andThen`` f === f a
  2. right id: ma ``andThen`` pure === ma
  3. assoc: (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

Additional Operations

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

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

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

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

The first operator above doesn't actually require andThen:

(*>) :: Applicative_ t => t a -> t b -> t b
ta *> tb = curry snd `Functor_.map` ta `Applicative_.apply` tb

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

Errors

class Monad_ t => MonadPlus_ t where
    guardFalse :: t ()

    guard :: Bool -> t ()
    guard True  = lift ()
    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 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.

Do-notation

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

do { doThing_0; ...; doThing_n; lastExp }

gets desugared as follows:

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

Based on this translation, we can understand the required types for each kind of doThing. Below, M is some particular type in the Monad class. The entire translate expression evaluates to (and is assigned the type of) lastExp :: M T for some T.

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

Compare this to the desugaring we saw when talking about I/O --- IO is just one instance of Monad (and its implementation happens to perform side effects).

For example:

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

List Comprehensions

Remember the translation of list comprehensions [ expression | things ] from before. We can now understand list comprehensions as a variation of a do-block (for the list 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
    return (x, y)

Free Instances

If you know that you will make T a Monad, implement it 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

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).

Essentially, the "minimal complete definition" for the classes Functor, Applicative, and Monad, together, is pure (a.k.a return) and (>>=).

Source Files

results matching ""

    No results matching ""