Type Families with Class, Type Classes with Family

Abstract

Type classes and type families are key ingredients in Haskell programming. Type classes were introduced to deal with ad-hoc polymorphism, although with the introduction of functional dependencies, their use expanded to type-level programming. Type families also allow encoding type-level functions, now as rewrite rules. This paper looks at the interplay of type classes and type families, and how to deal with shortcomings in both of them. Furthermore, we show how to use families to simulate classes at the type level. However, type families alone are not enough for simulating a central feature of type classes: elaboration, that is, generating code from the derivation of a rewriting. We look at ways to solve this problem in current Haskell, and propose an extension to allow elaboration during the rewriting phase.