Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
A Few Constructions on Constructors
| |
|
A Few Constructions on Constructors
Conor McBride1, Healfdene Goguen2 and James McKinna3
| (1) |
School of Computer Science and Information Technology, University of Nottingham, |
| (2) |
AT&T Labs, Florham Park, New Jersey, |
| (3) |
School of Computer Science, University of St Andrews, |
Abstract
We present four constructions for standard equipment which can be generated for every inductive datatype: case analysis, structural
recursion, no confusion, acyclicity. Our constructions follow a two-level approach—they require less work than the standard
techniques which inspired them [11,8]. Moreover, given a suitably heterogeneous notion of equality, they extend without difficulty
to inductive families of datatypes. These constructions are vital components of the translation from dependently typed programs
in pattern matching style [7] to the equivalent programs expressed in terms of induction principles [21] and as such play
a crucial behind-the-scenes rôle in Epigram [25].
Fulltext Preview (Small, Large)
|
|
|
|
|
|