Hindley-Milner type inference with constraints

Algorithm W is the best known algorithm for implementing Hindley-Milner type inference. But it is a bit complicated as it intermingles two separate processes: constraint generation and solving.

There is an alternative approach based on constraints generation. In this approach, constraints are collected by bottom-up traversal, and then solved independently. Heeren’s Generalizing Hindley-Milner Type Inference Algorithms paper describes the algorithm in details.

Here’s my implementation of Heeren’s algorithm. I forked Stephen Diehls’s Poly and modified the type checker to use the Heeren’s algorithm.