Monadic yak shaving

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 layers and 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.

We already have MonadIO; I just need to generalise it to work on any monad, right?

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 transformers library.

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

In particular, 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 unwrap and 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!

Variadic lowering

It took a while to sort out it would work (dealing with State and Reader was easy; having to extend how this worked for Cont took quite a while and then even more for Writer) but 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 CallCC becomes 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 MonadCont:

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 a and 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!

Drawbacks

There are two main sources of problems currently with monad-levels.

Alpha-state

• 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. MkVarFn and MkVarFnFrom for 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.)

Something that might also be a problem for some is the complexity: lots of language extensions are used, not to mention using a lot of things like Proxy and explicit dictionary passing.

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.