Wednesday, September 19, 2012

The MonadTrans class is missing a method

My work on pipes-2.4 leads me to the inescapable conclusion that the MonadTrans class is incomplete. In an ideal world, this is what it should actually look like:
{-# LANGUAGE Rank2Types #-}

class MonadTrans t where
    lift  :: (Monad m, Monad (t m)) => m a -> t m a
    embed :: (Monad m, Monad (t m), Monad (t n))
          => (forall a .   m a -> t n a)
          -> (forall b . t m b -> t n b)
          -- This last forall is optional

 :: (Monad f, Monad g, Monad (t g), Monad (t h),
     MonadTrans t)
 => (forall a . f a -> t g a)
 -> (forall b . g b -> t h b)
 -> (forall c . f c -> t h c) -- This last forall is optional
(f >|> g) x = embed g (f x)

squash :: (Monad (t (t m)), Monad (t m), MonadTrans t)
       => t (t m) a -> t m a
squash = embed id

 :: (Monad m, Monad n, Monad (t m), Monad (t n), MonadTrans t)
 => (forall a . m a -> n a) -> t m b -> t n b
mapT morph = embed (lift . morph)
I can justify this additional method just by changing the names around and using a type operator:
{-# LANGUAGE Rank2Types, TypeOperators #-}

type a :~> b = forall r . a r -> b r

class MonadM m where
    returnM :: (Monad a, Monad (m a))
            =>  a :~> m a
    bindM   :: (Monad a, Monad (m a), Monad (m b))
            => (a :~> m b) -> (m a :~> m b)

(>|>) :: (Monad a, Monad b, Monad (m b), Monad (m c),
          MonadTrans m)
      => (a :~> m b) -> (b :~> m c) -> (a :~> m c)
(f >|> g) x = bindM g (f x)

joinM :: (Monad (m (m a)), Monad (m a), MonadTrans m)
       => m (m a) :~> m a
joinM = bindM id

 :: (Monad a, Monad b, Monad (m a), Monad (m b), MonadTrans m)
 => (a :~> b) -> (m a :~> m b)
fmapM f = bindM (returnM . f)

In otherwords, I've stolen a page from Conor McBride's notebook and defined lift and embed as a higher-order monad in the category of monad morphisms. Going back to the previous names, we can establish that certain laws must hold:
-- Categorical version
lift >|> f = f
f >|> lift = f
(f >|> g) >|> h = f >|> (g >|> h)

-- bind/return version
embed lift m = m
embed f (lift m) = f m
embed g (embed f m) = embed (\x -> embed g (f x)) m

-- join/return version
squash (lift m) = m
squash (mapT lift m) = m
squash (squash m) = squash (mapT squash m)
Obviously, I won't suggest we break the existing MonadTrans class by adding an additional method. All we have to do is simply define a new MonadM class and make all existing monad transformers instances of it and possibly make MonadTrans a super-class of it.

I'll bet more experienced Haskell programmers have wanted mapT or squash in one form or another. The above type-class provides a uniform interface to these operations, so that you don't have to rely on transformer-specific functions like mapStateT or mapMaybeT.

Note that all monad transformers have a sensible instance for MonadM that obeys the above laws. Usually the easiest route is to first define squash (i.e. joinM) and mapT (i.e. fmapM). mapT is usually very straight-forward to write and simply involves type-chasing. squash simply takes the inner monad transformer and combines its operations with the outer monad transformer. Once you define these two, then you can easily define embed:
-- i.e.: (bindM f) = joinM . fmapM f
embed f = squash . mapT f
In the near future I will release a package containing this type-class and appropriate instances for the standard monad transformers. Additionally, the pipes-2.4 release will include an extra motivation for defining the above type-class, besides the obvious utility of having mapT and squash functions.


  1. I don't believe embed is the right abstraction.

    There is something very close to it that I do advocate, which I've called 'hoist' for a few years now:

    class MonadHoist t where
    hoist :: (Monad m, Monad n) => (forall a. m a -> n a) -> t m a -> t n a

    This represents the lifting of natural transformations into the transformer.

    Unlike embed, you aren't forced into situations where you need to randomly discard state, etc.

    The problem is, just like your proposed MonadTrans variant, it requires Rank2Types and therefore falls outside of the scope of the transformers which provides MonadTrans and is Haskell 98) and the MTL (which does not use Rank2Types)

    1. er. I meant monad homomorphisms, not natural transformations.

      It lifts a monad homomorphism from m to n into a monad homomorphism from t m to t n.

    2. I don't see why/when embed forces you into situations where you need to randomly discard state. Can you elaborate a bit?

    3. He means for the case of StateT. StateT forms a sensible higher order functor (i.e. just mapT), but not a sensible higher order monad.

    4. What Edward is proposing is to have a class of *functorial* monad transformers (transformers which are endofunctors in the category Mon(C) of monads over a category C and monad morphisms)

      Note that some transformers, like the continuation monad transformer, are not functorial.

      Even less monad transformers are a monad in Mon(C) . In fact, I think it's only those arising from distributive laws of monads (error and reader).

      However, in the code above it is not clear when you mean a natural transformation between monads and when you mean a monad morphism.