Generic programming with fixed points for mutually recursive datatypes
Alexey Rodriguez, Stefan Holdermans, Andres Löh, Johan Jeuring

Many datatype-generic functions need access to the recursive positions in the structure of the datatype, and therefore adopt a fixed point view on datatypes. Examples include variants of fold that traverse the data following the recursive structure, or the zipper data structure that enables navigation along the recursive positions. However, Hindley-Milner-inspired type systems with algebraic datatypes make it difficult to express fixed points for anything but regular datatypes. Many real-life examples such as abstract syntax trees are in fact systems of mutually recursive datatypes and therefore excluded. Using Haskell's GADTs and type families, we describe a technique that allows a fixed-point view for systems of mutually recursive datatypes. We demonstrate that our approach is widely applicable by giving several examples of generic functions for this view, most prominently the Zipper.

ACM DL Author-ize serviceGeneric programming with fixed points for mutually recursive datatypes
Alexey Rodriguez Yakushev, Stefan Holdermans, Andres Löh, Johan Jeuring
ICFP '09 Proceedings of the 14th ACM SIGPLAN international conference on Functional programming, 2009
Draft Paper, submitted to ICFP 2009
Old draft from 2008
multirec Haskell library based on the ideas of the paper
zipper Generic zipper based on multirec
Generated Haskell source code (This is the source code actually generated from the 2009 paper sources. It contains all the definitions the paper contains, but without extra structure. Furthermore, the generated names do not necessarily match the names used in the paper, because the paper defines multiple versions of the same identifiers. You probably want to use the multirec library.)
Haskell source code (Haskell libraries containing all the examples from the 2008 paper, but not directly generated from the paper sources. Several modules, few comments. This version used to contain the Zipper example when that was not yet released as a library on Hackage, but since it now is, the Hackage versions are preferable.)

Valid XHTML 1.0! Valid CSS!

Andres Löh, 2009-03-06