How do I convert a functional DSL into a Monad in Haskell?

Question

The following Haskell code is a simple "console IO" DSL:

data Ap a = Ap { runAp :: ApStep a }

data ApStep a =
    ApRead   (String -> Ap a)
  | ApReturn a
  | ApWrite  String (Ap a)

ioRead    k   = Ap $ ApRead k
ioReturn  a   = Ap $ ApReturn a
ioWrite   s k = Ap $ ApWrite s k
ioWriteLn s   = ioWrite (s ++ "\n")

apTest =
  ioWriteLn "Hello world!" $
  ioRead $ \i ->
  ioWriteLn ("You wrote [" ++ i ++ "]") $
  ioReturn 10

uiRun ap =
  case runAp ap of
    ApRead k     -> uiRun (k "Some input")
    ApReturn a   -> return a
    ApWrite s k  -> putStr s >> uiRun k

run = uiRun apTest

It works OK however I would like to write the "application" apTest using a monad instead of using $. In other words like this:

apTest = do
  ioWriteLn "Hello world!"
  i <- ioRead
  ioWriteLn $ "You wrote [" ++ i ++ "]"
  return 10

The problem is that the code is resisting all my attempts to turn the "function style" DSL into a monad. So the question is how to implement a monad instance for this DSL that allows you to write apTest monad style instead of "$" style?

Answer 1

Sure it's a monad. In fact it would be simpler to express it as a free monad [1] but we can work with what you've got.

Here's how we know it's a monad: if you have a type data Foo a = ... where Foo represents some sort of recursive tree structure where as only occur at the leaves then you have a monad. return a is "give me a tree consisting of one leaf labelled by a", and >>= is "substitution at the leaves".

In your case Ap is a tree structure where

• ApReturn a is a leaf

• there are two sorts of interior nodes

  1. ApRead is a node which has no label and has one descendant coming off it for every value of type String
  2. ApWrite is a node which is labelled by a String and has only one descendant coming off it

I've added the monad instance to your code below. return is just AppReturn (plus the Ap wrapper). >>= is just recursively applying >>= and substituting at the leaves.

A couple of hints for the future

1. Put type signatures on everything top-level. Your colleagues, Stack Overflow commenters and your future self with thank you.
2. The Ap wrapper was unnecessary. Consider removing it.

Enjoy!

data Ap a = Ap { runAp :: ApStep a }

data ApStep a =
    ApRead      (String -> Ap a)
    |   ApReturn    a
    |   ApWrite     String (Ap a)

ioRead    k   = Ap $ ApRead k
ioReturn  a   = Ap $ ApReturn a
ioWrite   s k = Ap $ ApWrite s k
ioWriteLn s   = ioWrite (s ++ "\n")

apTest =
  ioWriteLn "Hello world!" $
  ioRead $ \i ->
  ioWriteLn ("You wrote [" ++ i ++ "]") $
  ioReturn 10

uiRun ap =
  case runAp ap of
    ApRead k        -> uiRun (k "Some input")
    ApReturn a      -> return a
    ApWrite s k     -> putStr s >> uiRun k

run = uiRun apTest

instance Monad Ap where
    return = Ap . ApReturn
    Ap (ApReturn a) >>= f = f a
    Ap (ApRead r) >>= f = Ap (ApRead (\s -> r s >>= f))
    Ap (ApWrite s a) >>= f = Ap (ApWrite s (a >>= f))

monadRead = Ap (ApRead (\s -> return s))
monadWrite s = Ap (ApWrite s (return ()))
monadWriteLn = monadWrite . (++ "\n")

apTestMonad = do
  monadWriteLn "Hello world!"
  i <- monadRead
  monadWriteLn $ "You wrote [" ++ i ++ "]"
  return 10

monadRun = uiRun apTestMonad

[1] http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html

Answer 2

Is my thing a monad?

I don't have any specific help for you, but I have a bit of general guidance that is way too long for a comment. When my intuition tells me I want to make something an instance of Monad, the first thing I do is sit down with a pen and a piece of paper and I ask myself,

Is my thing really a monad, though?

As it turns out, a lot of times it isn't – it was just my intuition wanting to jump on the bandwagon a bit too quickly. You can't very well create a Monad instance for your thing if your thing isn't a monad. Here's my checklist of three things that need to be covered before I call my thing a monad.

When I have decided that my thing is a monad, I have usually also in the process accidentally come up with everything I need to create a monad instance for my thing, so this is not a useless exercise in rigor. This actually will give you the implementations of the two operations you need to create a monad instance for your thing.

What are monads?

For your thing to be a monad, it needs to have two operations. These are commonly, in the Haskell world, referred to as return and (>>=) (pronounced "bind".) A monad can be seen as a computation with a "context" of some kind. In the case of IO, the context is side effects. In the case of Maybe, the context is failure to provide a value, and so on. So a monad is something that has a value, but there's something more than just the value. This something more is often referred to as a "context" for lack of a better word.

Operations

Anyway, the signatures involved are

return :: Monad m => a -> m a
(>>=) :: Monad m => m a -> (a -> m b) -> m b

This means that return takes any old value a and puts it into the context of your monad somehow. This is often a fairly easy function to implement (there aren't too many ways you can put any a value into a context.)

What's interesting is (>>=). It takes a value a inside your monad context and a function from any value a to a new value b but inside your monad context. It then returns the b value with context. You need to have a sensible implementation of this before you even consider making a Monad instance for your thing. Without (>>=), your thing is definitely not a monad.

Laws

However, it isn't enough to have return and (>>=)! I said the implementation needs to be sensible. This also means that your thing must have implementations of return and (>>=) that obey the monad laws. They are as follows:

1. return a >>= f should be the same thing as f a
2. m >>= return should be the same thing as just m
3. (m >>= f) >>= g should be the same thing as m >>= (\x -> f x >>= g)

These make a lot of sense* (the first two are trivial and the third one is just an associativity law), and we need all monads to obey them. This is not checked by the compiler (but it might assume they will hold) so it is your responsibility to make sure they hold.

If your monad-to-be obeys these laws, you get a monad! Congratulations! The rest is just paperwork, i.e. defining the instance as

instance Monad MyThing where
  return a = {- definition -}
  m >>= f  = {- definition -}

and then you are ready to use do syntax as well!

---

* More information on the Haskell wiki page on monad laws.