Day 10: Eff — Extensible Effects

Free monads let you take a data type that represents instructions, or (approximately the same) effects that you want to happen, and then have interpreters which understand how to make those effects actually happen.

As presented yesterday, if you want a particular set of effects, you need to explicitly define a datatype to represent that set of effects.

But datatypes can be defined in other ways: you can construct them out of other datatypes. For example, say you have a datatype for State effects and a datatype for exception effects (such as Throw) then we could define Combo:

data Combo a = L (State a) | R (Exc a)
> :kind Combo
Combo :: * -> *

To interpret FFree Combo we need an interpreter which can handle three instruction cases: L Put L Get and R Throw.

Or, we can be more fancy and generalise this:

data (l :+: r) a = InL (l a) | InR (r a)
type Combo = State :+: Exc

and in fact we can construct arbitrarily long lists of component data types to give a free(r) monad with a long list of effects:

FFree (State :+: Exc :+: Logging :+: Backtracking) a

That is all presented in the functional pearl Datatypes a la Carte linked at the bottom.

However that is only half the story — having defined the datatype in modular fashion, it would be nice to also define corresponding interpreters in modular fashion, so that we might compose a state interpreter and an exception interpreter and a logging interpreter and a backtracking interpreter and end up with a single thing that knows how to do all of those things.

Remember that we can write an interpreter for some FFree that runs inside another monad: yesterday I showed an interpreter for FFree State that ran inside IO— we still needed something that knew how to run IO programs, although luckily Haskell already knows how to do that.

We can use a similar approach here: if we’ve got FFree (State :+: others) then we can write an interpreter that knows how to deal with State effects, but doesn’t touch the others:

interpretState :: FFree (State :+: others) -> FFree others

If we’ve got a signature FFree (State :+: others) then we can write an interpreter that interprets only that state effect, in FFree others . We still need to provide an interpreter for others , whatever those other effects are, but through a stack of interpreters like this, we can get ensure all effects are interpreted (in whatever underlying layer we want — perhaps IO, or perhaps a pure value). There are other tricks that can happen: an interpreter can see all of the effects in the stack and doesn’t have to be constrained to interpret only one particular type of effect. This is a big difference from mtl style monad transformers, where layering of “interpreters” is strictly defined at compile time, and each layer can only deal with its own particular effect.

There is more type level magic in the real implementation that builds upon the above to make things more convenient to use, and so if/when you read the papers or use the library, you’ll find the syntax quite different.

Practicalities

I ported my reddit bot to use extensible effects, and gave a talk at the London Haskell User Group about it. My biggest difficulty was a very different style of type signature and type error — it would tell me if the program wouldn’t type check but I found it difficult to use those errors to guide me to the correct solution. That’s also something I have found, to a lesser extent, with lenses.

See Also

Datatypes A La Carte — this describes building up the data types, but doesn’t describe how they could be interpreted with modular interpreters.

http://okmij.org/ftp/Haskell/extensible/more.pdf

Ollie Charles wrote about this in 24 Days of Hackage three years ago.