Maybe Monad Transformer...

We have spent several weeks studying how the Monad interface hides the plumbing involved with sequencing a bunch of actions for many different types. However, we have not yet tried “stacking” different types of actions. To demonstrate, we will consider a simple programming task: (maybe) reading three integers from standard input and summing them. After working through this example, maybe monad transformers… will not seem so scary.

Motivating Example

Read three Ints from user and sum them.

First read one Int…

readInt0 :: IO (Maybe Int)
readInt0 = do
  s <- getLine
  if s /= "" && all isDigit s then
    pure $ pure $ read s
  else
    pure Nothing

Or:

readInt :: IO (Maybe Int)
readInt = do {- IO -}
  s <- getLine
  pure $ do {- Maybe -}
    guard $ s /= "" && all isDigit s
    pure $ read s

Then run it three times:

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

Could use a do-block for the final expression.

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

But this always reads three lines, rather than failing as soon as one bad line is entered.

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

Okay, let’s reduce the ugliness here. Define new versions of bind and pure for the combination of IO and Maybe, so that we can write:

addThree =
  readInt `bindIOMaybe` \i ->
  readInt `bindIOMaybe` \j ->
  readInt `bindIOMaybe` \k ->
    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)
action `bindMonadPlusMaybe` f = do
  ma <- action
  case ma of
    Nothing -> pure Nothing
    Just a  -> f a

Exercise: Recall the characterization of monads via join. Implement:

joinMonadPlusMaybe :: Monad m => m (Maybe (m (Maybe a))) -> m (Maybe a)

Now let’s plug this plumbing into the Monad interface, to benefit from library and syntactic conveniences provided to Monad.

Monad Transformers

The pattern we want is to “stack” 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 by adding the functionality of MPrime to m.

The Monad Transformer Library (MTL)

import Control.Monad.Trans.Maybe
import Control.Monad.Trans.State
import Control.Monad.Trans.Reader
import Control.Monad.Trans.Writer

defines the following:

newtype MaybeT m a    = MaybeT  { runMaybeT  :: m (Maybe a)   }
newtype StateT s m a  = StateT  { runStateT  :: s -> m (a, s) }
newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a      }
newtype WriterT w m a = WriterT { runWriterT :: m (a, w)      }

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, but with MaybeT and runMaybeT sprinkled in.

Note: A minor ramification of taking the free instance of Functor here is the Monad m constraint, rather than just Functor m as strictly necessary.

Example

Let’s 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 $ s /= "" && all isDigit s
  pure $ read s

… and run it thrice:

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

> runMaybeT maybeReadInt
> runMaybeT maybeAddThree

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.

MonadTrans

First, liftMaybeT is specific to the MaybeT transformer. But, as we will see, we will want to lift functions to different transformers. The following describes a bunch of monad transformers:

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

instance MonadTrans MaybeT where
    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.

Pop Quiz: What kind of types does MonadTrans classify?

Alternative

Second, let’s make MaybeT m an Alternative, which will unlock guard (rather than guardMaybeT).

instance Monad m => Alternative (MaybeT m) where
  empty :: MaybeT m a
  empty = MaybeT $ pure Nothing

  (<|>) :: MaybeT m a -> MaybeT m a -> MaybeT m a
  mma <|> mmb = MaybeT $ do
    ma <- runMaybeT mma
    case ma of
      Just a  -> pure $ Just a
      Nothing -> runMaybeT mmb

Note: Here’s an “overeager” variation of the above:

  mma <|> mmb = MaybeT $ do
    ma <- runMaybeT mma
    mb <- runMaybeT mmb
    pure $ ma <|> mb

And here’s a more elegant variation (courtesy Stuart Kurtz):

  MaybeT mma <|> MaybeT mmb =
    MaybeT $ (<|>) <$> mma <*> mmb

Denouement

Now our final version of maybeReadInt:

maybeReadInt :: MaybeT IO Int
maybeReadInt = do
  s <- lift getLine
  guard $ s /= "" && all isDigit s
  pure $ read s

Source Files

MaybeT.hs

Misc

Using TypeOperators, enabled by default in GHC2021, allows writing infix binary type applications. For example:

maybeReadInt  :: IO `MaybeT` Int       -- MaybeT IO Int
maybeAddThree :: IO `MaybeT` Int       -- MaybeT IO Int