AST annotations

AST (Abstract Syntax Trees) annotation is an important step in compilation process. I have been trying to figure out how these would be implemented in Haskell. By studying a paper on SPARK (The design and implementation of SPARK, A Toolkit for Implementing Domain Specific Languages), I sort of developed a general intuitive understanding of this process. You need to traverse over the AST in either pre-order or post-order or a mix of pre and post order. And you need to add extra data to each node in the AST during this traversal. Additionally, you can conduct an extensive set of semantic tests during this traversal process.

So how does it map to Haskell? Here are my guesses AST annotation is essentially an isomorphic process which takes an input AST and generates an output AST. The structure of AST is maintained isomorphically while additional information is stuck on each node in the AST during the transformation process. Also, if there are semantic errors detected during the annotation, we simply generate a list of such errors and return an empty AST as a result. Eigher AST or Errors. Naturally errors will have a reference to source code locations where the problem was observed.

I don't know, whether my understanding is correct or not. I guess I am reasonably correct. :-) I need to study a lot more in depth.