Type inference with constraints

These papers explore type inference using constraints. See also papers about GADTs and about type families.

Modular type inference with local assumptions

Modular type inference with local assumptions, Dimitrios Vytiniotis, Simon Peyton Jones, Tom Schrijvers, Martin Sulzmann. To be published by Journal of Functional Programming; camera ready copy April 2011. This epic 83-page paper brings together our work on type inference for type functions, GADTS, and the like, in a single uniform framework. See also papers on GADTs and type families.


Advanced type system features, such as GADTs, type classes, and type families, have proven to be invaluable language extensions for ensuring data invariants and program correctness. Unfortunately, they pose a tough problem for type inference when they are used as local assumptions. Local type assumptions often result in the lack of principal types and cast the generalisation of local let-bindings prohibitively difficult to implement and specify. User-declared axioms only make this situation worse. In this article, we explain the problems and -- perhaps controversially -- argue for abandoning local let-binding generalisation. We give empirical results that local let generalisation is only sporadically used by Haskell programmers.

Moving on, we present a novel constraint-based type inference approach for local type assumptions. Our system, called OutsideIn(X), is parameterised over the particular underlying constraint domain X, in the same way as HM(X). This stratification allows us to use a common metatheory and inference algorithm. OutsideIn(X) extends the constraints of X by introducing implication constraints on top. We describe the strategy for solving these implication constraints, which in turn relies on a constraint solver for X. We characterise the properties of the constraint solver for X so that the resulting algorithm only accepts programs with principal types, even when the type system specification accepts programs that do not enjoy principal types.

Going beyond the general framework we give a particular constraint solver for X = type classes + GADTs + type families, a non-trivial challenge in its own right. This constraint solver has been implemented and distributed as part of GHC 7.

Let should not be generalised

Let should not be generalised, Dimitrios Vytiniotis, Simon Peyton Jones, and Tom Schrijvers; submitted to TLDI 2010.

Abstract. From the dawn of time, all derivatives of the classic Hindley-Milner type system have supported implicit generalisation of local let-bindings. Yet, as we will show, for more sophisticated type systems implicit let-generalisation imposes a disproportionate complexity burden. Moreover, it turns out that the feature is very seldom used, so we propose to eliminate it. The payoff is a substantial simplification, both of the specification of the type system, and of its implementation.