We present techniques for representing typed abstract syntax trees in
the presence of observable recursive structures. The need for this
arose from the desire to cope with left-recursion in combinator based
parsers. The techniques employed can be used in a much wider setting
however, since it enables the inspection and transformation of any
program structure, which contains internal references. The hard part of
the work is to perform such analyses and transformations in a setting
in which the Haskell type checker is still able to statically check the
correctness of the program representations, and hence the type
correctness of the transformed program.
See also the Haskell Workshop 2004 article.