Algorithm W Created 2026-10-14 Updated 2026-11-05
Algorithm W infers data types for a pure lambda calculus with let polymorphism. Write , where is a type substitution and the inferred data type. Composition means applying first. The following presentation uses type schemes explicitly.[ref]
For a program identifier, take a fresh instance of its type scheme in the typing context. For , introduce fresh , infer , and return .
For an application , compute and . With fresh , let be the most general unifier of and . Return . An incompatible base data type or failed occurs check rejects the expression.
For let x = e1 in e2, first infer . Generalize exactly those type variables of not free in , producing a type scheme . Infer for under and return .
For example, let id = \x -> x in let a = id 3 in id True has a Boolean data type result. The identity function receives type scheme , then separate uses instantiate it at integer and Boolean data types. A parameter to a lambda abstraction instead has one shared monomorphic type; treating that parameter like a let-bound type scheme would accept programs outside this type system.
Both uses of x in this definition have the same monomorphic type within the body. Write x :: u -> v. The inner application x z forces z :: u and has type v; the outer application x (x z) forces v = u. Thus x :: u -> u. Finally, x (x z) is applied to y, so u must itself be a function type, say a -> b. This gives
f :: ((a -> b) -> a -> b) -> a -> (a -> b) -> b
f x y z = x (x z) y
The principal type is therefore
The argument x transforms a function into another function of the same type. The body transforms z twice, then applies the resulting function to y; no recursive type equation is required.