[Haskell-cafe] Monad for HOAS?

[Edsko de Vries]

Hi,

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)

or something along those lines. It is however not at all clear to me
what this monad should look like. I have experimented with adding a type
parameter to Expr, something like

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

which has the additional benefit of supporting catamorphisms; I have
also experimented with defining various variations on

> Let a b = Let a (a -> b)

and making Let an instance of Monad rather than Expr; but none of my
experiments wered satisfactory.  

Am I missing something obvious, or is there a good reason this cannot be
done?

Thanks,

Edsko