Recently a blog post came out which I quite like, it describes how to use the concrete base transformers. It’s very thorough and gives a concrete example for using transformers. Although it looks quite low level and I think you’ll get more out of transformers by using full MTL.

That blogpost inspired me to write this, because I can’t find a succinct description on how to use MTL¹. I learned MTL by staring at reflex for days, if not weeks. Which is an uncomfortable learning process. To make MTL more accessible I’ll give a brief overview of this style³. I’ll write down how MTL works from the ground up, so people can read how to use it rather then struggling with code for days like I did.

If you like video presentations, I also presented how to use MTL in a video format.

The type variable m

We start by introducing m. Which could’ve been named monad or x, but the community settled on using m for type variables with the Monad constraint, so I will use this too. Normally we use type variable’s in concrete types, for example Maybe a or [a]. However, Instead of having our type variable inside a concrete type, we can also flip it around:

moreMonad :: Monad m => m Int
moreMonad = return 5

This compiles because the Monad constraint on m gives us the return function ². After you’re convinced this is a valid definition, let’s use it. What can we do with this moreMonad binding? Well, we can pattern match on it:

fiveTroughMaybe :: Int
fiveTroughMaybe = case moreMonad of
  Just x -> x
  Nothing -> 9

GHC will give moreMonad the type Maybe at this call site. GHC reasons backwards from the pattern match up to the case moreMonad of definition to figure out the type. In my head I describe this backwards reasoning process as: “pretending you have a Maybe which makes it becomes true”. So fiveTroughMayberesults in 5 because return is implemented as Just on the Maybe type’s Monad instance.

This is valid. You should convince yourself it’s valid. To convince yourself I’m not lying paste this code into GHCI before continuing, and gain some confidence, because yonder be dragons.

Continuing now with the same module we can also pattern match on Either:

fiveTroughEither :: Int
fiveTroughEither = case moreMonad of
  Right x -> x
  Left _y -> 9

Both fiveTroughMaybe and fiveTroughEither will result in 5. This is allowed in the same module because moreMonad will only get assigned the type at the call site. The compiler figures out the type of moreMonad by looking at usage per call site. This backwards ‘figuring out’ is normal for type variables.

(optional) mastery exercise

• Can we always pattern match on every possible monad type like we just did with Just or Either? Can we always get the value out without being in the same monad? The answer is in the footnote. ⁴

Transformers as constraints on m

With that brief introduction, we can start applying this idea to the ‘“A Brief Intro to Monad Transformers” blogpost‘ which inspired me to write this. In that blogpost, a newtype is constructed to hold the entire monad transformer stack like this:

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

I call this AppM a concrete type because there is only one way to pattern match on it. We’re not allowed to pretend it’s a Maybe for example. This definition is used in the assignIndexToVariables function:

assignIndexToVariables :: AST VariableName -> Variables -> AppM (AST Int)

Instead of using the concrete type AppM, we could use MTL type classes to describe what is needed. These type classes will become constraints on m, similarly to how Monad was a constraint on m in the introduction. Which means we want to have MonadError String as replacement for ExceptT String ⁵, and MonadState (M.Map VariableName Int) as replacement for State (M.Map VariableName Int). Doing this will change the type signature of assignIndexToVariables as follows:

assignIndexToVariables ::
               MonadError String m
            => MonadState (M.Map VariableName Int) m
            => AST VariableName
            -> Variables
            -> m (AST Int)

So what’s the difference? The type signature is more verbose, although we no longer need the newtype. In trade for this verbosity, we can use the monad stack in any order at the call site. Both invocations of running this code are now allowed:

main :: IO ()
main = do
 ...
 print $ flip evalState mempty $ runExceptT $
    assignIndexToVariables ast vars
 print $ runExcept $ flip evalStateT mempty $
    assignIndexToVariables ast vars

This wasn’t possible in the original code. We’ve told the compiler that the order of a monad stack doesn’t matter. Which makes sense because consider two monad stacks:

at :: Char -> ExceptT String (State (M.Map VariableName Int)) Int
bt :: Int -> StateT (M.Map VariableName Int) (Except String) String

These describe the same capabilities, however the compiler says a and b should not compose. It’s impossible to write:

ct :: Char -> _ String
ct = at >=> bt

We don’t know what goes at _ for ct because at and bt have concrete types. We can write this composition however if these signatures are defined in MTL style:

am :: MonadError String m
  => MonadState (M.Map VariableName Int) m
  => Char -> m Int
bm :: MonadState (M.Map VariableName Int) m
  => MonadError String m
  => Int -> m String

cm :: MonadState (M.Map VariableName Int) m
    => MonadError String m
    => Char -> m String
cm = am >=> bm

Because constraints don’t specify an order on transformers, the MTL style function definition can compose. ⁶

This section described the core idea of MTL. In the following sections we’re going to extend MTL using type error driven development. This all sound like madness if you don’t try it out with a compiler. And I feel understanding errors is a large part of understanding MTL. The type errors are difficult to decipher. I’ve made an reference project so the reader can verify the truth of my claims.

Even though you may doubt me dear reader, let’s go deeper into the abyss.

(optional) mastery exercises

• What does the function lift do? The answer is in the footnotes. ⁸
• Is the order of a transformer stack always irrelevant? The answer is in the footnotes. ⁷

• Say ct has this type signature:

  ct :: Char 
     -> ExceptT String (State (M.Map VariableName Int)) String
  

  Call at and then bt from within ct such that it composes like the fish operator >=> would with help of liftWith. For additional background see this blogpost. The answer can be found in the reference project under the binding answer.

Lose and tight constraints

Say we want to use moreMonad from the introduction in assignIndexToVariables. I call moreMonad a tightly constrained binding. It’s only allowed to use what Monad typeclass provides. assignIndexToVariables on the other hand is less tightly constrained, since it has Monad by implication, and also everything in MonadError and MonadState. So let’s use it:

assignIndexToVariables ::
    MonadError String m =>
    MonadState (M.Map VariableName Int) m =>
    AST VariableName -> Variables -> m (AST Int)
assignIndexToVariables _ _ = do
   _z <- moreMonad 
   ...

This would just work, because both MonadError and MonadState imply Monad in their definitions. In mtl style, the functions with tighter constraints can be used in more situations without any refactoring.

Now we’re going to do the complete opposite. The most lax constraint possible is MonadIO, which gives access to arbitrary IO trough the liftIO function. I’m not casting judgement, I just want to show what happens. So let’s add a MacGyver ¹⁰ logging function as follows:

macGyverLog :: MonadIO m => String -> m ()
macGyverLog msg = liftIO $ putStrLn msg

The code is perfect. Y’know, it misses some things you’d expect from your regular logging library such as code positions, time stamping, etc. But that’s why it’s called macGyverLog and not kitchenSinkLog. And if we did some introspection we may find our code tends to look a lot more like macGyverLog then kitchenSinkLog, so let’s throw it into production:

assignIndexToVariables ::
    MonadError String m =>
    MonadState (M.Map VariableName Int) m =>
    AST VariableName -> Variables -> m (AST Int)
assignIndexToVariables _ _ = do
   macGyverLog "Starting reading more monad"
   _z <- moreMonad 
   macGyverLog "End reading more monad"
   ...

This will cause the following type error:

src/Lib.hs:31:5: error:
    • Could not deduce (MonadIO m) arising from a use of ‘macGyverLog’
      from the context: (MonadError String m,
                         MonadState (M.Map VariableName Int) m)
        bound by the type signature for:
                   assignIndexToVariables :: forall (m :: * -> *).
                                             (MonadError String m,
                                              MonadState (M.Map VariableName Int) m) =>
                                             AST VariableName -> Variables -> m (AST Int)
        at src/Lib.hs:(26,1)-(29,46)
      Possible fix:
        add (MonadIO m) to the context of
          the type signature for:
            assignIndexToVariables :: forall (m :: * -> *).
                                      (MonadError String m,
                                       MonadState (M.Map VariableName Int) m) =>
                                      AST VariableName -> Variables -> m (AST Int)

The possible fix read in the type error is correct, but we have to know what a context is, and a type signature to decipher that error message¹¹. The compiler is saying in incomprohensible error speak that you need to add a constraint MonadIO m like so:

assignIndexToVariables ::
    MonadIO m =>
    MonadError String m =>
    MonadState (M.Map VariableName Int) m =>
    AST VariableName -> Variables -> m (AST Int)

Cryptic as it may be, the reason I’m writing about this isn’t that particular error message, it’s the next one:

src/Lib.hs:51:50: error:
    • No instance for (MonadIO Data.Functor.Identity.Identity)
        arising from a use of ‘assignIndexToVariables’
    • In the second argument of ‘($)’, namely
        ‘assignIndexToVariables ast vars’
      In the second argument of ‘($)’, namely
        ‘runExceptT $ assignIndexToVariables ast vars’
      In the second argument of ‘($)’, namely
        ‘flip evalState mempty
           $ runExceptT $ assignIndexToVariables ast vars’
   |
51 |     print $ flip evalState mempty $ runExceptT $ assignIndexToVariables ast vars
   |                                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Here you may start thinking, WTF. Rightfully so. The reason it starts talking about identity is because evalState runs in identity. Look at the haddocks for evalState, then click on State. The base monad is identity. How do we fix this? First we replace Identity with a gap by invoking evalStateT instead of evalState (note the T). This will result in the following beauty :

src/Lib.hs:51:5: error:
    • Ambiguous type variable ‘m0’ arising from a use of ‘print’
      prevents the constraint ‘(Show
                                  (m0 (Either String (AST Int))))’ from being solved.
      Probable fix: use a type annotation to specify what ‘m0’ should be.
      These potential instances exist:
        instance (Show a, Show b) => Show (Either a b)
          -- Defined in ‘Data.Either’
        instance (Show k, Show a) => Show (M.Map k a)
          -- Defined in ‘Data.Map.Internal’
        instance Show a => Show (AST a) -- Defined at src/Lib.hs:21:13
        ...plus 18 others
        ...plus 9 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In a stmt of a 'do' block:
        print
          $ flip evalStateT mempty
              $ runExceptT $ assignIndexToVariables ast vars
      In the expression:
        do print
             $ flip evalStateT mempty
                 $ runExceptT $ assignIndexToVariables ast vars
           print (eitherFive, maybeFive)
      In the expression:
        let
          vars = S.fromList [...]
          ast
            = Node (Leaf "a") (Node (Leaf "b") (Node (Leaf "a") (Leaf "c")))
        in
          do print
               $ flip evalStateT mempty
                   $ runExceptT $ assignIndexToVariables ast vars
             print (eitherFive, maybeFive)
   |
51 |     print $ flip evalStateT mempty $ runExceptT $ assignIndexToVariables ast vars
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

src/Lib.hs:51:18: error:
    • Ambiguous type variable ‘m0’ arising from a use of ‘evalStateT’
      prevents the constraint ‘(Monad m0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘m0’ should be.
      These potential instances exist:
        instance Monad (Either e) -- Defined in ‘Data.Either’
        instance Monad IO -- Defined in ‘GHC.Base’
        instance [safe] Monad m => Monad (ExceptT e m)
          -- Defined in ‘Control.Monad.Trans.Except’
        ...plus six others
        ...plus 16 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In the first argument of ‘flip’, namely ‘evalStateT’
      In the expression: flip evalStateT mempty
      In the second argument of ‘($)’, namely
        ‘flip evalStateT mempty
           $ runExceptT $ assignIndexToVariables ast vars’
   |
51 |     print $ flip evalStateT mempty $ runExceptT $ assignIndexToVariables ast vars
   |                  ^^^^^^^^^^

src/Lib.hs:51:51: error:
    • Ambiguous type variable ‘m0’ arising from a use of ‘assignIndexToVariables’
      prevents the constraint ‘(MonadIO m0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘m0’ should be.
      These potential instances exist:
        instance [safe] MonadIO IO -- Defined in ‘Control.Monad.IO.Class’
        instance [safe] MonadIO m => MonadIO (ExceptT e m)
          -- Defined in ‘Control.Monad.Trans.Except’
        instance [safe] MonadIO m => MonadIO (StateT s m)
          -- Defined in ‘Control.Monad.Trans.State.Lazy’
        ...plus 11 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In the second argument of ‘($)’, namely
        ‘assignIndexToVariables ast vars’
      In the second argument of ‘($)’, namely
        ‘runExceptT $ assignIndexToVariables ast vars’
      In the second argument of ‘($)’, namely
        ‘flip evalStateT mempty
           $ runExceptT $ assignIndexToVariables ast vars’
   |
51 |     print $ flip evalStateT mempty $ runExceptT $ assignIndexToVariables ast vars
   |                                                   ^^^^^^^^^^^^^^^^^^^

All these m0 occur because we introduced the gap, GHC has no idea what the base monad is at this point. Which is what we want. Let’s solve it all in one change:

    print =<< flip evalStateT mempty
        (runExceptT $ assignIndexToVariables ast vars)

Note that we replaced the application of $ to a bind =<<. The base monad is now IO instead of Identity, which solves everything. It’s solved because IO, surprise, surprise, has an instance of MonadIO! Who would’ve thought liftIO could be id. The readers’ keen eye spots a pattern: We merely select instances with types that have code attached to them. It’s code generation based on type selection.

Reinterpreting IO or the MTL style

In most situations MonadIO is fine. However it doesn’t allow us to reinterpret effects that are using IO. An example of reinterpretation is a test where you would want to measure how often the mcGyverLog function is being called. This section will show you how to do that.

First we start by MTL-izing our IO based code. How can we rewrite mcGyverLog so that it doesn’t use IO explicetly? The function that needs IO is putStrLn. It’s type signature is String -> IO (). We want that IO to be an m, so we introduce a new typeclass for our not invented here log:

class (Monad m) => NotInventedHereLog m where
    nihLog :: String -> m ()

We already know what implementation m has if it’s an IO instance:

instance NotInventedHereLog IO where
    nihLog :: String -> IO ()
    nihLog = putStrLn

To make our previous example work we need to replace MonadIO in our function definition with NotInventedHereLog. Because we renamed the macGyverLog function to nihLog, we need to replace those calls with nihLog as well:

assignIndexToVariables2 ::
  NotInventedHereLog m =>
  MonadError String m =>
  MonadState (M.Map VariableName Int) m =>
  AST VariableName -> Variables -> m (AST Int)
assignIndexToVariables2 ast variables = forM ast $ \var -> do
    nihLog "start more monad"
    _z <- moreMonad
    ...

Running this will give us the following type error:

src/Lib.hs:54:52: error:
    • No instance for (NotInventedHereLog
                         (StateT (M.Map VariableName Int) (ExceptT [Char] IO)))
        arising from a use of ‘assignIndexToVariables2’
    • In the second argument of ‘($)’, namely
        ‘assignIndexToVariables2 ast vars’
      In the first argument of ‘runExceptT’, namely
        ‘(flip evalStateT mempty $ assignIndexToVariables2 ast vars)’
      In the second argument of ‘(=<<)’, namely
        ‘runExceptT
           (flip evalStateT mempty $ assignIndexToVariables2 ast vars)’
   |
54 |     print =<< runExceptT (flip evalStateT mempty $ assignIndexToVariables2 ast vars)

This looks scary, maybe this is the one, the one type error I can’t solve? After all, I’ve been waiting for that one perfect type error for over four years now. But no, this is known as the $n^2$-instances problem¹², which sounds very impressive. However for now we completely ignore that problem by providing an instance which solves this type error:

instance (NotInventedHereLog m) => NotInventedHereLog (StateT s m) where
  nihLog = lift . nihLog

This code says: If you’re a StateT and your base monad already has a NotInventedHereLog constraint, you also have NotInvnetedHereLog instance with help of lift. By providing this instance we’re generating lift calls over StateT for all occurrences of niLog.

Moving on we get the same error for ExceptT:

src/Lib.hs:54:52: error:
    • No instance for (NotInventedHereLog (ExceptT [Char] IO))
        arising from a use of ‘assignIndexToVariables2’
    • In the second argument of ‘($)’, namely
        ‘assignIndexToVariables2 ast vars’
      In the first argument of ‘runExceptT’, namely
        ‘(flip evalStateT mempty $ assignIndexToVariables2 ast vars)’
      In the second argument of ‘(=<<)’, namely
        ‘runExceptT
           (flip evalStateT mempty $ assignIndexToVariables2 ast vars)’
   |
54 |     print =<< runExceptT (flip evalStateT mempty $ assignIndexToVariables2 ast vars)

We will keep getting these errors for every unique transformer we use because of the $n^2$-instances problem¹². This blogpost isn’t about solving the $n^2$ problem, so I will ignore it. The solution to the type error however is pretty much the same:

instance (NotInventedHereLog m) => NotInventedHereLog (ExceptT e m) where
  nihLog = lift . nihLog

The example code will compile with these two additional instances. However we still don’t know how to reinterpret this purely, and we have introduced code duplication. This duplication can be removed with the default mechanism described in Alexis King her blogpost.

For the pure interpretation we need to introduce a newtype, which is used to attach an instance for NotInventedHereLog. This type’s instance will collect the logged messages. Turns out that the WriterT monad transformer does exactly what we want. So the pure code will look like this:

newtype NihLogT m a = MkNihLogT {
        runNihLog :: WriterT [String] m a
    } deriving (Functor, Applicative, Monad, MonadTrans, MonadWriter [String])

instance Monad m => NotInventedHereLog (NihLogT m) where
  nihLog msg = tell [msg]

The instance simply tell‘s the message, which mappends it to the list. To run this code we use runNihLog:

    let pureCode :: (Either String (AST Int),  [String])
        pureCode = runWriter $ runNihLog $ runExceptT (flip evalStateT mempty $ assignIndexToVariables2 ast vars)
        (eitherAst, allLoggedMessages) = pureCode 
    print pureCode

Now allLoggedMessages will contain all messages emitted by nihLog. With this you can write property tests on assignIndexToVariables2. For example you could assert that an AST of size 20 should emit at least 40 log messages. Obviously this isn’t limited to tests or purity, you could also add a newtype that has a connection pool to send the messages to some database for example.

I’ll tap out here. This was supposed to be a short note on someone else’s blogpost, which spiraled into dumping all my knowledge here on MTL and extending it a bit as well. For example I didn’t even know about the defaults mechanism Alexis wrote about. I’ll tap out here, thanks for reading.

Let me know if you have any strong opinions on this style. Love it or hate it, I’d like to know! Or if you need any help using it. I’m interested in effect systems in general. Also let me know about your favorite effect system that I didn’t acknowledge.

Links

• Inspirational blogpost
• A functional example is available here
• A video presentation on the exact same topic.
• Full mtl style reinterpretation test example
• And a library for mocking around mtl style, also gives more background.
• If I didn’t manage to exhaust you, here is more background and alternatives.