Dependency-style Generic Haskell

Generic Haskell is an extension of Haskell that supports the construction of generic programs. During the development of several applications, such as an XML editor and compressor, we encountered a number of limitations of the existing (Classic) Generic Haskell language, as implemented by the current Generic Haskell compiler. Specifically, generic definitions become disproportionately more difficult to write as their complexity increases, such as when one generic function uses another, because the recursion is implicit in generic definitions. In the current implementation, writing such functions suffers from the burden of a large administrative overhead and is at times counter-intuitive. Furthermore, the absence of type checking in the current implementation can make Generic Haskell hard to use. In this paper we develop the foundations of Dependency-style Generic Haskell which addresses the above problems, shifting the burden from the programmer to the compiler. These foundations consist of a full type system for Dependency-style Generic Haskell's core language and appropriate reduction rules. The type system enables the programmer to write generic functions in a more natural style, taking care of the dependency details which were previously the programmer's responsibility.status: publishe