Reducing the pain of transformer stacks with duplicated effects.

The mtl provides a nice way to write monadic actions which take advantage of a particular kind of effect (say, statefulness or exception handling) without being forced to say exactly which monad is providing that effect. However, if a transformer stack includes two transformers that provide the given effect, mtl does not provide a clean way to disambiguate which one is wanted; the topmost one is always chosen.

This package provides tools for disambiguating without being forced to choose a particular transformer stack. It provides a separate stack for each kind of effect; you may then disambiguate by depth within each stack. For example, in a stack with two StateT transformers, one can write

foo :: MonadStateDepth 0 m a => m a
foo = depthState @0 get

for access to the topmost state effects, or

bar :: MonadStateDepth 1 m a => m a
bar = depthState @1 get

for access to the state from underneath the topmost StateT, no matter how deep in the stack the two StateTs are.

See the readme for more detailed motivation, usage examples, and documentation.

Table of Contents

• Table of Contents
• Why?
• Naming conventions
• How do I...
  • ...use the library to write monadic actions?
  • ...use a new transformer with existing kinds of effects?
  • ...create an effect stack for a new kind of effect?
• Why not...
  • ...type-based resolution?
  • ...type-level tags?

Why?

The transformers package gives us a nice library for building up monad transformer stacks that combine just the right mix of effects for a given application. For example, in a compiler, we might want to combine IO effects for reading and writing files, a scoping environment effect, the ability to report warnings and errors, state for generating fresh variable names or tracking type unification information, and so on. We might cook up a quite complicated stack like

type Compiler = ReaderT ScopingInformation
              ( StateT UnificationState
              ( ExceptT TypeError
              ( WriterT [Warning]
              ( StateT FreshNameGenerator
              ( IO
              )))))

to capture all of these effects in one monad.

With just the tools provided by the transformers package, though, this type can be somewhat frustrating to use. Getting access to the WriterT [Warning] part of the stack, for example, involves lifting the write effect through three layers of the stack using something like:

warn :: Warning -> Compiler ()
warn w = lift (lift (lift (tell [w])))

Besides being tedious, this also calcifies the monad stack; if later we discover we got the stack in the wrong order, or decide we need to add another effect, we would need to revisit all the places where we did such lifting and reconsider exactly how many occurrences of lift there should be.

The mtl package addresses this problem by adding one typeclass for each kind of effect. (Transformers which don't provide that effect pass it through.) This gives us two benefits:

1. We can write type signatures that constrict us to using fewer effects than our top-level application monad actually provides, and get the compiler to check that we have really used only those effects. These actions can still be used in the richer top-level application monad.
2. The need for explicitly lifting is drastically reduced, with the typeclass resolution mechanism inferring the correct number of lifts for us.

For example, using that library, we might write

warn :: MonadWriter [Warning] m => m ()
warn w = tell [w]

which now continues to work even if we change the monad stack later, provided we retain the property of having just one WriterT in the stack. The three uses of lift are inferred, and will be adjusted up or down as needed as the top-level application monad changes.

However, if one wishes to have two or more copies of a single kind of effect, there is no convenient, generic way to choose anything other than the one that appears topmost in the stack. With our Compiler monad above, for example, we might write

unify :: MonadState UnificationState m => Type -> Type -> m ()
unify t1 t2 = get >>= \us -> ...

to get access to the unification state. But if we want to access the FreshNameGenerator, we are back to writing fragile lift-based code:

freshName :: Compiler Name
freshName = lift (lift (lift (lift (modify (...)))))

We can, with some effort and perhaps a confusing type signature, retain some of the benefits of indicating in the type exactly which effects are used by mixing mtl-style actions with transformers-style lifting, though I dare say this style is as yet not very popular:

freshName :: (MonadTrans t1, MonadTrans t2, MonadState FreshNameGenerator m) => t1 (t2 m) Name
freshName = lift (lift (modify (...)))

The fragility of lift remains, though.

The effect-stack package addresses this problem, providing a way to choose lower layers of the monad stack generically and without explicitly writing the correct number of lifts. It introduces a separate stack for each kind of effect, and provides an operation for popping one layer of a given effect's stack. For example, we can still write

unify :: MonadState UnificationState m => Type -> Type -> m ()

for actions that access the topmost state, but with this library we can also write

freshName :: (StateStack m, MonadState FreshNameGenerator (PopState m)) => m Name

to access the state from underneath the outermost StateT, no matter how deep it is. We can implement this type using liftState; for example:

freshName = liftState (modify (...))

The typeclass resolution mechanism will turn liftState into the correct number of lifts to get from one StateT to the next.

Our Compiler monad has only two kinds of state, but one could imagine needing a third. Writing down the type for accessing the third type shows that using the primitive StateStack and PopState operations quickly becomes tedious with deep stacks:

thirdStateGet :: (StateStack m, StateStack (PopState m), MonadState X (PopState (PopState m))) => m X
thirdStateGet = liftState (liftState get)

Consequently, the library also provides some type families and operations that ease this iteration. Using them, we can also write thirdStateGet this way:

thirdStateGet :: MonadStateDepth 2 m X => m X
thirdStateGet = depthState @2 get

Of course, and unfortunately, inferred types will still use the fully-expanded form, but at least the human-written types can be a bit prettier.

Naming conventions

There is one module per kind of effect, named Control.Monad.Stack.<Effect>. Generally, if there is a class for the effect, we drop the initial Monad from the class name and use that as the name of the effect (e.g. MonadState → State). Otherwise we use the final part of the module name from transformers as the effect name (e.g. Control.Monad.Trans.Accum → Accum). Each module exports the following things:

• A typeclass for popping one layer of that kind of effect off the stack at a time. This should generally be viewed as a low-level tool, but it may also be independently useful.
  • The class is named <Effect>Stack.
  • There is an associated type family Pop<Effect>; it takes a monad, and removes enough transformers to drop the outermost transformer of the current kind of effect. For example, PopState Compiler would throw away the outermost ReaderT and StateT, leaving a new stack that began at the ExceptT.
  • There is a method lift<Effect>; it applies lift the appropriate number of times to take an action one layer down in the effect stack and lift it to the full monad.
• A type alias <Effect>Depth. It takes a type-level number and a monad, and calls Pop<Effect> the given number of times on the monad. This should probably also be considered a low-level tool.
• A type alias <Effect>Constraints. It takes a type-level number and a monad, and produces a constraint saying that you are permitted to call Pop<Effect> and lift<Effect> the given number of times with the monad. For transformers with no associated class, this will likely be the most commonly-used type-level export.
• A function depth<Effect>. It takes a type-level number and a monadic action, and calls lift<Effect> the given number of times on the action. This will most likely be the most commonly-used computation-level export.

For effects that are associated with a class, the module will also export:

• A type alias Monad<Effect>Depth. It takes a type-level number and a monad as its first two arguments. For classes which have other parameters than the monad, those parameters follow in the same order that the Monad<Effect> class demands them. (But note that the monad always comes before the other arguments, unlike in mtl!) It produces a constraint saying that you can call Pop<Effect> and lift<Effect> the given number of times with the monad, and that if you call Pop<Effect> the given number of times then the result is an instance of Monad<Effect> <args>. This will likely be the most commonly-used type-level export when it is available.

How do I...

...use the library to write monadic actions?

Generally, you will mix mtl-style classes for identifying what effect you want and effect-stack-style classes for identifying which layer of your transformer should provide that effect. In what follows, we will recap the Compiler example from the "Why?" section, including a complete, compilable file demonstrating simple usage of effect-stack. First some imports, data declarations, and other standard-ish nonsense:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeApplications #-}

-- base
import System.Exit

-- mtl
import Control.Monad.Reader
import Control.Monad.State
import Control.Monad.Writer
import Control.Monad.Except

-- effect-stack
import Control.Monad.Stack.State
import Control.Monad.Stack.Error

type Compiler = ReaderT ScopingInformation
              ( StateT UnificationState
              ( ExceptT TypeError
              ( WriterT [Warning]
              ( StateT FreshNameGenerator
              ( IO
              )))))

type Name = String
type ScopingInformation = [Name]
type UnificationState = ()
type Type = ()
type TypeError = (Type, Type)
type Warning = String
type FreshNameGenerator = Int

runCompiler :: Compiler a -> IO a
runCompiler act = do
	(res, warnings) <- evalStateT (runWriterT (runExceptT (evalStateT (runReaderT act []) ()))) 0
	traverse putStrLn warnings
	case res of
		Left err -> die (show err)
		Right a -> pure a

Now for some actual good stuff. We can still use mtl-style polymorphism freely when there is no ambiguity about which part of the stack should provide a particular effect. For example, Compiler has only one WriterT, so there's no problem knowing which tell to use:

warn :: MonadWriter [Warning] m => Warning -> m ()
warn w = tell [w]

Similarly, if we want to use the top-level state, we can still use mtl if we want:

unify :: ( MonadState UnificationState m
         , MonadError TypeError m
         ) => Type -> Type -> m ()
unify t1 t2 = do
	us <- get
	if t1 == t2
	then put ()
	else throwError (t1, t2)

Alternately, we can write the same type signature using effect-stack types explicitly saying that we want these effects to be provided by the top-most transformer that can provide them:

unify' :: ( MonadStateDepth 0 m UnificationState
          , MonadErrorDepth 0 m TypeError
          ) => Type -> Type -> m ()
unify' t1 t2 = do
	us <- get
	if t1 == t2
	then put ()
	else throwError (t1, t2)

Each kind of effect's stack is 0-indexed, so the outermost layer is layer 0. If we want to access effects not provided by the top-most transformer, then we must use effect-stack types (like MonadStateDepth) and methods (like depthState).

freshName :: MonadStateDepth 1 m FreshNameGenerator => m Name
freshName = depthState @1 $ do
	modify (1+)
	gets show

We can also mix and match, both at the type level (using mtl, base, and effect-stack classes), and within do blocks at the computation level (using mtl-style transformer polymorphic methods, base-style polymorphic lifting methods, and effect-stack-style polymorphic lifting methods).

debug :: ( MonadStateDepth 1 m FreshNameGenerator
         , MonadReader ScopingInformation m
         , MonadIO m
         ) => m ()
debug = do
	n <- depthState @1 get
	env <- ask
	liftIO (print (n, env))

Here's a main that exists just to show that all the pieces can now be specialized to the Compiler type as we wanted:

main :: IO ()
main = runCompiler $ do
	unify () ()
	warn "PHP is still more popular than Haskell."
	v <- freshName
	local (v:) $ do
		unify' () ()
		debug

Running it exits successfully after printing

(1,["1"])
PHP is still more popular than Haskell.

...use a new transformer with existing kinds of effects?

You can write new instances for the existing effect stack classes for your transformer. You must first decide whether the transformer you are writing an instance for provides the effect the class provides a stack for or not. For example, for the StateStack class, does your transformer provide access to some kind of stateful effect?

If it does, write an instance in which the Pop<Effect> family immediately returns the monad being transformed, and lift<Effect> is just lift. For example, because the AccumT family of transformers provides the Accumulation effect, the library provides this instance:

instance (Monad m, Monoid w) => AccumStack (AccumT w m) where
	type PopAccum (AccumT w m) = m
	liftAccum = lift

The (Monad m, Monoid w) constraints are needed to satisfy the Monad superclass of AccumStack; all the <Effect>Stack classes have this superclass for user convenience.

If your transformer does not provide the effect, you should write an instance that passes everything down one layer: Pop<Effect> should recurse on the transformed monad, and lift<Effect> should be lift . lift<Effect>. For example, since MaybeT does not provide Accumulation effects, the library provides this instance:

instance AccumStack m => AccumStack (MaybeT m) where
	type PopAccum (MaybeT m) = PopAccum m
	liftAccum = lift . liftAccum

...create an effect stack for a new kind of effect?

You will want to create a new class for the effect that provides the low-level tools for popping one layer of the stack at a time at the type level and lifting one layer at a time at the computation level. Once you have done that, there are some tools in Control.Monad.Stack.Internal that will be helpful for creating the high-level interface that accepts type-level numbers and iterates the low-level operations.

The classes are all quite similar to each other; you should be able to follow the exact same pattern for each new effect. The class itself should look like this:

class Monad m => <Effect>Stack m where
	type Pop<Effect> m :: * -> *
	lift<Effect> :: Pop<Effect> m a -> m a

At this point you will need to choose a type-level token that can uniquely identify this kind of effect. The type families that need this token as an argument are poly-kinded and will accept a token of any kind here. For most of the effects in this library, the token was chosen to be one of the transformers that is typically used to provide the effect. You may also simply invent a new type without exporting it if you are paranoid about collisions. Once you have chosen a token, make a mapping from the token to the family created above:

type instance Pop <Token> m = Pop<Effect> m

This token may now be passed to IteratePop, StackConstraints, and depth to provide the high-level interface:

type <Effect>Depth n m = IteratePop n <Token> m
type <Effect>Constraints n m = (KnownNat n, StackConstraints n <Token> <Effect>Stack m)

depth<Effect> :: forall n m a. <Effect>Constraints n m a => <Effect>Depth n m a -> m a
depth<Effect> = depth @n @<Token> @<Effect>Stack lift<Effect>

If there is a class associated with the effect, you may also want to offer a suitably stackified version of that class:

type Monad<Effect>Depth n m <args> =
	( <Effect>Constraints n m
	, Monad<Effect> <args> (<Effect>Depth n m)
	)

You will probably also want to write a bunch of instances for existing transformers. See the section "How do I...", subsection "...use a new transformer with existing kinds of effects?" for more information on doing this.

Why not...

...type-based resolution?

One alternate method of selecting which of many copies of an effect to use from a stack would be to look at the type being used for that effect. For example, continuing the Compiler example form the "Why?" section, one might imagine that one could write a class which used type inference to decide whether the current stateful actions were mucking about with FreshNameGenerators or UnificationStates, and use that information to decide whether to lift once or four times.

This approach has two main drawbacks:

1. It turns out that type inference fails to differentiate between the two situations surprisingly often. This puts an unusually high type-annotation burden on users. (Indeed, this is the standard justification for the functional dependency included in all mtl typeclasses.)
2. It still leaves you open to the problem of mixing effects which just happen, by coincidence, to need access to the same type in the effect. For example, suppose your compiler is tracking how many tab characters it has seen so that it can issue an appropriate warning. Even so, some local module might want to slap a transformer on top to add an effect for tracking the arity of the function currently being compiled. These both happen to be Ints, and so once again we have a disambiguation problem.

...type-level tags?

One could imagine adding a tag to each transformer, and using the tags to differentiate which effect is wanted. For example, with suitably modified transformers, one might write:

data Tag = Unification | Fresh | Other
type Compiler = ReaderT Other ScopingInformation
              ( StateT Unification UnificationState
              ( ExceptT Other TypeError
              ( WriterT Other [Warning]
              ( StateT Fresh FreshNameGenerator
              ( IO
              )))))

Then, instead of using type-level numbers to indicate the depth in a stack, one would use the tag to indicate which part of the stack was meant; so one might imagine writing something like:

unify :: MonadState Unification UnificationState m => Type -> Type -> m ()
unify t1 t2 = get @Unification >>= \us -> ...

freshName :: MonadState Fresh FreshNameGenerator m => m Name
freshName = modify @Fresh (...)

Convenient shorthands could be provided by the appropriate libraries for selecting, say, the () tag by default when the stack of interest was unambiguous about which layer should provide a given effect.

Unlike choosing by effect or choosing by effect+type, one need not worry about collisions with tags; modules which want to transform an existing monad could ensure they use fresh tags by just making a new data kind.

This approach has a lot going for it, and I'd love to see a competing library attempt this. The main drawback is that it is all-or-nothing, in that the existing transformers transformers do not have these tags. By contrast, effect-stack interoperates smoothly with existing transformers stacks. This means that

1. Existing projects can adopt this library without a big migration.
2. New projects can use just transformers+mtl, which are syntactically and conceptually very light, right up to the moment that they need something more complicated.