Associated Types
See ExtensionDescriptionHowto for information on how to write these extension descriptions. Please add any new extensions to the list of HaskellExtensions.
Brief Explanation
Associated types are data type and type synonym declarations in type classes. They are useful to denote type-indexed data types (i.e., generic programming) and functions over types. Applications include the typical applications of functional dependencies, but also self-optimising libraries and APIs that resemble ML module signatures.
References
- Associated Types with Class by Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow, in POPL'05.
- Associated Type Synonyms by Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones, in ICFP'05.
- phrac (Darcs repo) is a prototype implementation of HM type inference with ATs.
Pros
- Associated types are a functional alternative to FunctionalDependencies, which are actually relational. (Why use relational programming on the type level if we don't do it on the value level?)
- They avoid some problems with FDs (described in the above papers).
- They closes the gap reported in A comparative study of language support for generic programming
Cons
- Only a prototype implementation so far. We are in the process of implementing them in GHC, but that is a significant undertaking as they have to play nicely along with other extensions (e.g., GADTs) and we are after a more lightweight type-preserving translation than the one in the POPL paper. So, given requirement that all Haskell' features need to have been implemented in at least on Haskell system, it seems unlikely that we can meet the currently proposed Haskell' timeline.
- The inference algorithm may accept types with unsatisfiable constraints, deferring errors until the function is used.
- The published version of ATs does not permit constraints on associated type synonyms in superclass contexts, which are required by some monad transformer classes. In conjunction with other proposed extensions, allowing such constraints may lead to further non-termination problems.