| doi:10.2201/NiiPi.2013.10.5 |
| Modularising inductive families |
| Hsiang-Shang KO1 and Jeremy GIBBONS2 |
| 1,2Department of Computer Science, University of Oxford |
(Received: May 10,2012)
(Revised: October 16,2012)
(Accepted: December 17,2012) |
Abstract:
Dependently typed programmers are encouraged to use inductive families to integrate constraints with data construction. Different constraints are used in different contexts, leading to different versions of datatypes for the same data structure. For example, sequences might be constrained by length or by an ordering on elements, giving rise to different datatypes “vectors” and “sorted lists” for the same underlying data structure of sequences. Modular implementation of common operations for these structurally similar datatypes has been a longstanding problem. We propose a datatype-generic solution, in which we axiomatise a family of isomorphisms between datatypes and their more refined versions as datatype refinements, and show that McBride's ornaments can be translated into such refinements. With the ornament-induced refinements, relevant properties of the operations can be separately proven for each constraint, and after the programmer selects several constraints to impose on a basic datatype and synthesises a new datatype incorporating those constraints, the operations can be routinely upgraded to work with the synthesised datatype.
|
Keywords:
Dependently typed programming, inductive families, datatype-generic programming, modularity
|
|
|
| PDF(619KB) | References |
National Institute of Informatics is a member of CrossRef.
|
