Generalizing Hindley-Milner Type Inference Algorithms
Bastiaan Heeren, Jurriaan Hage, S. Doaitse Swierstra · 2002
Type inferencing according to the standard algorithms often yields uninformative error messages. Many times, this is a consequence of a bias inherent in the algorithms. The method developed here is to first collect constraints from the program, and to solve these afterwards, possibly under the influence of a heuristic. We show the soundness and completeness of our algorithm. The algorithms turn out to be deterministic instances of our method, giving the correctness for with respect to the Hindley-Milner typing rules for free. We also show that our algorithm is more flexible, because it naturally allows the generation of multiple messages.