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