Day 9: Freer — Free Monads

On day 5, I wrote about how to make a set monad — first build a sequence of instructions that describe how to build a Set, and then interpret that sequence of instructions to give a result, an actual Set.

That technique of building a monadic instruction language, and separately building interpreters, is more generally useful, and free monads are a tool to help you do that.

I’m going to talk about the freer monad, FFree which is like Free but even freer — Free has been round longer and you’ll find more writing about it, but FFree needs a little bit less boilerplate and appeals to me a bit more.

The language needs to be built as a datastructure that implements the Monad typeclass. There are two parts to that: some routine monadic stuff to deal with >>= and return which can be the same for every language, and the application-specific interesting stuff which represents instructions in your specific language.

FFeer provides the routine stuff, with a hole to plug in a datatype for the interesting instructions (call it YourLanguage); this gives a monad FFree YourLanguage.

YourLanguage can be anything of kind * -> *.— that is any data type with a single type parameter. GADT syntax fits well for defining these types, and that’s what I’ll use here — but it isn’t compulsory.

For example, here is a simple state language with instructions to get and put integers:

data State x where
 Get :: State Integer
 Put :: Integer -> State ()

Get is an instruction which will return an integer, and Put is an instruction that will store an integer, returning nothing (or () rather).

There’s nothing in that language to provide monad stuff: sequencing, or pure values — but FFree State wraps this language with exactly those things.

Now we can write monadic programs which get and put values, using etaF to lift our instructions into the freer monad: (etaF isn’t my choice of name. You could imagine it being called doCommand perhaps)

> x = do
  etaF (Put 7)
  a <- etaF Get
  return (a + 1)
> :t x
x :: FFree State Integer

However, we can’t yet run that program: x just holds a data structure that is a basically just a transcription of the do notation into the FFree data type.

So, we need an interpreter. One of the strengths of free monads is that you can have different interpreters for the same language. Here are two interpreters for FFree State.

The first is pure. We pass in an initial state and a program, and get back a final result. There is a case for pure values, and then for each kind of instruction, a case that takes an instruction and the rest of the program and does whatever the right thing is: in the case of Get, it runs the rest of the program passing in the state, and in the case of Put, it runs the rest of the program with that new state.

runPure :: Integer -> FFree State a -> a
runPure old_state (FPure a) = a
runPure old_state (FImpure (Get) rest_of_program) =
  runPure old_state (rest_of_program old_state)
runPure old_state (FImpure (Put new_state) rest_of_program) =
  runPure new_state (rest_of_program ())
> runPure 100 x
8

The second interpreter runs in IO and outputs some tracing messages. We can run exactly the same program x in it without modification:

runIO :: Integer -> FFree State a -> IO a
runIO old_state (FPure a) = return a
runIO old_state (FImpure (Get) rest_of_program) = do
  putStrLn "Getting state"
  runIO old_state (rest_of_program old_state)
runIO old_state (FImpure (Put new_state) rest_of_program) = do
  putStrLn "Setting state"
  runIO new_state (rest_of_program ())
> runIO 100 y
Setting state
Getting state
8

Note that the interpreter is entirely in charge of what to do with the rest of the program, just like >>= is general — if you were implementing a language with exceptions, for example, you wouldn’t call rest_of_program when interpreting a throw; and if you were implementing non-deterministic search (like []) then you’d call rest_of_program many times.

So how do you use the freer monad to do something different? You write an instruction type, and you write one (or more) interpreters, and you let FFree provide the boiler plate.

This all fits in the with the mindset of “first build a language or a library to solve your problem, then solve your problem using that language or library.” Which I don’t necessarily agree with but it is an interesting idea.

Downsides

The performance can be bad.

You and the compiler lose some ability to reason about what your program will do: in a state monad, put 1 >> put 2 is the same as put 2 and so maybe that first step can be optimised away. With a free monad approach, you don’t get to know the behaviour until you apply an interpreter. (and indeed, in the above runIO case, put 1 >> put 2 would give different output to just put 2 )

See Also

Day 3 talked about interpeting the Maybe monad in two different ways: in [] and in IO, using monad morphisms.

The source code for FFree frustratingly isn’t on hackage but grab it from http://okmij.org/ftp/Computation/free-monad.html#freer — there is a freer package on hackage, but you’ll have to wait until tomorrow to discover what that does.