International Conference on Functional Programming Poster Session
International Conference on Function Programming edition:13 location:Victoria, Canada date:22-24 September 2008
Haskell has a rich type system with various complementary, interacting and overlapping features. In particular we think of the established type classes, with several extensions: multiple parameters, functional dependencies,...
In a recent proposal, a new feature is added to the Haskell language: type-level functions, or type families in GHC.
This multitude of type-level features is a blessing for programmers. A well-chosen combination of features allows the accurate expression of many problem domain semantics.
However, the plethora of features is also a nightmare for Haskell compiler writers, who have to implement and maintain all these features. For instance, GHC's core type checking modules for type classes and type families comprise
approximately 3,1 kloc and 1,2 kloc, which is understood by very few people.
Currently, no other Haskell system has managed to provide the same type class functionality as GHC.
The contributions of this work aim at reducing the implementation complexity of two Haskell type system features, type classes and type families:
* We reduce the type checking problem of type classes to a type checking problem of type functions.
* We propose a small extension of the current type checking algorithm for type functions to cope with the above mapping.
* We sketch how to deal with evidence for both cases, dictionaries for type classes and coercions for type families.
* Our approach lifts a current restriction of type classes: it allows instance contexts to be extracted from dictionaries.
Published in Technical Report 640, Department of Computer Science, Rutgers University, Piscataway, NJ 08854, USA, pp. 14-15.