Editing Unification (computer science) (section)

=== Application: type inference ===
[[Type inference]] algorithms are typically based on unification, particularly [[Hindley–Milner type system|Hindley-Milner]] type inference which is used by the functional languages [[Haskell (programming language)|Haskell]] and [[ML (programming language)|ML]]. For example, when attempting to infer the type of the Haskell expression <code>True : ['x']</code>, the compiler will use the type <code>a -> [a] -> [a]</code> of the list construction function <code>(:)</code>, the type <code>Bool</code> of the first argument <code>True</code>, and the type <code>[Char]</code> of the second argument <code>['x']</code>. The polymorphic type variable <code>a</code> will be unified with <code>Bool</code> and the second argument <code>[a]</code> will be unified with <code>[Char]</code>. <code>a</code> cannot be both <code>Bool</code> and <code>Char</code> at the same time, therefore this expression is not correctly typed.

Like for Prolog, an algorithm for type inference can be given:

# Any type variable unifies with any type expression, and is instantiated to that expression.  A specific theory might restrict this rule with an occurs check.
# Two type constants unify only if they are the same type.
# Two type constructions unify only if they are applications of the same type constructor and all of their component types recursively unify.