Type-indexed data types
Ralf Hinze, Johan Jeuring, Andres Löh

A polytypic function is a function that can be instantiated on many data types to obtain data type specific functionality. Examples of polytypic functions are the functions that can be derived in Haskell, such as show, read, and `=='. More advanced examples are functions for digital searching, pattern matching, unification, rewriting, and structure editing. For each of these problems, we not only have to define polytypic functionality, but also a type-indexed data type: a data type that is constructed in a generic way from an argument data type. For example, in the case of digital searching we have to define a search tree type by induction on the structure of the type of search keys. This paper shows how to define type-indexed data types, discusses several examples of type-indexed data types, and shows how to specialize type-indexed data types. The approach has been implemented in Generic Haskell, a generic programming extension of the functional language Haskell.

Paper, appeared in: Eerke A. Boiten and Bernhard Möller (editors): Proceedings of the 6th International Conference on Mathematics of Program Construction, LNCS 2386, pages 148–174, Springer-Verlag 2002.
Also available as Technical Report UU-CS-2002-011 of Utrecht University.
A journal version of this paper appeared in Science of Computer Programming, Volume 51, Issues 1–2, May 2004, Pages 117–151.

Valid XHTML 1.0! Valid CSS!

Andres Löh, 2009-06-03