## 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 `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
`````` PDF - Download Haskell Language for free