Skip to main content

Towards a categorical foundation for generic programming

Ralf Hinze and Nicolas Wu

Abstract

Generic Haskell is an extension of Haskell that supports datatype-generic programming. The central idea of Generic Haskell is to interpret a type by a function, the so-called instance of a generic function at that type. Since types in Haskell include parametric types such as `list of', Generic Haskell represents types by terms of the simply-typed lambda calculus. This paper puts the idea of interpreting types as functions on a firm theoretical footing, exploiting the fact that the simply-typed lambda calculus can be interpreted in a cartesian closed category. We identify a suitable target category, a subcategory of Cat, and argue that slice, coslice and comma categories are a good fit for interpreting generic functions at base types.

Address
New York‚ NY‚ USA
Book Title
Proceedings of the seventh ACM SIGPLAN workshop on Generic programming
Editor
Järvi‚ Jaakko and Mu‚ Shin−Cheng
ISBN
978−1−4503−0861−8
Location
Tokyo‚ Japan
Pages
47−58
Publisher
ACM
Series
WGP '11
Year
2011