Writing a Monad Transformer, does it really need so many hardcoded instances

Question

I am a long time monad transformer user, first time monad transformer writer.... And I feel like I've done something unnecessary.

We are working on a project that has multiple DB tables, and hardcoding the set into different monad stacks was becoming unwieldy, so we decided to break it into different pluggable monad transformers, allowing us to pick and choose at the function type level, like this

doSomething::(HasUserTable m, HasProductTable m)=>Int->m String

(HasXTable is the class, XTableT is the concrete monad transformer). These separate monad transformers could be inserted or removed in a fully modular fashion, and would store the DB handles, require ResourceT, etc....

My first attempt was to just wrap around ReaderT, which would be used to hold the DB handle. It became immediately apparent that this would not work, as ReaderT (and StateT, etc) can not be stacked without using chains of hardcoded "lift"s, thus breaking the pluggable modularity of the stack elements.

The only solution seemed to be to write completely separate copies of the ReaderT monad, each allowing access to the others at a lower level. This works, but the solution is filled with boilerplate code, something like this

class HasUserTable m where
    getUser::String->m User

newtype UserTableT m r = UserTableT{runUserTableT::String->m r}

--Standard monad instance stuff, biolerplate copy of ReaderT
instance Functor m=>Functor (UserTableT m) where....
instance Applicative m=>Applicative (UserTableT m) where....
instance Monad m=>Monad (UserTableT m) where....
instance Monad m=>HasUserTable (UserTableT m) where....

--Gotta hardcode passthrough rules to every other monad transformer
--in the world, mostly using "lift"....
instance MonadTrans BlockCacheT where....
instance (HasUserTable m, Monad m)=>HasUserTable (StateT a m)....
instance (HasUserTable m, Monad m)=>HasUserTable (ResourceT m)....
.... etc for all other monad transformers

--Similarly, need to hardcode passthrough rules for all other monads
--through the newly created one
instance MonadResource m=>MonadResource (UserTableT m) where....
instance MonadState a m=>MonadState a (UserTableT m) where....
instance (MonadBaseControl IO m) => MonadBaseControl IO (UserTableT m)....
.... etc for all other monad transformers

What makes this even worse is that we need to add even more passthrough rules for each new monad transformer we add (ie- each new table we add needs to passthrough all the other table monad transformers, so we need n^2 instance declarations!)

Is there a cleaner way to do this?

This looks very reminiscent of extensible effects. hackage.haskell.org/package/free-vl has an implementation and references to papers that explain it. — Paul Johnson
"so we need n^2 instance declarations" this is a well known problem with the mtl style of monad transformers. If you write your type as ReaderT String m r instead, you can use generalized newtype deriving to derive those instances which are identical to the ones for reader (which seems like most of them here). You can replace most of the instances with MonadTrans t, HasUserTable m => HasUserTable (t m) but this sort of kills type inference, and requires several extensions. — user2407038
@user2407038 the problem with using a generalized MonadTrans t, HasUserTable m=>HasUserTable (t m) was that it applied to UserTableT also, conflicting with the proper instance that I needed to write. I suspect that this is why the n^2 problem exists at all (otherwise they would have just done this for all monad transformers). I think your comment on the n^2 problem might be the answer to my question, although not a happy one.... You can't do anything better with monad transformers, and perhaps even Haskell. I you have a reference discussing this problem, I'd accept that as the answer. — jamshidh

Benjamin Hodgson Benjamin Hodgson · Accepted Answer · 2016-02-21T20:16:41

Yep, that's one of the problems with monad transformers: when you add a new transformer, you have to write an ever-increasing number of boilerplate instances. It's n instances each time, for a total of O(n^2) instances. You can observe this scaling issue in the mtl source code, for example. Monad transformers are not readily extensible.

Now, a good percentage of the monads we use on a daily basis can be expressed as some combination of the transformers provided by mtl, which means that someone else has already done the work of writing all of those boring instances. But those transformers certainly don't cover every monad, and you'll get bitten whenever you need to write your own.

That's why there's ongoing effort being put into devising new approaches to effect typing. A good example in Haskell is Kiselyov et al's extensible-effects library, which takes an algebraic approach to effect typing, based on free monads. The design of this library is described in two articles: An Alternative to Monad Transformers, which spends some time describing problems with the mtl approach, and More Extensible Effects, describing an updated and optimised implementation of the library.

If you want to see how far safe and extensible effect typing can be taken, see Edwin Brady's effects library for the Idris language. There exist quite a lot of resources explaining effects: a tutorial, the original Programming and Reasoning with Algebraic Effects article, and Resource-dependent Algebraic Effects describing some newer features of effects. There's probably some more resources that I've forgotten in this list.

Writing a Monad Transformer, does it really need so many hardcoded instances

1 Answers