[Hs-Generics] New paper

Johan Jeuring johanj at cs.uu.nl
Tue Jul 15 09:47:08 EDT 2008

We have just finished a paper in which we use type families and GADTs  
to do
generic programming with fixed points for mutually recursive datatypes:

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  
Examples include variants of fold that traverse the data following the  
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  
recursive datatypes. We demonstrate that our approach is widely  
applicable by
giving several examples of generic functions for this view, most  
prominently the



-- Johan

More information about the Generics mailing list