Generic programming for indexed datatypes
- 18 September 2011
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the seventh ACM SIGPLAN workshop on Generic programming - WGP '11
Abstract
An indexed datatype is a type that uses a parameter as a type-level tag; a typical example is the type of vectors, which are indexed over a type-level natural number encoding their length. Since the introduction of generalised algebraic datatypes, indexed datatypes have become commonplace in Haskell. Values of indexed datatypes are often more involved than values of plain datatypes, and programmers would benefit from having generic programs on indexed datatypes. However, no generic programming library adequately supports them, leaving programmers with the tedious task of writing repetitive code. We show how to encode indexed datatypes in a generic programming library with type families and type-level representations in Haskell. Our approach can also be used in similar libraries, and is fully backwards-compatible. We show not only how to encode indexed datatypes generically, but also how to instantiate generic functions on indexed datatypes. Furthermore, all generic representations and instances are generated automatically, making life easier for users.Keywords
This publication has 16 references indexed in Scilit:
- A lightweight approach to datatype-generic rewritingJournal of Functional Programming, 2010
- Enumerating Well-Typed Terms GenericallyLecture Notes in Computer Science, 2010
- Generic programming with fixed points for mutually recursive datatypesPublished by Association for Computing Machinery (ACM) ,2009
- Unfolding Abstract DatatypesLecture Notes in Computer Science, 2008
- Foundations for structured programming with GADTsPublished by Association for Computing Machinery (ACM) ,2008
- Generic Programming in ΩmegaLecture Notes in Computer Science, 2007
- Datatype-Generic ProgrammingLecture Notes in Computer Science, 2007
- “Scrap Your Boilerplate” ReloadedLecture Notes in Computer Science, 2006
- Template meta-programming for HaskellPublished by Association for Computing Machinery (ACM) ,2002
- Polytypic values possess polykinded typesScience of Computer Programming, 2002