Generics.MRSOP.AG

Attribute grammars over mutual recursive datatypes

Documentation

data AnnFix (ki :: kon -> *) (codes :: [[[Atom kon]]]) (phi :: Nat -> *) (n :: Nat)

Annotated version of Fix. This is basically the Cofree datatype, but for n-ary functors

Constructors

AnnFix (phi n) (Rep ki (AnnFix ki codes phi) (Lkup n codes))

getAnn :: AnnFix ki codes ann ix -> ann ix

annCata :: IsNat ix => (forall iy. IsNat iy => chi iy -> Rep ki phi (Lkup iy codes) -> phi iy) -> AnnFix ki codes chi ix -> phi ix

forgetAnn :: AnnFix ki codes a ix -> Fix ki codes ix

Forget the annotations

mapAnn :: IsNat ix => (forall iy. chi iy -> phi iy) -> AnnFix ki codes chi ix -> AnnFix ki codes phi ix

synthesizeAnn :: forall ki codes chi phi ix. IsNat ix => (forall iy. chi iy -> Rep ki phi (Lkup iy codes) -> phi iy) -> AnnFix ki codes chi ix -> AnnFix ki codes phi ix

Synthesized attributes

synthesize :: forall ki phi codes ix. IsNat ix => (forall iy. IsNat iy => Rep ki phi (Lkup iy codes) -> phi iy) -> Fix ki codes ix -> AnnFix ki codes phi ix

Example of using synthesize to annotate a tree with its size at every node.

sizeAlgebra :: Rep ki (Const (Sum Int)) xs -> Const (Sum Int) iy
sizeAlgebra = (Const 1 <>) . monoidAlgebra

Annotate each node with the number of subtrees

sizeGeneric' :: (IsNat ix)
             => Fix ki codes ix -> AnnFix ki codes (Const (Sum Int)) ix
sizeGeneric' = synthesize sizeAlgebra

Note how using just cata will simply count the number of nodes

sizeGeneric :: (IsNat ix)
            => Fix ki codes ix -> Const (Sum Int) ix
sizeGeneric = cata sizeAlgebra