If I understand you correctly, the problem is to annotate an already constructed tree with arbitrary pieces of new data -- hopefully without reconstructing the tree. Perhaps the approach used in the FLOLAC type-checkers would be helpful. The `tree' was an expression in lambda-calculus to type check. The new annotations are the reconstructed types, of each node in the tree (of each sub-expression). I wanted to annotate each sub-expression with its reconstructed type -- without re-defining the data type of expressions or rebuilding the tree. The expression should stay as it was, I merely want to associate, after the fact, additional pieces of data with each node. I also wanted the code to be pure and avoid STRefs let alone StableNames and any IO. Here are the files in question: http://okmij.org/ftp/Computation/FLOLAC/TEvalNC.hs http://okmij.org/ftp/Computation/FLOLAC/TEvalNR.hs TEvalNC.hs is the ordinary type checker for the simply-typed lambda calculus with constants and the fix-point. The type reconstructor (aka, non-standard, abstract evaluator) has this type teval :: TEnv -> Term -> Typ Given the type environment and a term, it returns its inferred type (or reports an error). The file TEvalNR.hs returns not only the reconstructed type of the term but also the types of all the subterms. The latter data are returned in a `virtual' typed AST -- virtual because the original AST is not modified and the inferred types are attached to AST nodes, well, virtually. Generally speaking, after a simple modification teval could be made total: it would return reconstructed types of the subterms even if the entire term is ill-typed. That modification was one of the exercises. The intention was to model OCaml -- which, given a special flag, can dump the inferred types of all sub-expressions, even if the overall type checking failed. In Emacs and vi, one can highlight an expression or variable and see its inferred type. If the type checking failed, one can still explore what the type checker did manage to infer.