This modules exposes a type representing the fixpoint of a functor type, paired with an annotation. It exports the recursion-schemes instances for this type and a few specific utility functions.

Motivation

Suppose one has an Abstract Syntax Tree (AST) for the lambda calculus:

data Term = Var String | App Term Term | Lam String Term

Such a type can easily be used with the recursion-schemes library, but it is not always convenient to use this type. It is often the case that one wants to add extra informations to every node of an AST, such as location or type information. In this case, instead of adding those informations as an extra-field to all data constructors, one could prefer to represent terms as a record of a descriptor and the information present at every node, like so:

data TermDesc = Var String | App Term Term | Lam String Term
data Term = Term { termDesc :: TermDesc
                 , termTyp  :: Typ
                 , termLoc  :: Loc
                 , ...
                 }

This library implements this general pattern through the Annot type, representing the fixpoint of a functor type, paired with some annotation. In this setting, the above example would be represented like so:

data TermDesc r = Var String | App r r | Lam String r

data TermAnn = TermAnn { termTyp :: Typ
                       , termLoc :: Loc
                       , ...
                       }

type Term = Annot TermDesc TermAnn