Similarly to how Bryan O’Sullivan got side-tracked over five years ago, I recently found myself wishing a library existed to more easily deal with monad transformers.
There are quite a few libraries that try and provide more convenient ways of dealing with monad transformers (typically using those defined in transformers so as to avoid re-defining them all the time and to provide inter-compatibility): the old standard of mtl, the type-family variant found in monads-tf, the more ambitious layers package and Roman Cheplyaka’s monad-classes work.
However, I found that none of the libraries I could find really satisfied me. Even
monad-classes – that aim to simplify/remove the quadratic instance problem still require a “catch-all” default instance for all other monad transformers. Ideally for me, if I want to define a new transformer class, then I should only need to define instances for transformers that directly implement it’s functionality.
As such, I’m pleased to announce the first (alpha-level) release of my new library: monad-levels.
Why I wrote this library
Originally, all I wanted was to be able to lift operations in a base monad up through any transformers I might stack on top of it.
Except that I didn’t want to just lift up a single monad up through the stack: I wanted to be able to convert a function on my base monad up to whatever set of transformers I had stacked up on top of it. So I resigned myself to writing out instances for every existing transformer in the
As I started doing so though, I noticed a common pattern: for each method in the instance, I would be using a combination of the following operations (using
StateT as an example):
wrap: apply the monad transformer (e.g.
m (a,s) → StateT s m a)
unwrap: remove the monad transformer (e.g.
StateT s m a → m (a,s))
addInternal: adds the internal per-transformer specific state (e.g.
m a → m (a,s))
wrap is used everywhere,
unwrap is used when lowering existing monads down so that they can (eventually) be used in the base monad and
addInternal is used when lifting monadic values.
Thus, if I define this as a type class for monad transformers, then I could use the wonderful
DefaultSignatures extension to simplify defining all the instances, and what’s more such a class would be re-usable.
Generally, the definition of
addInternal require information from within the scope of the transformer (e.g. the
s parameter within
StateT); as such,
wrap ends up being a continuation function. I thus came up with the following class:
class (Monad m) => MonadLevel m where type LowerMonad m :: * -> * type InnerValue m a :: * -- A continuation-based approach for how to lift/lower a monadic value. wrap :: ( (m a -> LowerMonad m (InnerValue m a) -- unwrap -> (LowerMonad m a -> LowerMonad m (InnerValue m a)) -- addInternal -> LowerMonad m (InnerValue m a) ) -> m a
(Note that I’m not using
MonadTrans for this as I also wanted to be able to use this with newtype wrappers.)
So I define this class, use
DefaultSignatures and my instances – whilst still needing to be explicitly defined – become much simpler (and in many/most cases empty)!
Becoming more ambitious
Whilst I was looking to see if any existing libraries had something similar (
layers came the closest, but it uses multiple classes and requires being able to specify function inverses when using it), I came across Roman Cheplyaka’s blog post on how
monad-control uses closed type families to automatically recursively lift monads down to a monad that satisfies the required constraint. I became intrigued with this, and wondered if it would be possible to achieve this for any constraint (more specifically something of kind
(* → *) → Constraint) rather than using something that was almost identical for every possible monad transformer class.
So I wrote a prototype that made it seem as if this would indeed work (note that I used the term “lower” rather than “lift”, as I saw it as lowering operations on the overall monadic stack down to where the constraint would be satisfied):
data Nat = Zero | Suc Nat class SatisfyConstraint (n :: Nat) (m :: * -> *) (c :: (* -> *) -> Constraint) where _lower :: Proxy c -> Proxy n -> (forall m'. (c m') => m' a) -> m a instance (ConstraintSatisfied c m ~ True, c m) => SatisfyConstraint Zero m c where _lower _ _ m = m instance (MonadLevel m, SatisfyConstraint n (LowerMonad m) c) => SatisfyConstraint (Suc n) m c where _lower _ _ m = wrap (\ _unwrap addI -> addI (_lower (Proxy :: Proxy c) (Proxy :: Proxy n) m))
(This is a simplified snippet: for more information – including where the
ConstraintSatisfied definition comes from – see here.)
With this, you also get
liftBase for free! However, if all I wanted was a function just to lift a value in the base monad up the stack, then I could have used a much simpler definition. For this to actually be useful, I have to be able to write (semi-)arbitrary functions and lift/lower them as well.
I could just go back to my original plan and use
MonadLevel combined with
DefaultSignatures and not bother with this automatic lifting/lowering business… but I’ve already started, and in for a penny in for a pound. So full steam ahead!
It took a while to sort out it would work (dealing with
Reader was easy; having to extend how this worked for
Cont took quite a while and then even more for
monad-levels is now able to deal with arbitrary monadic functions.
Well… I say arbitrary…
To be able to deal with functions, you first need to use the provided sub-language to be able to specify the type of the function. For example, a basic function of type
m a → m a is specified as
Func MonadicValue (MkVarFnFrom MonadicValue)) (or more simply as just
MkVarFn MonadicValue, using the inbuilt simplification that most such functions will return a value of type
m a); something more complicated like
MkVarFn (Func (Func ValueOnly (MonadicOther b)) MonadicValue).
This language of lower-able functions is used to be able to know how to convert arguments and results up and down the monadic stack.
The end result
I’m finally releasing this library after being able to successfully replicate all the existing monad transformer classes in
mtl (with the exception of the deprecated
MonadError class). As an example, here is the equivalent to
import Control.Monad.Levels import Control.Monad.Levels.Constraints import Control.Monad.Trans.Cont (ContT (..)) import qualified Control.Monad.Trans.Cont as C import Control.Monad.Trans.List (ListT) -- | A simple class just to match up with the 'ContT' monad -- transformer. class (MonadLevel m) => IsCont m where -- Defined just to have it based upon the constraint _callCC :: CallCC m a b instance (MonadTower m) => IsCont (ContT r m) where _callCC = C.callCC instance ValidConstraint IsCont where type ConstraintSatisfied IsCont m = IsContT m type family IsContT m where IsContT (ContT r m) = True IsContT m = False -- | Represents monad stacks that can successfully pass 'callCC' down -- to a 'ContT' transformer. type HasCont m a b = SatisfyConstraintF IsCont m a (ContFn b) -- | This corresponds to @CallCC@ in @transformers@. type ContFn b = MkVarFn (Func (Func ValueOnly (MonadicOther b)) MonadicValue) -- This is defined solely as an extra check on 'ContFn' matching the -- type of 'C.callCC'. type CallCC m a b = VarFunction (ContFn b) m a -- Not using CallCC here to avoid having to export it. -- | @callCC@ (call-with-current-continuation) calls a function with -- the current continuation as its argument. callCC :: forall m a b. (HasCont m a b) => ((a -> m b) -> m a) -> m a callCC = lowerSat c vf m a _callCC where c :: Proxy IsCont c = Proxy vf :: Proxy (ContFn b) vf = Proxy m :: Proxy m m = Proxy a :: Proxy a a = Proxy -- By default, ListT doesn't allow arbitrary constraints through; -- with this definition it is now possible to use 'callCC' on @ListT (ContT r m) a@. instance (MonadTower m) => ConstraintPassThrough IsCont (ListT m) True
One thing that should be obvious is that the constraint is a tad more complicated than that required for
MonadCont. Specifically, it requires the
b parameters as well; this is because not all instances of
MonadLevel allow dealing with arbitrary other monadic values (that is, we’re dealing with
m a over all, but we also need to consider
m b in this case). In practice, however, the only existing monad transformer with this constraint is
ContT itself, and you can’t pass through a call to
callCC from one
ContT transformer to another (as there’s no way to distinguish between the two).
(Something that might not be obvious is that the interaction between
StateT – both lazy and strict – and how I’ve defined
callCC differs from how it’s defined in
mtl. Hence why I started this thread on Haskell Cafe.)
But, any monad transformer in the
transformers library that is an instance of
MonadCont also satisfies the requirements for the
HasCont constraint, and furthermore just by making it an instance of
MonadLevel any new transformer (including a newtype wrapper over a monadic stack) will also automatically satisfy the constraint!
There are two main sources of problems currently with
- Whilst the types line up and playing with the various classes in ghci seems to work, there is no comprehensive test-suite as yet to verify that it is indeed sound.
I have no idea how it compares speed- and memory-wise to
mtl; as it uses a lot of type families, explicit dictionary passing, etc. I expect it to be slower, but I haven’t compared it or investigated if there’s anywhere I can improve it.
I’m not sure of all the names (e.g.
MkVarFnFromfor dealing with variadic functions probably could be improved); not to mention that there’s probably also room for improvement in terms of what is exported (e.g. should the actual type classes for dealing with variadic arguments be fully exported in case people think of more possible argument types?).
It could also do with a lot more documentation.
These, however, are for the most part just a matter of time (though it might be that the performance one should actually belong to the next category).
Implications of approach/implementation
The biggest noticeable problem is one of discovery: if you look at
mtl, it’s obvious to tell when a transformer is an instance of a particular class; in contrast, with
monad-levels there’s no obvious way of looking at Haddock documentation to tell whether or not this is the case. The best you can do for a specific constraint
c and monad
m (without trying it in ghci) is that if it’s
MonadLevel_ definition has
AllowOtherValues m ~ True and
DefaultAllowConstraints m ~ True (both of which are the defaults) and the latter hasn’t been overriden with
instance ConstraintPassThrough c m ~ False then it is allowed. (Assuming that the constraint and its functions are sound, and something screwy hasn’t been done like having the monad actually being a loop.)
As part of this, this means things like type errors sometimes being difficult to resolve due to the large usage of associated types and constraint kinds. Furthermore, as you probably saw in the
HasCont definition shown above, you typically need to use
ScopedTypeVariables with proxies.
Go forth and use it!
Whilst it most definitely isn’t perfect, I think
monad-levels is now at a usable state. As such, I’d appreciate any attempts people make at using it and giving me any feedback you might have.
This is also the first time I’ve used git and Github for my own project. I missed the simplicity and discoverability of darcs, but magit for Emacs makes using it a bit easier, and in-place branches and re-basing turned out to be quite nice.