Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
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''.