Theorem. Next on Grammars Is Presheaf Structure
For presheaves, restricts along the strict past, as in later on presheaves. A grammar is only a family over strings, so a map into the later on grammars is extra data. It sends a parse over to parses over every proper suffix of .
Let , so that . This is the comonad for the suffix order, and presheaves are comonadic over families. The counit law forces the first component of a coalgebra to be the identity. Hence:
- a presheaf on strings under the suffix order is the same as a grammar with a map that satisfies coassociativity. Restricting to and then to must agree with restricting to directly;
- for a proposition-valued grammar (a language), coassociativity is automatic, and exists exactly when the language is closed under suffixes. For example, has one, but does not, since is empty.
LΓΆb does not need on . The fixed-point equation only restricts a global parse , and a global parse can always be restricted. In the Agda, the grammar-level IsCoalgebra record, with only the field next, is in Grammar/Later/Coalgebra.agda on the guarded branch.
On presheaves the strict downset of is represented by , because every proper suffix of is a suffix of . So predecessors simplify later to . On grammars there is no such simplification, since the factors at different suffixes are unrelated.