[Haskell-cafe] Monad for HOAS?

[Lauri Alanko]

On Wed, May 14, 2008 at 10:11:17AM +0100, Edsko de Vries wrote:
> Suppose we have some data structure that uses HOAS; typically, a DSL
> with explicit sharing. For example:
> 
> > data Expr = One | Add Expr Expr | Let Expr (Expr -> Expr)
> 
> When I use such a data structure, I find myself writing expressions such
> as
> 
> > Let foo $ \a -> 
> > Let bar $ \b ->
> > Add a b
> 
> It seems to me that there should be a monad here somewhere, so that I
> can write this approximately like
> 
> do a <- foo
>    b <- bar
> 	return (Add a b)

Neat idea, but the monad can't work exactly as you propose, because
it'd break the monad laws: do { a <- foo; return a } should be equal
to foo, but in your example it'd result in Let foo id.

However, with an explicit binding marker the continuation monad does
what you want:

import Control.Monad.Cont

data Expr = One | Add Expr Expr | Let Expr (Expr -> Expr)

type ExprM = Cont Expr

bind :: Expr -> ExprM Expr
bind e = Cont (Let e)

runExprM :: ExprM Expr -> Expr
runExprM e = runCont e id

Now you'd write your example as

do a <- bind foo
   b <- bind bar
   return (Add a b)

HTH.


Lauri