Simplifying and Improving Qualified Types

Simplifying and Improving Qualified Types

Mark P. Jones, Research Report YALEU/DCS/RR-1040, Yale University, New Haven, Connecticut, USA, June 1994. (Shorter revised version, without proofs, appears in FPCA '95: Conference on Functional Programming Languages and Computer Architecture, La Jolla, CA, June 1995.)


Qualified types provide a general framework for constrained type systems, with applications including type class overloading, subtyping and record calculi. This paper presents an extended version of the type inference algorithm used in previous work, that can take account of the satisfiability of constraints to obtain more accurate principal types. The new algorithm is obtained by adding two new rules, one for simplification and one for improvement of constraint sets. In particular, it permits a better treatment for the previously troublesome multiple parameter extensions of Haskell type classes. For example, a form of parametric type classes, proposed by Chen, Hudak and Odersky, can be viewed as a special case of this work.

(Supported in part by a grant from ARPA, contract number N00014-91-J-4043.)

Available by http in pdf, PostScript, or gzipped dvi.

FPCA '95 version of paper available by http in pdf, PostScript, or gzipped dvi.