Journal of Functional Programming

Articles

A lightweight approach to datatype-generic rewriting

THOMAS VAN NOORTa1, ALEXEY RODRIGUEZ YAKUSHEVa2, STEFAN HOLDERMANSa2, JOHAN JEURINGa3, BASTIAAN HEERENa4 and JOSÉ PEDRO MAGALHÃESa5

a1 Institute for Computing and Information Sciences, Radboud University Nijmegen, P.O. Box 9010, 6500 GL Nijmegen, The Netherlands (e-mail: thomas@cs.ru.nl)

a2 Vector Fabrics, Paradijslaan 28, 5611 KN Eindhoven, The Netherlands (e-mail: alexey@vectorfabrics.com, stefan@vectorfabrics.com)

a3 Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands and School of Computer Science, Open University of the Netherlands, P.O. Box 2960, 6401 DL Heerlen, The Netherlands (e-mail: johanj@cs.uu.nl)

a4 School of Computer Science, Open University of the Netherlands, P.O. Box 2960, 6401 DL Heerlen, The Netherlands (e-mail: bastiaan.heeren@ou.nl)

a5 Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands (e-mail: jpm@cs.uu.nl)

Abstract

Term-rewriting systems can be expressed as generic programs parameterised over the shape of the terms being rewritten. Previous implementations of generic rewriting libraries require users to either adapt the datatypes that are used to describe these terms or to specify rewrite rules as functions. These are fundamental limitations: the former implies a lot of work for the user, while the latter makes it hard if not impossible to document, test, and analyze rewrite rules. In this article, we demonstrate how to overcome these limitations by making essential use of type-indexed datatypes. Our approach is lightweight in that it is entirely expressible in Haskell with GADTs and type families and can be readily packaged for use with contemporary Haskell distributions.

(Online publication September 27 2010)