Haskell Language Free Monads The Freer monad
Example
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
Freeris isomorphic toFree. Recall the definition of theCoYonedafunctor:data CoYoneda i b where CoYoneda :: i a -> (a -> b) -> CoYoneda i b
Freer iis equivalent toFree (CoYoneda i). If you takeFree's constructors and setf ~ 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) bfrom which we can recover
Freer i's constructors by just settingFreer 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
