`Monad` hides the plumbing involved with sequencing a bunch of actions. But they don't support alternation between different types of actions.

## Motivating Example

Read three `Int`s from user and sum them.

First read one `Int`...

``````readInt0 :: IO (Maybe Int)
s <- getLine
if all isDigit s
then pure \$ Just (read s)
else pure Nothing``````

Or:

``````readInt :: IO (Maybe Int)
readInt = do {- IO -}
s <- getLine
pure \$ do {- Maybe -}
guard (all isDigit s)

Then run it three times:

``````addThree :: IO (Maybe Int)
case (mi, mj, mk) of
(Just i, Just j, Just k) -> pure \$ Just (i+j+k)
_                        -> pure Nothing``````

Could use a `do`-block for the final expression.

``````addThree :: IO (Maybe Int)
addThree = do {- IO -}
pure \$ do {- Maybe -}
i <- mi
j <- mj
k <- mk
pure \$ i + j + k``````

But this waits for all three lines before reporting error. Might rather fail as soon as one bad line is entered.

``````addThree :: IO (Maybe Int)
addThree = do {- IO -}
case mi of
Nothing -> pure Nothing
Just i  -> do {- IO -}
case mj of
Nothing -> pure Nothing
Just j -> do {- IO -}
case mk of
Nothing -> pure Nothing
Just k  -> pure \$ Just (i+j+k)``````

Okay, let's reduce the ugliness here. Define new, specialized versions of `bind` and `pure` to combine `Maybe` and `IO`, so that we can write:

``````addThree =
pureIOMaybe \$ i + j + k``````

So:

``````pureIOMaybe :: a -> IO (Maybe a)
pureIOMaybe a = pure \$ Just a

bindIOMaybe :: IO (Maybe a) -> (a -> IO (Maybe b)) -> IO (Maybe b)
action `bindIOMaybe` f = do
ma <- action
case ma of
Nothing -> pure Nothing
Just a  -> f a``````

These are "mashups" of `pure` and `(>>=)` from the `IO` and `Maybe` instances. In fact, these definitions work, not just for `IO`, but for any `Monad` type `m`:

``````pureMonadPlusMaybe :: Monad m => a -> m (Maybe a)
pureMonadPlusMaybe a = pure \$ Just a

bindMonadPlusMaybe :: Monad m => m (Maybe a) -> (a -> m (Maybe b)) -> m (Maybe b)
ma <- action
case ma of
Nothing -> pure Nothing
Just a  -> f a``````

Factoring this common plumbing makes definitions like `addThree` much better than before. Now let's plug this plumbing into the `Monad` interface, to benefit from library and syntactic conveniences provided to `Monad`.

As demonstrated by the motivating example, the pattern we want is to "alternate" between actions of two `Monad` types `m` and `m'`:

``````do
x1 <- e0  -- e0 :: m (m' a1)  ~= MPrimeT m a1
x2 <- e1  -- e1 :: m (m' a2)  ~= MPrimeT m a2
x3 <- e2  -- e2 :: m (m' a3)  ~= MPrimeT m a3
...
en        -- en :: m (m' an)  ~= MPrimeT m an``````

For each such `m'`, we will define a combination of `m` and `m'` — called `MPrimeT m` — that forms a `Monad`.

Convention: The monad transformer `FooT` creates a new monad from an existing `Monad` type `m` (the "underlying" or "inner monad") by adding the functionality of `Foo` (the "base monad") to `m`.

The libraries

``````import Control.Monad.Trans.Maybe

define the following:

``````newtype MaybeT m a    = MaybeT  { runMaybeT  :: m (Maybe a)   }
newtype ListT m a     = ListT   { runListT   :: m [a]         }
newtype StateT s m a  = StateT  { runStateT  :: s -> m (a, s) }
newtype WriterT w m a = WriterT { runWriterT :: m (a, w)      }``````

Each `FooT`, partially applied to all but its last arguments, is a `Monad` (when the underlying type `m` is).

## MaybeT

Let's work through `MaybeT`, which is the combination we need for our example:

``newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }``

We'll implement `Monad` first and take the free instances of `Functor` and `Applicative`:

``````instance Monad m => Monad (MaybeT m) where
-- return :: a -> MaybeT m a
return = MaybeT . return . Just

-- (>>=) :: MaybeT m a -> (a -> MaybeT m b) -> MaybeT m b
MaybeT mma >>= f = MaybeT \$ do
ma <- mma
case ma of
Nothing -> return Nothing
Just a  -> runMaybeT \$ f a

instance Monad m => Functor (MaybeT m) where {fmap f x = pure f <*> x}
instance Monad m => Applicative (MaybeT m) where {pure = return; (<*>) = ap}``````

The implementations of `return` and `(>>=)` are just like `pureMonadPlusMaybe` and `bindMonadPlusMaybe` implementations, but with `MaybeT` wrappers and `runMaybeT` unwrappers sprinkled in.

### Example

Let's try to re-implement `readInt` and `addThree` to be `MaybeT IO Int` actions rather than "raw" `IO (Maybe Int)` actions.

We'll need to "lift" `m` actions to `MaybeT m` actions:

``````liftMaybeT :: Monad m => m a -> MaybeT m a
liftMaybeT ma = MaybeT (fmap Just ma)``````

And we'll define a version of `guard` for `MaybeT m`:

``````guardMaybeT :: Monad m => Bool -> MaybeT m ()
guardMaybeT True  = MaybeT \$ pure \$ Just ()
guardMaybeT False = MaybeT \$ pure Nothing``````

Now we can define the following (notice the difference compared to the nested `do` blocks in the final version of `readInt`; now there is just one, with the "stacking" taking place inside)...

``````maybeReadInt :: MaybeT IO Int
maybeReadInt = do {- MaybeT IO -}
s <- liftMaybeT getLine
guardMaybeT \$ all isDigit s

... and run it thrice:

``````maybeAddThree :: MaybeT IO Int
maybeAddThree = do {- MaybeT IO -}
pure \$ i+j+k

This is like the final version of `addThree`, achieved via the `MaybeT` plumbing — which allows `Maybe` to be composed with any `Monad`, not just `IO`.

There are two minor improvements to make, which will clean up `maybeReadInt` a bit more.

First, `liftMaybeT` is specific to the `MaybeT` transformer. But, as we will see, we will want to lift functions to different transformers. Type class to describe a bunch of monad transformers:

``````class MonadTrans t where
lift :: Monad m => m a -> t m a

-- lift :: Monad m => m a -> MaybeT m a
-- lift = liftMaybeT
-- lift ma = MaybeT (fmap Just ma)
lift = MaybeT . fmap Just``````

This will be just as easy for all other monad transformers.

### Alternative

Second, let's make `MaybeT m` an `Alternative`, so that we can simply use `guard` rather than `guardMaybeT`.

``````instance (Monad m, Alternative m) => Alternative (MaybeT m) where
-- empty :: MaybeT m a
empty = MaybeT empty

-- (<|>) :: MaybeT m a -> MaybeT m a -> MaybeT m a
MaybeT mma <|> MaybeT mmb = MaybeT \$ mma <|> mmb``````

(Note: This instance is defined with different class constraints in the library.)

Now our final version of `maybeReadInt`:

``````maybeReadInt :: MaybeT IO Int