A Lightweight Approach to Datatype-Generic Rewriting

Previous implementations of generic rewriting libraries have a number of limitations: they require the user to either adapt the datatype on which rewriting is applied, or the rewriting rules are specified as functions, which makes it hard or impossible to docu-ment, test, and analyse them. We describe a library that demon-strates how to overcome these limitations by defining rules in terms of datatypes, and show how to use a type-indexed datatype to automatically extend a datatype for syntax trees with a case for metavariables. We then show how rewrite rules can be imple-mented without any knowledge of how the datatype is extended with metavariables. We use Haskell, extended with associated type synonyms, to implement both type-indexed datatypes and generic functions. We analyse the performance of our library and compare it with other approaches to generic rewriting