# Examining Hackage: operational

In this installment of “jozefg is confused by other people’s code” we turn to `operational`

. This is a package that’s a little less known than I’d like. It provides a monad for transforming an ADT of instructions, a monad that can be used with `do`

notation and separates out interpretation.

Most people familiar with free monads are wondering what the difference is between operational’s approach and using free monads. Going into this, I have no clue. Hopefully this will become clear later on.

## Diving Into The Source

Let’s get started shall we

`~$ cabal get operational`

Happily enough, there’s just one (small) file so we’ll go through that.

To start with `Control.Monad.Operational`

exports

```
module Control.Monad.Operational (
Program, singleton, ProgramView, view,
interpretWithMonad,
ProgramT, ProgramViewT(..), viewT,
liftProgram,
) where
```

Like with most “provides a single monad” packages, I’m most interested in how `Program`

works. Looking at this, we see that it’s just a synonym

Just like the mtl, this is defined in terms of a transformer. So what’s this transformer?

```
data ProgramT instr m a where
Lift :: m a -> ProgramT instr m a
Bind :: ProgramT instr m b -> (b -> ProgramT instr m a)
-> ProgramT instr m a
Instr :: instr a -> ProgramT instr m a
```

So `ProgramT`

is a GADT, this is actually important because `Bind`

has an existential type variable: `b`

. Otherwise this is really just a plain tree, I assume `(>>=) = Bind`

and `return = Lift . return`

in the monad instance for this. And finally we can see that instructions are also explicitly supported with `Instr`

.

We can confirm that the `Monad`

instance is as boring as we’d expect with

```
instance Monad m => Monad (ProgramT instr m) where
return = Lift . return
(>>=) = Bind
instance MonadTrans (ProgramT instr) where
lift = Lift
instance Monad m => Functor (ProgramT instr m) where
fmap = liftM
instance Monad m => Applicative (ProgramT instr m) where
pure = return
(<*>) = ap
```

So clearly there’s no interesting computation happening here. Looking at the export list again, we see that there’s a helpful combinator `singleton`

for building up these `Program[T]`

s since they’re kept abstract.

Which once again is very boring.

So this is a lot like free monads it seems since neither one of these actually does much in its monad instance. Indeed the equivalent with free monads would be

```
data Free f a = Pure a | Free (f (Free f a))
instance Functor f => Monad (Free f) where
return = Pure
Pure a >>= f = f a
(Free a) >>= f = Free (fmap (>>= f) a)
singleton :: Functor f => f a -> Free f a
singleton = Free . fmap Pure
```

The obvious differences is that

`Free`

requires a functor while`Program`

doesn’t`Free`

s monad instance automatically guarantees laws

2 is the bigger one for me. `Free`

has a tighter set of constraints on its `f`

so it can guarantee the monad laws. This is clearly false with `Program`

since `return a >>= f`

introduces an extra `Bind`

instead of just giving `f a`

.

This would explain why `ProgramT`

is kept abstract, it’s hopelessly broken just to expose it in its raw form. Instead what we have to do is somehow partially normalize it before we present it to the user.

Indeed that’s exactly what `ProgramViewT`

is representing. It’s a simpler data type

```
data ProgramViewT instr m a where
Return :: a -> ProgramViewT instr m a
(:>>=) :: instr b
-> (b -> ProgramT instr m a)
-> ProgramViewT instr m a
```

This apparently “compiles” a `Program`

so that everything is either binding an instruction or a pure value. What’s interesting is that this seems to get rid of all `Lift`

’s as well.

How do we produce one of these? Well that seems to be `viewT`

’s job.

```
viewT :: Monad m => ProgramT instr m a -> m (ProgramViewT instr m a)
viewT (Lift m) = m >>= return . Return
viewT ((Lift m) `Bind` g) = m >>= viewT . g
viewT ((m `Bind` g) `Bind` h) = viewT (m `Bind` (\x -> g x `Bind` h))
viewT ((Instr i) `Bind` g) = return (i :>>= g)
viewT (Instr i) = return (i :>>= return)
```

Note that this function returns an `m (ProgramViewT instr m a)`

, not just a plain `ProgramViewT`

. This makes sense because we have to get rid of the lifts. What I think is particularly interesting here is that the 2nd and 3rd cases are just the monad laws!

The second one says binding to a computation is just applying the function to it in the obvious manner. The third re-associates bind in a way guaranteed by the monad laws.

This means that while `ProgramT`

isn’t going to satisfy the monad laws, we can’t tell because all the things said to be equal by the monad laws will compile to the same view. Terribly clever stuff.

The rest of the module is mostly boring stuff like `Monad*`

instances. The last interesting functions is `interpretWithMonad`

```
interpretWithMonad :: forall instr m b.
Monad m => (forall a. instr a -> m a) -> (Program instr b -> m b)
interpretWithMonad f = eval . view
where
eval :: forall a. ProgramView instr a -> m a
eval (Return a) = return a
eval (m :>>= k) = f m >>= interpretWithMonad f . k
```

This nicely highlights how you’re supposed to write an interpreter for a `Program`

. `eval`

handles the two cases of the `view`

using the mapping to a monad we provided and `view`

handles actually compiling the program into these two cases. All in all, not too shabby.

## Surprise, There Were Docs The Whole Time!

Now I assume that most people didn’t actually download the source to operational, but you really should! Inside you’ll find a whole directory, `doc`

. It contains a few markdown files with explanations and references to the appropriate papers as well as a couple examples of actually building things with `operational`

.

Now that you understand how the current implementation works, you should be able to understand most of what is being said there.

## Wrap Up

So `operational`

illustrates a neat trick I rather like: using modularity to provide an `O(1)`

implementation of `>>=`

and hide its rule breaking with a view.

This package also drops the positivity requirement that `Free`

implies with its functor constraint. Which I suppose means you could have

Which is potentially useful.

Last but not least, `operational`

really exemplifies having a decent amount of documentation even though there’s only ~100 lines of code. I think the ratio of documentation : code is something like 3 : 1 which I really appreciate.