A library for constraint-based Hindley-Milner type inference
Library inferno
Module Inferno . OccursCheck . Make


module S : sig ... end
module U : sig ... end


exception Cycle of U.variable

Cycle v is raised by the occurs check.

val new_occurs_check : ( -> bool ) -> U.variable -> unit

new_occurs_check is_young initiates a cycle detection phase. It produces a function check that can be applied to a number of roots. The function check visits the vertices that are reachable from some root and that satisfy the user-supplied predicate is_young. If a cycle is detected, then Cycle v is raised, where v is a vertex that participates in the cycle.

The function check has internal state and records the vertices that it has visited, so no vertex is visited twice: the complexity of the occurs check is linear in the size of the graph fragment that is visited.