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:

classHastmwhereliftH::tIdentitya->ma

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

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.

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'::Monadm=>ReaderTrmrprog'=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:

(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 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:Any transformer lifts into itself if it is an

`MFunctor`

(goodbye`ContT`

at this point):Adding further transformers onto a monad always preserves the effect:

Lifting first order effects is easy:

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:

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:It will say:

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

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

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