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

dsl, haskell, monads

Solution

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 `a`s 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

- `ApRead` is a node which has no label and has one descendant coming off it for every value of type `String`

- `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

- Put type signatures on everything top-level. Your colleagues, Stack Overflow commenters and your future self with thank you.

- 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

Problem

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?

Original source