When writing a compiler, one typically annotates the syntax tree in various phases. What the nodes are annotated with will vary over the course of the program; one might add type information during a type synthesis phase.

By making the abstract syntax tree polymorphic in the annotation type, we get type safety at all phases. For example:

data Type = IntTy
| ...data Ast a = IntLit a Int
| StringLit a String
| ...annotateTypes :: Ast () -> Ast Type

This Ast type will be a functor, so we can map over annotations and void will discard annotations.

# Syntactic Sugar

We can use polymorphism to ban certain constructors at certain phases. This could be useful if you have a desugaring phase which (for instance) rewrites all for-loops into while-loops.

We could share a data type between parsing and desugaring like so:

data Statement a = ForLoop a ...
| WhileLoop ...parse :: String -> [Statement a]desugar :: Statement () -> Statement Void

A Statement Void can never be constructed with a ForLoop but a WhileLoop can. So a never ends up holding data but it lets us reuse the data type safely.