Practical type inference for arbitrary-rank types
Open accessThe DOI matches its Crossref record.
Abstract
Haskell's popularity has driven the need for ever more expressive type system features, most of which threaten the decidability and practicality of Damas-Milner type inference. One such feature is the ability to write functions with higher-rank types – that is, functions that take polymorphic functions as their arguments. Complete type inference is known to be undecidable for higher-rank (impredicative) type systems, but in practice programmers are more than willing to add type annotations to guide the type inference engine, and to document their code. However, the choice of just what annotations are required, and what changes are required in the type system and its inference algorithm, has been an ongoing topic of research. We take as our starting point a λ-calculus proposed by Odersky and Läufer. Their system supports arbitrary-rank polymorphism through the exploitation of type annotations on λ-bound arguments and arbitrary sub-terms. Though elegant, and more convenient than some other proposals, Odersky and Läufer's system requires many annotations. We show how to use local type inference (invented by Pierce and Turner) to greatly reduce the annotation burden, to the point where higher-rank types become eminently usable. Higher-rank types have a very modest impact on type inference. We substantiate this claim in a very concrete way, by presenting a complete type-inference engine, written in Haskell, for a traditional Damas-Milner type system, and then showing how to extend it for higher-rank types. We write the type-inference engine using a monadic framework: it turns out to be a particularly compelling example of monads in action. The paper is long, but is strongly tutorial in style. Although we use Haskell as our example source language, and our implementation language, much of our work is directly applicable to any ML-like functional language.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
A history of Haskell: being lazy with class
Hudak, P., Hughes, J., Peyton Jones, S., & Wadler, P. (2007) · Proceedings of the third ACM SIGPLAN conference on History of programming languages · doi:10.1145/1238844.1238856 · Cited by 261
HMF: simple type inference for first-class polymorphism
Leijen, D. (2008) · Proceedings of the 13th ACM SIGPLAN international conference on Functional programming · doi:10.1145/1411204.1411245 · Cited by 44
Effect handlers in Haskell, evidently
Xie, N., & Leijen, D. (2020) · Proceedings of the 13th ACM SIGPLAN International Symposium on Haskell · doi:10.1145/3406088.3409022 · Cited by 8
First class dynamic effect handlers: or, polymorphic heaps with dynamic effect handlers
Leijen, D. (2018) · Proceedings of the 3rd ACM SIGPLAN International Workshop on Type-Driven Development · doi:10.1145/3240719.3241789 · Cited by 3
Metadata
- Authors
- JONES, S. P., VYTINIOTIS, D., WEIRICH, S., & SHIELDS, M.
- Venue
- Journal of Functional Programming
- Publisher
- Cambridge University Press (CUP)
- Published
- 2007-01
- Volume
- 17
- Issue
- 1
- Pages
- 1-82
- ISSN
- 0956-7968 (ISSN-L)
- 1469-7653
- OpenAlex
- W2131916293
- Cited by
- 216
- References
- 0
- FWCI
- 21.05
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Practical type inference for arbitrary-rank types. https://app.cochat.ai/papers/10.1017/s0956796806006034
- The paper
- JONES, S. P., VYTINIOTIS, D., WEIRICH, S., & SHIELDS, M. (2007). Practical type inference for arbitrary-rank types. Journal of Functional Programming. https://doi.org/10.1017/s0956796806006034
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.