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