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

[Merijn Verstraaten]

Hi,

So I'm playing around with using bound to define a simple AST using the bound library to deal with substitution/abstraction.

Being a lazy haskeller I figured that ASTs map nicely onto Free and that I could get all the necessary Applicative, Monad, etc. instances for free by using something like:

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.

My initial idea was to use FreeT with ((,) a) as a base monad for annotations, but I quickly realised this fails, because "((,) a)" is only a Monad if 'a' is a Monoid and there's no sensible Monoid for type information/source locations.

Then I looked around more and realised that this actually sounds a lot like Cofree. But here's where I run into problems. Bound expects the type of variables to be in the functor position of my Expr type, whereas Cofree expects the type of *annotations* to be in the functor position.

So I can't figure out an elegant way to both use bound to deal with substitution for me *and* use Cofree to deal with annotations, since there's no way to make the types line up sanely.

So my question boils down too: Has anyone done all the hard work for me already? i.e. how can I have an annotated AST with substitution *and* an easy way to modify the annotations, without writing a ton of boiler plate to deal with substitution and/or annotations?

Cheers,
Merijn
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150729/912e1c25/attachment.sig>