[Haskell-cafe] Annotated ASTs, and the tension between Bound, Free, and Cofree...

[Tom Ellis]

On Wed, Jul 29, 2015 at 05:43:23PM +0200, Merijn Verstraaten wrote:
> newtype Expr a = Expr { unExpr :: Free (ExprF Expr) a }
>    deriving (Functor,Applicative,Monad,Foldable,Traversable)
> 
> data ExprF f a
>  = App (f a) (f a)
>  | Lam Type (Scope () f a)
>  | TmTrue
>  | TmFalse
>  | If (f a) (f a) (f a)
>  deriving (Eq,Ord,Show,Read,Functor,Foldable,Traversable)
> 
> Now, for an AST to be useful, it has to be annotated with things like
> source location, type info, etc.  So I started looking into how to
> accomplish this in a way where it's easy to add/modify annotations on any
> node of the AST.

If you want *some* subterms to be annotated, can you just add another
constructor to ExprF?

    | Annotation annotationType (f a)

Or if you want *every* subterm annotated then how about

    newtype Expr f a = Expr { unExpr :: Free (ExprF (Compose f Expr)) a }