Haskell Language Free Monads The Freer monad


There's an alternative formulation of the free monad called the Freer (or Prompt, or Operational) monad. The Freer monad doesn't require a Functor instance for its underlying instruction set, and it has a more recognisably list-like structure than the standard free monad.

The Freer monad represents programs as a sequence of atomic instructions belonging to the instruction set i :: * -> *. Each instruction uses its parameter to declare its return type. For example, the set of base instructions for the State monad are as follows:

data StateI s a where
    Get :: StateI s s  -- the Get instruction returns a value of type 's'
    Put :: s -> StateI s ()  -- the Put instruction contains an 's' as an argument and returns ()

Sequencing these instructions takes place with the :>>= constructor. :>>= takes a single instruction returning an a and prepends it to the rest of the program, piping its return value into the continuation. In other words, given an instruction returning an a, and a function to turn an a into a program returning a b, :>>= will produce a program returning a b.

data Freer i a where
    Return :: a -> Freer i a
    (:>>=) :: i a -> (a -> Freer i b) -> Freer i b

Note that a is existentially quantified in the :>>= constructor. The only way for an interpreter to learn what a is is by pattern matching on the GADT i.

Aside: The co-Yoneda lemma tells us that Freer is isomorphic to Free. Recall the definition of the CoYoneda functor:

data CoYoneda i b where
  CoYoneda :: i a -> (a -> b) -> CoYoneda i b

Freer i is equivalent to Free (CoYoneda i). If you take Free's constructors and set f ~ CoYoneda i, you get:

Pure :: a -> Free (CoYoneda i) a
Free :: CoYoneda i (Free (CoYoneda i) b) -> Free (CoYonda i) b ~
        i a -> (a -> Free (CoYoneda i) b) -> Free (CoYoneda i) b

from which we can recover Freer i's constructors by just setting Freer i ~ Free (CoYoneda i).

Because CoYoneda i is a Functor for any i, Freer is a Monad for any i, even if i isn't a Functor.

instance Monad (Freer i) where
    return = Return
    Return x >>= f = f x
    (i :>>= g) >>= f = i :>>= fmap (>>= f) g  -- using `(->) r`'s instance of Functor, so fmap = (.)

Interpreters can be built for Freer by mapping instructions to some handler monad.

foldFreer :: Monad m => (forall x. i x -> m x) -> Freer i a -> m a
foldFreer eta (Return x) = return x
foldFreer eta (i :>>= f) = eta i >>= (foldFreer eta . f)

For example, we can interpret the Freer (StateI s) monad using the regular State s monad as a handler:

runFreerState :: Freer (StateI s) a -> s -> (a, s)
runFreerState = State.runState . foldFreer toState
    where toState :: StateI s a -> State s a
          toState Get = State.get
          toState (Put x) = State.put x