Questions: Dependent Type Theory

Question 1

What can dependent types express that simple types (like those in Haskell or Java) cannot?

• A. Dependent types can express recursive data structures
• B. Dependent types can express properties that relate values to types, such as 'a list of length n' or 'a sorted array,' embedding specifications into the type itself so that type-checking enforces correctness
• C. Dependent types can express higher-order functions
• D. Dependent types can express polymorphism

Answer: (B)

Simple type systems can express 'this is a list of integers' but not 'this is a list of exactly 5 integers' or 'this is a sorted list.' Dependent types allow types to mention values: Vec(Int, 5) is a type that depends on the value 5. A function append : Vec(A, n) -> Vec(A, m) -> Vec(A, n+m) has a return type that computes from the input lengths, making it a type error to return a vector of the wrong length. This moves invariants from runtime checks or comments into the type system where they are enforced at compile time.

Question 2

In dependent type theory, the type Vec(A, 0) (a vector of zero elements) has exactly one inhabitant: the empty vector nil.

• T. True
• F. False

Answer: True

Vec(A, n) is typically defined as an inductive type with two constructors: nil : Vec(A, 0) and cons : A -> Vec(A, n) -> Vec(A, n+1). Since only nil produces a Vec(A, 0), the type has exactly one inhabitant. This illustrates how dependent types encode precise invariants: the type determines the shape of the data. A function receiving Vec(A, 0) knows statically that it is the empty vector — no runtime check is needed.

Question 3

Explain the Pi type (x : A) -> B(x) and how it generalizes both ordinary function types and universal quantification.

Model answer: The Pi type (x : A) -> B(x) is a function type where the return type B(x) can depend on the input value x. When B does not actually depend on x, it reduces to the ordinary function type A -> B. Under Curry-Howard, it corresponds to universal quantification: 'for all x : A, B(x).' A value of this type is a function that, given any x of type A, produces a value of type B(x) — simultaneously a program (a function) and a proof (of the universal statement).

This generalization is what makes dependent type theory so powerful. Ordinary polymorphism (forall a. a -> a) is a special case where the type parameter is a type, not a value. Dependent types allow the parameter to be any value: a natural number, a list, a proof. The function head : (n : Nat) -> Vec(A, n+1) -> A takes a natural number n (which it may not even use computationally) and a non-empty vector, returning an element. The type-level computation n+1 guarantees the vector is non-empty, making a runtime bounds check unnecessary.