Haskell and principal types

Abstract

This paper points out two problems which prevent Haskell from having principal types. For each problem, we discuss a program which exhibits it. The first problem has to do with type signatures and class constraints containing both generic and nongeneric type variables. The second problem is caused by the monomorphism restriction. In both cases there is an interaction between generalization and class constraints where substituting a nonvariable type for a constrained type variable makes the constraint tautological and opens up for more aggressive generalization.We also discuss how these problems can be solved by introducing quantified class constraints and strengthening the monomorphism restriction from prohibiting only the generalization of constrained type variables to prohibiting any generalization at all. We also give an inference algorithm producing principal types for the new system.