``````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``````

``````(>>) :: 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

-- 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 `guard`s:

``````[[ 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.

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