inferno

A library for constraint-based Hindley-Milner type inference
IN THIS PACKAGE
Module type Inferno . Signatures . OUTPUT
type 'a structure

A structure is a piece of information that the unifier attaches to a variable (or, more accurately, to an equivalence class of variables).

In some contexts, a structure represents a logical constraint that bears on a variable. A structure of type 'a structure may itself contain variables, which are represented as values of type 'a. We refer to these values as the children of this structure.

In some contexts, a structure may record not only a logical constraint, but also other kinds of meta-information, such as the unique identifier of this equivalence class, where and how it is bound (its rank; whether it is rigid or flexible; etc.).

For example, in the case of first-order unification, a structure might be an optional shallow term: that is,

  • either None, which indicates the absence of a constraint;
  • or Some term, where term is a shallow term (a term of depth 1 whose leaves are variables of type 'a), which indicates the presence of an equality constraint.
type tyvar

A representation of decoded type variables.

type ty

A representation of decoded types.

val inject : id -> tyvar

inject provides an injection of unique integer identifiers into decoded type variables.

val variable : tyvar -> ty

variable v is a representation of the type variable v as a decoded type.

val structure : ty structure -> ty

structure s turns s, a structure whose children are decoded types, into a decoded type.

val mu : tyvar -> ty -> ty

If v is a type variable and t is a decoded type, then mu v t is a representation of the recursive type mu v.t. The function mu is used only by the cyclic decoder.