Type Inference for Parametric Type Classes

Kund Chen, Martin Odersky, Paul Hudak

Research Report YALEU/DCS/RR-900
Yale University, Department of Computer Science
June 1992

Haskell's type classes permit the definition of overloaded operators
in a rigorous and (fairly) general manner that integrates well with
the underlying Hindley-Milner type system. As a result, operators that
are monomorphic in other typed languages can be given a more general
type.  Most notably missing, however, are overloaded functions for
data selection and construction. Such overloaded functions are quite
useful, but the current Haskell type system is not expressive enough
to support them.

We introduce the notion of parametric type classes** as a significant
generalization of Haskell's type classes. A parametric type class is a
class that has type parameters in addition to the placeholder variable
which is always present in a class declaration. Haskell's type classes
are special instances of parametric type classes with just a
placeholder but no parameters.  We show that this generalization is
essential to represent container classes with overloaded data
constructor and selector operations. Furthermore, through a simple
encoding scheme, we show that parametric type classes are able to
capture the notion of ``type constructor variables'', thus permitting
the definition of overloaded operators such as map.

The underlying type system supporting our proposed generalization is
an extension of Hindley-Milner type system with parametric type
classes.  The range of type variables are bounded by constraints.
Rules for satisfiability and entailment of these constraints are given
by a context-constrained instance theory that is separate from the
inference rules of the type system. The decoupling of the instance
theory from the type inference system makes our system more modular
than previous work. We prove that the resulting type system is
decidable, and provide an effective type inference algorithm to
compute the principal types for well-typed expressions.

**This is an expanded version of our LFP paper ``Parametric Type
Classes''.