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

[Alan & Kim Zimmerman]

Have you looked at this? https://hackage.haskell.org/package/Annotations

Alan

On Wed, Jul 29, 2015 at 5:43 PM, Merijn Verstraaten <merijn at inconsistent.nl>
wrote:

> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150729/56ea8ea1/attachment.html>