[Haskell-cafe] Shared modification inside lambdas

[Andrew Hunter]

I'm developing an embedded DSL in Haskell (for exact real arithmetic
work, but that's irrelevant right now.)  Among other things, the
language contains functions and application, as well as various
terms. In one iteration, the abstract syntax looked kinda like this
(in spirit, don't worry about the actually available terms...)

data Expr = Var String
          | Const Int
          | Plus Expr Expr
          | Quantified Range String Expr
          | Lambda String Expr
          | App Expr Expr

Here, lambda-terms just have the name of their bound variable and the
RHS.  Quantified terms are much like specialized lambdas; one note is
that you *will* have to evaluate the RHS of the quantified term with
many values for the argument.

It's obvious how to write an evaluator on these--just keep an
environment, etc.  All well and good, but it seems to me that if I'm
embedding the DSl, shouldn't I be able to use the host language's
facilities--for example, function abstractions and
applications--directly?

Well, I tried this, and it seems it works OK, like so:
           
data Expr = Var String
          | Const Int
          | Plus Expr Expr
          | Quantified Range (Int -> Expr)

I replaced Lambda terms and applications with Haskell-level functions.
Note that my quantifiers still need internal functions, but I replaced
them in the same fashion.  However, I have a problem; one thing I
often have to do with expressions is refine them, where refine has
type:

refine :: Expr -> Expr

and transforms expressions into more interesting ones via certain,
mostly simple rules.  The problem comes with functions, either just
plain lambdas or quantified ones.  The rule for refining functions
boils down to just refining (recursively) the RHS; in the old version,
that was easy!

refine (Lambda var rhs) = Lambda var (refine rhs)

I only refine while evaluating terms of type Expr, so top level
functions aren't important--by the time I'm evaluating them, I've
applied them to arguments--but quantified terms are a problem.  I
could write something like:

refine (Quantified range pred) = Quantified range pred' 
  where
    pred' = \c -> refine (pred c)

But the problem is that this refines the term, again, every time I
apply an argument to pred': I know I'm going to apply arguments many
times to that new pred, and I want to refine it /once/: refinement is
argument-agnostic, it only rearranges the structure of the AST, so in
theory it'd be nice if I could refine that structure, just duplicating
references to the appropriate free variable where I would have
duplicated refences to the appropriate (Var String) before.  Am I sore
out of luck here?

Is there a reasonable way I can implement my internal functions via
Haskell functions, but apply argument-agnostic transformations to the
RHS in a shared fashion?  Or, is there some optimization in GHC that
means I don't need to worry about this?

Thanks,
AHH