User loginNavigation |
Parametric datatype-genericity
Parametric datatype-genericity. Jeremy Gibbons and Ross Paterson. Submitted for publication.
Datatype-generic programs are programs that are parametrized by a datatype or type functor. There are two main styles of datatype-generic programming: the Algebra of Programming approach, characterized by structured recursion operators parametrized by a shape functor, and the Generic Haskell approach, characterized by case analysis over the structure of a datatype. We show that the former enjoys a kind of parametricity, relating the behaviours of generic functions at different types; in contrast, the latter is more ad hoc, with no coherence required or provided between the various clauses of a definition. How could we have not mentioned this before? The main result of this paper is that fold is a higher-order natural transformation. This means, the authors explain, that fold is a rather special kind of datatype-generic operator, both enjoying and requiring coherence between its datatype-specific instances. We had several long discussions about the uniqueness of fold, which may serve as an introduction for those new to this sort of discussion. The tutorial on the universality of fold is, of course, on the papers page. For some reason I feel a craving for bananas... |
Browse archives
Active forum topics |
Recent comments
25 weeks 3 days ago
25 weeks 3 days ago
25 weeks 3 days ago
47 weeks 4 days ago
51 weeks 6 days ago
1 year 1 week ago
1 year 1 week ago
1 year 4 weeks ago
1 year 8 weeks ago
1 year 8 weeks ago