Re:How the OCaml type checker works (2022)
by Rusky on Monday August 19, 2024 @02:48PM
(#41293635)
Paterson-Wegman and Martelli-Montanari are worst-case linear, but Algorithm J just uses the earlier almost-linear union-find approach: unification variables are represented as mutable pointers to either a) nothing, or b) another type (which may itself be the "parent" unification variable in the union-find structure). Unification is then just a recursive function over a pair of types that updates these pointers as appropriate- and often doesn't even bother with e.g. path compression.
[ Parent
| on HN ]
There are no comments on this comment yet.