Roman Cheplyaka

Two failed attempts at extensible effects

June 14, 2014

After I had published The problem with mtl, many people wondered what my proposed solution was. If you, like them, are impatient to find out, feel free to peek at the slides from my kievfprog talk, or directly at the code on github.

Still, I’ll continue this series at my own pace. Today we’ll look at two failed solutions to the problem described in the previous article.

Free monads

The approach based on free monads, proposed in the original Extensible Effects paper by Oleg Kiselyov, Amr Sabry, and Cameron Swords, and implemented in the corresponding package indeed addresses our problem. My plan for ZuriHac was to revise its API and measure and possibly improve its performance.

I started the hackathon by writing a benchmark to compare different free monad implementations, to decide which one to use internally in the library. What surprised me most was not the relative performance of different representations, but how the State monad implemented through free monads did relatively to the State from transformers.

The free monad based State consistently performed up to two orders of magnitude slower than the transformers’ version. And the free monad version was essentially Free State, even without the Typeable-based open unions (which certainly carry an overhead of their own).

Thus, it became clear that if an extensible effects library is to perform well, it has to be based on raw transformers, not free monads.

mtl

If, as I wrote in the previous article, the functional dependency is an issue in mtl, can we simply get rid of it?

Well, we could, but that by itself wouldn’t help much. You see, mtl’s classes work by having instances that lift, say, MonadState actions through ReaderT, WriterT, and other transformers known to mtl:

instance MonadState s m => MonadState s (ReaderT r m) where
    get = lift get
    put = lift . put
    state = lift . state

In order to make multiple MonadState instances work, we’d have to write a similar instance for lifting MonadState through StateT itself. But in that case GHC would become confused: it wouldn’t know whether to lift a given get through a StateT, or attempt to execute it right there. It just isn’t smart enough to make a decision based on the type of the StateT’s state.

My solution to this problem is exactly to teach GHC to make such a decision. We’ll see how it works in the next article.