A type inference engine tries to unify the type expression `α → β` with `Int → Bool`. What is the result?
AFailure — the arrow type constructor cannot be unified with other constructors
BThe substitution {α → Int, β → Bool}, making both expressions identical
CThe substitution {α → Bool, β → Int}, since type variables are symmetric
DSuccess with no substitution — arrow types are always compatible
Unification succeeds when two compound types share the same constructor. Both expressions use `→`, so the algorithm decomposes them: unify the left components (α with Int → yields {α → Int}) and the right components (β with Bool → yields {β → Bool}). The combined substitution {α → Int, β → Bool} makes both expressions identical: Int → Bool. Option C reverses the bindings incorrectly — the algorithm matches components positionally, not arbitrarily. Option D is wrong because the substitution is necessary, not vacuous.
Question 2 Multiple Choice
A programmer writes a function where, accidentally, the return type depends on itself — the function returns a list of its own return type. What does the unification algorithm do when it encounters the constraint unifying `α` with `List<α>`?
ASucceeds and infers the type `List<List<List<...>>>` as the return type
BFails immediately with a type error, because no finite substitution can satisfy this constraint
CSucceeds only if the list is empty, since an empty list has no elements to cause the cycle
DSkips the constraint and continues with remaining constraints in the program
The occurs check detects this case and reports a type error. When the algorithm tries to bind α to List<α>, it first checks whether α appears *inside* List<α> — it does. Binding α → List<α> would create an infinite type (List<List<List<...>>>), which is unsound. The occurs check catches this before the binding is made and reports failure. Without the occurs check, the algorithm might loop infinitely trying to expand the infinite substitution, or produce an unsound result. This is why the occurs check is not optional: it prevents a class of genuine programming errors.
Question 3 True / False
The occurs check in unification is an optional optimization — skipping it makes unification faster, and in practice, recursive types rarely arise in real programs.
TTrue
FFalse
Answer: False
The occurs check is not optional — it is a correctness requirement. Without it, unification of a variable with a term containing that variable would succeed, creating an infinite type that represents a cyclic, unbounded data structure. This leads to either infinite loops during substitution propagation or unsound type inference. While some languages deliberately omit the occurs check to allow explicitly recursive types (with special syntax), removing it silently from a standard type system produces incorrect behavior. The distinction is not about performance optimization but about soundness.
Question 4 True / False
Unifying two compound types with different constructors — for example, `List<Int>` with `Pair<Int, Bool>` — always fails, even if their component types are compatible.
TTrue
FFalse
Answer: True
Constructor mismatch is an immediate and irrecoverable failure in unification. The algorithm requires both terms to have the same top-level constructor before it can recursively unify their components. `List` and `Pair` are different type constructors — they represent structurally different types — so no substitution can make `List<Int>` identical to `Pair<Int, Bool>`. The component types (Int and Bool) are irrelevant once the constructors differ. This reflects the type system's guarantee: a list and a pair are categorically different even if they contain the same element types.
Question 5 Short Answer
Explain why the occurs check is necessary in unification and what specific error it prevents.
Think about your answer, then reveal below.
Model answer: The occurs check ensures that when binding a type variable α to a type term T, α does not appear anywhere inside T. Without this check, the algorithm could create the substitution {α → List<α>}, which represents an infinite type List<List<List<...>>> with no finite base. This infinite type is unsound: the type system cannot represent or reason about it correctly. The occurs check detects this by scanning T for any occurrence of α before making the binding; if found, it reports a type error. In practice, occurs-check violations usually signal real programming errors — a function that recursively wraps its own return type without a proper base case.
The occurs check adds a linear scan over the term being bound, which can slow unification in pathological cases. Some systems (like standard Prolog) omit it for performance, explicitly allowing infinite terms. But for type systems that must be sound, the occurs check is non-negotiable — it is the mechanism that keeps the type language finite and decidable.