Exploring Generic Haskell

This thesis is an exploration -- an exploration of a language extension of the functional programming language Haskell. The extension is called Generic Haskell, albeit the name has been used to refer to different objects over the last several years: Many papers have described different proposals, features, variations, and generations of the language. One purpose of this thesis is to do away with at least part of this fuzziness: everything is described in a common notation and from a single starting point. The other purpose is to simply give a complete overview of the language: we will systematically explain the core features of Generic Haskell, and several extensions, all with motivating examples and details on how the features can be implemented. Generic programming gives the user of the programming language the ability to define functions by analysis of the structure of datatypes. Such generic functions are statically checked for type correctness. They are reusable in many contexts, and can adapt easily to changed environments, because they work for all datatypes. The thesis starts with the presentation of a simple functional core language which is gradually extended with features that allow generic programming. We show how generic programming can benefit from the concept of dependencies, which are a result of the combination and generalization of two approaches to generic functions by Ralf Hinze. Whenever the language is extended, we first motivate the additions using examples, and subsequently discuss implications for the underlying theory. In the second half of the thesis, several concepts are described that make generic programming more powerful and easier to use: generic abstraction is a simple mechanism to form new generic functions out of existing ones; type inference can help to reduce the notational burden for the programmer quite significantly, default cases allow to define several variations of one generic behaviour quickly. We discuss type-indexed datatypes, which lift the concept of generic programming to the level of types and provide the possibility to define datatypes that have an implementation based on the structure of a type argument. Multiple views on datatypes allow the definition of generic functions which would otherwise be difficult to define. Finally, we discuss practical issues arising from the embedding into Haskell, such as dealing with type synonyms, or the module system and separate compilation. All in all, we present a complete and rich language for generic programming, which can, has been, and hopefully will be used for several interesting application