Really simple first order effect system with transformers - Haskell

I recently talked with people about effect systems and transformers. I wanted to demonstrate the "quadratic instances problem" of mtl, and then accidentally discovered a really simple solution to it (so I believe).

Transformers compose all right, but it's a nuisance to address the effects in a longer transformer stack. E.g. if your stack is WriterT w (ReaderT r (ExceptT e IO))), you have to do lift $ lift $ except e to throw an exception. And the number of lifts changes every time you modify your stack, which is horrible.

Enter mtl, which supplies you type classes like MonadReader which basically say "there is a ReaderT in your stack". So you can use ask :: MonadReader r m -> m r and never have to worry what else there is in your transformer stack. _BUT_ the issue is that you have to "handcraft" a new MonadWhatever class for every new transformer you think of, and you have to write one instance per class _and_ transformer, amounting to O(n^2) instances (assuming that there is a 1-1-correspondence between classes and transformers). These classes and instances are never hard to write, but it's not obvious how to automate it. This is not practically extensible.

Then people invent all kinds of effect systems and say that we should separate the effect (loosely said, the MonadWhatever class, or the API of the transformer) from the handler (the implementation of the transformer and its Monad instance). This is all nice and dandy if you want to do higher order effects, but if we really only want to solve the O(n^2) issue I think there is a simpler way.

The basic insight is that the essence of a transformer lies in what you can do if you apply it to the Identity monad. In fact, Reader r a is just a type synonym for ReaderT r Identity a.

So my proposal is: For a transformer t, the monad t Identity fully represents the effect we want to encode with t. Everything else follows naturally from there.

First, instead of writing a new class MonadWhatever corresponding to WhateverT, we can demand that it should be possible to lift WhateverT Identity into our monad:

class Has t m where
  liftH :: t Identity a -> m a

Any transformer lifts into itself if it is an MFunctor (goodbye ContT at this point):

class MFunctor t where
  hoist :: (forall x . m a -> n a) -> t m a -> t n a

instance (MFunctor t, Monad m) => Has t (t m) where
  liftH = hoist $ return . runIdentity

Adding further transformers onto a monad always preserves the effect:

instance (Functor m, MonadTrans t1, Has t m) => Has t (t1 m) where
  liftH = lift . liftH

Lifting first order effects is easy:

askH :: Has (ReaderT r) m => m r
askH = liftH ask

It's not possible to lift higher-order effects like listen :: m a -> m (a, w) or MonadPlus though, without specifying at least part of the transformer stack. But this I expect and accept.

I'm wondering whether this approach is already known and implemented somewhere.

It's an interesting solution to the problem of stacking transformers.
Btw. What do you do if there's two ReaderT in your mtl stack?

Henri Tuhola said:

Btw. What do you do if there's two ReaderT in your mtl stack?

Great question. Turns out I missed an important detail. You will get overlapping instances for Has (ReaderT r). Already now you will get overlapping instances when you write this simple program:

prog' :: Monad m => ReaderT r m r
prog' = askH'

It will say:

Overlapping instances for Has (ReaderT r) (ReaderT r m)
    arising from a use of ‘askH'’
  Matching instances:
    instance (MFunctor t, Monad m) => Has t (t m)
    instance (Functor m, MonadTrans t1, Has t m) => Has t (t1 m)

The solution, I think, is to mark the second instance overlappable:

instance {-# Overlappable #-} (Functor m, MonadTrans t1, Has t m) => Has t (t1 m) where
  liftH = lift . liftH

This means that we'll favour the outermost transformer in case we have several:

twoReaders :: ReaderT String (ReaderT String IO) ()
twoReaders = do
  env <- askH'
  liftIO $ putStrLn env

main :: IO ()
main = twoReaders `runReaderT` "outer" `runReaderT` "inner"

Running this gives the string outer.

(The reason I didn't realise this is because overlapping instances are only detected when you try to instantiate them, not when you're declaring them.)

I made this idea into a library: https://hackage.haskell.org/package/has-transformers