[Haskell-cafe] Painting logs to get a coloured tree

[oleg at okmij.org]

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.