Published on June 14, 2014; tags: Haskell, 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.

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.

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.