A few friends have recently asked about literature introducing Monad
Transformers
. The best introduction I have found was in Haskell Programming From First Principles. If you don't have, or want to purchase, this book, then here is a brief explanation with examples.
Lets start with the problem they solve.
Functor
and Applicative
are both closed under composition. If we compose any two Functor
or Applicative
types then we get a Functor
or Applicative
.
We can do this composition with the Compose
newtype:
newtype Compose f g a = Compose (f (g a))
The composition is witnessed by the Functor
and Applicative
instances for Compose
:
instance (Functor f, Functor g) => Functor (Compose f g) where
fmap :: (a -> b) -> Compose f g a -> Compose f g b
fmap f (Compose x) = Compose (fmap (fmap f) x)
instance (Applicative f, Applicative g) => Applicative (Compose f g) where
pure :: a -> Compose f g a
pure a = Compose $ pure $ pure a
liftA2 :: (a -> b -> c) -> Compose f g a -> Compose f g b -> Compose f g c
Compose x) (Compose y) = Compose (liftA2 (liftA2 f) x y) liftA2 f (
Now we can compose Functors
together and get combined effects:
> xs = Compose [Just True, Just False, Nothing]
> :t xs
xs :: Compose [] Maybe Bool
> fmap not xs
Compose [Just False,Just True,Nothing]
> xs
Compose [Just True,Just False,Nothing]
> ys
Compose [Just False,Just True,Nothing]
> liftA2 (||) xs ys
Compose [Just True,Just True,Nothing,Just False,Just True,Nothing,Nothing,Nothing,Nothing]
We can do this with any two Functors
. That is Really Cool:tm:.
But What about Monad
? Can we write a Monad
instance for Compose
?
instance (Monad f, Monad g) => Monad (Compose f g) where
return :: a -> Compose f g a
return = pure
(>>=) :: Compose f g a -> (a -> Compose f g b) -> Compose f g b
Compose fga >>= f = _
What we are trying to do in this >>=
instance is combine these two functions:
Monad f => f a -> (a -> f b) -> f b
Monad g => g a -> (a -> g b) -> g b
Into this function:
Monad f, Monad g) => f (g a) -> (a -> f (g b)) -> f g b (
It turns out this is impossible. If we look at the combined join
type we can see the knot we have created:
join :: (Monad f, Monad g) => f (g (f (g a))) -> f (g a)
There simply is no way to implement this while keeping both Monads
polymorphic.
The fundamental problem with composing two polymorphic Monads
is the polymorphism. If we could make one of the Monads
concrete then we could define bind
and join
:
bind :: Monad f => f (Maybe a) -> (a -> f (Maybe b)) -> f (Maybe b)
=
bind ma f >>= \case
ma Nothing -> pure Nothing
Just a -> f a
join :: Monad f => f (Maybe (f (Maybe a))) -> f (Maybe a)
= ma >>= \case
join ma Nothing -> pure Nothing
Just ma' -> ma' >>= \case
Just a -> pure $ Just a
Nothing -> pure Nothing
This is Monad Transformers
in a nutshell!
As long as we know at least one of the Monads
at play then we have a pathway to compose them. We can create special Transformer versions of all our standard Monads
which will have a slot for a second polymorphic monad:
newtype IdentityT m a = IdentityT { runIdentityT :: m a }
newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }
newtype ExceptT e m a = ExceptT { runExceptT :: m (Either e a) }
newtype ListT m a = ListT { runListT :: m [a] }
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }
-- etc
An interesting side note is that you can recover all the standard Monad
variants by selecting Identity
for the m
parameter:
type Identity a = IdentityT Identity a
type Maybe a = MaybeT Identity a
type Either' e a = ExceptT e Identity a
type List a = ListT Identity a
type State s a = StateT s Identity a
-- etc
I'll show the instances for MaybeT
and the rest are left as an exercise for the reader:
instance Functor m => Functor (MaybeT m) where
fmap :: (a -> b) -> MaybeT m a -> MaybeT m b
fmap f (MaybeT ma) = MaybeT $ fmap (fmap f) ma
instance Applicative m => Applicative (MaybeT m) where
pure :: a -> MaybeT m a
pure a = MaybeT $ pure $ pure a
liftA2 :: (a -> b -> c) -> MaybeT m a -> MaybeT m b -> MaybeT m c
MaybeT ma) (MaybeT mb) = MaybeT $ liftA2 (liftA2 f) ma mb
liftA2 f (
instance Monad m => Monad (MaybeT m) where
return :: a -> MaybeT m a
return = pure
(>>=) :: MaybeT m a -> (a -> MaybeT m b) -> MaybeT m b
MaybeT ma >>= f =
MaybeT $ ma >>= \case
Nothing -> pure Nothing
Just a -> runMaybeT $ f a
With combined monadic effects we can do really nice sequencing and combination of effects. For example..
Imagine we wanted to traverse an AST and replace the values with indices referencing those values. Perhaps there is also the possiblity that there are invalid values in your AST and if found we want to fail the traversal. How might we write this code?
Our AST is just a binary tree and valid variables are given in a HashSet
:
data AST a = Leaf a | Node (AST a) (AST a)
deriving (Show, Functor, Foldable, Traversable)
type VariableName = String
type Variables = S.HashSet VariableName
While traversing the tree we will need to keep a map of Variables to Indices in state, generating new mappings as we encounter fresh variables. For this we can use the State
monad.
If we encounter an invalid variable then we need a way to exit early from the traversal and report an error message. We can do this with the Either
Monad or its transformer variant ExceptT
.
Our Transformer Stack will consist of ExceptT
and State
:
newtype AppM a = AppM { runAppM :: ExceptT String (State (M.Map VariableName Int)) a }
deriving newtype (Functor, Applicative, Monad, MonadError String, MonadState (M.Map VariableName Int))
Now our program becomes a simple traversal where we can perform both State
effects and Either
effects:
assignIndexToVariables :: AST VariableName -> Variables -> AppM (AST Int)
= forM ast $ \var -> do
assignIndexToVariables ast variables `S.member` variables) $
unless (var $ "Unknown Variable " <> var
throwError <- get
cache case M.lookup var cache of
Just index -> pure index
Nothing -> do
let index = M.size cache
$ M.insert var index cache
put pure index
main :: IO ()
=
main let vars = S.fromList ["a", "b", "c"]
= Node (Leaf "a") (Node (Leaf "b") (Node (Leaf "a") (Leaf "c")))
ast in print $ flip evalState mempty $ runExceptT $ runAppM $ assignIndexToVariables ast vars
> main
Right (Node (Leaf 0) (Node (Leaf 1) (Node (Leaf 0) (Leaf 2))))