I've been fiddling around with the Elm compiler, which is written in Haskell.
I'd like to start implementing some optimizations for it, and part of this involves traversing the AST and adding "annotation" to certain nodes, such as tail-calls, etc.
I know I can use SYB or uniplate to do the traversal, but I'm wondering if there's a boilerplate-free way to deal with the types.
So, suppose we have a bunch of algebraic types for our AST:
data Expr = PlusExpr Expr Expr ...
data Def = TypeAlias String [String] Type ...
If I were writing the boilerplate, I'd make new types like this:
data AnnotatedExpr = PlusExpr Expr Expr [Annotation] ...
data AnnotatedDef = TypeAlias String [String] Type [Annotation] ...
This is a lot of boilderplate to write, and it seems like good practice to avoid this.
I could write something like this:
Data AnnotationTree = Leaf [Annotation]
| Internal [AnnotationTree] [Annotation]
Then I'd just have an annotation tree running parallel to the AST. But there is no guarantee that these trees will have the same structure, so we lose type safety.
So I'm wondering, is there an elegant/recommended solution to avoid boilerplate but still annotate a tree in a type-safe way? To replace each node with an equivalent one, plus a list of annotations which will be used in compilation later?
If you leave the recursion in your data type open you end up suffering an extra constructor everywhere, but can layer in annotations freely without changing most of your skeletal tree.
This style is much easier when you can write most of your computations as
Hutton
-algebras since they will compose better.What's also nice is that if you don't mind letting some amount of binding live in the Haskell level (such as in a middling-deep eDSL) then the
Free Hutton
monad is great for building ASTs and theCofree Hutton
comonad is essentially whatAnnotated
is.Here's a way to build annotations from the bottom up.
such that with the appropriate
Show
andNum
instancesAnd here's how you can strip them
See here for a description of how you might achieve this kind of AST work with mutually recursive ADTs, insured by Gallais' comment below.