Two failed attempts at extensible effects

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.

The competing free monad implementations were:

• Free: the standard Pure a | Free (f (Free f a)) free monad
• Codensity: forall b. (a -> f b) -> f b, as described in Asymptotic Improvement of Computations over Free Monads
• Church: forall w. (a -> w) -> (f w -> w) -> w, as described in Free Monads for Less. This is the Church- (or Boehm-Berarducci-) encoded version of Free.
• NoRemorse, as described in Reflection without Remorse (code taken from Atze van der Ploeg’s repository)

The benchmark compared the performance of State-like monads implemented on top of each free monad. I also added a plain State from the transformers package to this comparison.

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.