In Proceedings of The 32nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'05), pages 1-13, ACM Press, 2005.
Abstract
Haskell's type classes allow ad-hoc overloading, or type-indexing, of
functions. A natural generalisation is to allow type-indexing of
data types as well. It turns out that this idea directly supports a
powerful form of abstraction called associated types, which are
available in C++ using traits classes. Associated types are useful in many
applications, especially for self-optimising libraries that adapt their data
representations and algorithms in a type-directed manner.
In this paper, we introduce and motivate associated types as a rather
natural generalisation of Haskell's existing type classes. Formally, we
present a type system that includes a type-directed translation into an
explicitly typed target language akin to System F; the existence of this
translation ensures that the addition of associated data types to an
existing Haskell compiler only requires changes to the front end.
PostScript version (13 pages)
Proofs of Theorem 1 & 2 of the paper (PostScript) (14 pages)
This page is part of Manuel Chakravarty's WWW-stuff.