Towards a Categorical Foundation for Generic Programming

Journal article

Generic Haskell is an extension of Haskell that supports datatypegeneric 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. Copyright © 2011 ACM.

Authors: Hinze, R; Wu, N; ACM

• Publication status: Published
• Journal: WGP 11: PROCEEDINGS OF THE 2011 ACM SIGPLAN WORKSHOP ON GENERIC PROGRAMMING
• Pages: 47-58
• Publication date: 2011-01-01
• DOI: 10.1145/2036918.2036926
• Language: English
• Keywords: category theory; comma category; Generic programming; slice category