Cubist

LANGUAGE REFERENCE · CHAPTER 8

Natural numbers and inductive types

Inductive declarations, constructors, pattern matching, recursive functions and proofs, induction, and binary numbers.

Natural numbers are not built into the kernel. UNat is an ordinary inductive declaration in the module unat, which a file imports to use it, and its numerals, match and induction work as they do for any declared type.

Declaring an inductive type

An inductive declaration introduces a type and the constructors that build its values. This type has two constructors, each taking no arguments:

inductive Bool : U0 {
  false;
  true;
}

def enabled : Bool := true;

Bool : U0 says that Bool is a small type. Each constructor ends with ;; the declaration ends with }. A constructor without a written result builds the declared type. Constructor arguments go in parentheses, with their types. A recursive argument can itself have the declared type.

For example, the standard unat module contains this entire declaration:

inductive UNat : U0 {
  zero;
  succ(n : UNat);
}

zero : UNat builds zero, and succ(n) builds the successor of n : UNat. Decimal numerals abbreviate these constructors: 2 is succ(succ(zero)). UNat, zero and succ are ordinary imported names. A file imports them, with addition, multiplication and order, by import unat;; nothing is imported without being asked for. In the proof workspace, click UNat and select View source to open its declaration.

You can put your own inductive declaration in a module and import it like a def. Declarations become available in source order. If you omit the universe after :, the checker picks the least universe containing the constructor data and recursive argument domains. An explicit universe must be large enough for them. See universes for the level notation.

Parameters and constructors

A type can take parameters. Here U ranges over finite universes, and A : U is the type of the elements stored in the list:

import unat;
use unat;

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def empty_list : List(U0, UNat) := nil;
def numbers : List(U0, UNat) := cons(2, cons(3, nil));
def empty_again := typed(List(U0, UNat), nil);

List(U0, UNat) is a type. nil builds an empty list, and cons(head, tail) prepends an element. Write the universe and type arguments when applying List. The constructors take only their declared arguments; their instance is inferred from the expected type. A result annotation, a function argument type, or typed can supply it. In numbers, the expected type also reaches the nested constructors.

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def ambiguous := nil;  // Error: nil needs an expected type, to know which List(…) it builds: write typed(List(…), nil).

Here U only bounds the type of A, so an instance of List is one type at every universe: List(U0, UNat) and List(U1, UNat) are the same type, and the universe is called erased. The checker reads it from A, so a checked term does not carry it, and printed terms write it as __U, as in List(__U, UNat). To write such a term out, replace __U with a universe; the checker says so when it meets one.

A recursive occurrence uses the declaration's own parameters, as List(U, A) does in tail. Indices that change these arguments, mutually recursive declarations, and negative occurrences such as List(U, A) -> A as a constructor argument are not supported. A recursive argument may also be a function into the declared type, as in node(children : UNat -> Tree); a structural call then takes a child children(n).

A constructor can also build a path rather than a point, as the circle’s loop : base = base does, and a declaration can make its type a proposition or a set. Such higher inductive types use coordinates on paths, and come after cubical paths.

Functions by pattern matching

Use match to define what a function does at each constructor. Give the result type in the function header or with return on the match:

import unat;
use unat;

inductive Bool : U0 {
  false;
  true;
}

def negate(value : Bool) : Bool := match value {
  false => true;
  true => false;
};

def negates_true : negate(true) = false { rfl; }

def predecessor(n : UNat) := match n return UNat {
  zero => zero;
  succ(k) => k;
};

def predecessor_three : predecessor(3) = 2 { rfl; }

Each branch names a constructor and binds its arguments in their declared order. In succ(k), k is the predecessor, a value of type UNat. Branches are expressions ending in ;. Every case must be covered, and an unknown constructor is rejected.

Matching a constructor computes to its branch. Thus negate(true) computes to false and predecessor(3) to 2; rfl checks both equalities by computation. Matching an unknown variable waits until its constructor is known.

Several values and nested patterns

A match can take apart several values at once, match xs, ys { … }, with a pattern for each in every clause. A pattern is a constructor with patterns for its arguments, a variable, which names the value, or _, which ignores it. A name that is a constructor without arguments of the type matched there is that constructor, as nil in cons(x, nil). The clauses are tried in order, and the first that fits a case takes it:

import unat;
use unat;

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def shorter(xs, ys : List(U0, UNat)) : UNat := match xs, ys {
  nil, _ => 0;
  _, nil => 1;
  cons(x, rest), cons(y, more) => 2;
};

def second(xs : List(U0, UNat)) : UNat := match xs {
  cons(x, cons(y, rest)) => y;
  other => 0;
};

def second_of_two : second(cons(1, cons(7, nil))) = 7 { rfl; }

Such a match is a match on one value at a time, each clause matching what remains, so it computes as one: second takes its list apart, then the list's tail. A case no clause covers, and a clause that no case reaches, are rejected:

import unat;
use unat;

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def single(xs : List(U0, UNat)) : UNat := match xs {  // Error: The match has no case for cons(…) in the tail of xs.
  cons(x, nil) => 1;
  nil => 0;
};

def first_wins(n : UNat) : UNat := match n {
  m => 0;
  zero => 1;  // Error: This clause is never reached: the clauses before it take every case it would.
};

When the expected type mentions the matched variable, each clause is checked at its constructor, as in the match statement: in pick, the zero clause gives a Unit and the successor clause a number.

import unat;

def Picked(n : UNat) : U0 := match n {
  zero => Unit;
  succ(m) => UNat;
};

def pick(n : UNat) : Picked(n) := match n {
  zero => tt;
  succ(m) => m;
};

Structural recursion

A definition can call itself on a recursive child bound by its match. The module unat defines addition this way:

computable def add(x, y : UNat) : UNat := match x {
    zero => y;
    succ(k) => succ(add(k, y));
  };

For zero, return y. For succ(k), recursively add k and y, then take the successor. The recursive call uses the smaller child k. The same rule works on your own inductive types:

import unat;
use unat;

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def length(U < UU0, A : U, xs : List(U, A)) : UNat := match xs {
  nil => 0;
  cons(head, tail) => succ(length(U, A, tail));
};

def numbers : List(U0, UNat) := cons(2, cons(3, nil));
def length_two : length(U0, UNat, numbers) = 2 { rfl; }

Give a recursive definition a result type. Its body must be a match on one of its parameters, either a match expression or a match in a proof block. A recursive call passes a child for that parameter. Universe parameters and parameters on which the matched type depends stay the same: length keeps U and A. Other arguments can change, which allows an accumulator:

import unat;
use unat;

def count_into(n, total : UNat) : UNat := match n {
  zero => total;
  succ(k) => count_into(k, succ(total));
};

def counted : count_into(2, 3) = 5 { rfl; }

A call on the original input or on a newly constructed value does not satisfy the structural rule:

import unat;
use unat;

def growing(n : UNat) : UNat := match n {
  zero => 0;
  // Error: The recursive call of growing is not on an argument of the matched constructor: only structural recursion, as growing(m) in succ(m) => ….
  succ(k) => growing(succ(k));
};

These calls are checked as structural eliminations; arbitrary recursive equations are not admitted. The computation of a recursive definition at a constructor follows its written branch, so concrete results can be proved with rfl.

Proofs and dependent results

A proof about an inductive value is a function whose result type can depend on that value. In a proof block, match specializes the goal to each constructor, and each branch contains a proof block:

import unat;
use unat;

def add_zero(n : UNat) : n + 0 = n {
  match n {
    zero => { rfl; }
    succ(k) => { exact cong(succ, add_zero(k)); }
  }
}

The zero branch proves 0 + 0 = 0 by computation. The successor branch needs succ(k) + 0 = succ(k), which computes to succ(k + 0) = succ(k). The recursive proof add_zero(k) has type k + 0 = k; applying cong of succ to it gives the required proof. Here k is the predecessor, and add_zero(k) supplies the induction hypothesis.

A match expression can state its dependent result explicitly. Bind the matched value with as and write the family after return:

import unat;
use unat;

def add_zero(n : UNat) : n + 0 = n :=
  match n as value return value + 0 = value {
    zero => refl(0);
    succ(k) => cong(succ, add_zero(k));
  };

In match n as value return C(value), the zero branch produces C(zero) and the successor branch produces C(succ(k)). The family C is called the motive. Write it over the name bound by as, so each branch gets its own instance. This also works for dependent functions on lists and other declared types. A proof-block match reads the motive from the goal and closes that goal in every branch. Induction writes the same proofs without calling the definition: it names the result for each recursive argument instead.

Induction

A recursive definition reaches the result for a smaller value by calling itself. induction gives that result a name instead, so it needs no named function: each clause names the constructor’s fields in parentheses, then uses with to name an induction hypothesis for each recursive field, the result for that field. It works on every declared type:

import unat;
use unat;

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def length(xs : List(U0, UNat)) : UNat := induction xs return UNat {
  nil => 0;
  cons(head, tail) with ih => succ(ih);
};

def append(xs, ys : List(U0, UNat)) : List(U0, UNat) := induction xs return List(U0, UNat) {
  nil => ys;
  cons(head, tail) with rest => cons(head, rest);
};

def length_two : length(cons(4, cons(5, nil))) = 2 { rfl; }

cons has two arguments, and one of them, tail, is recursive, so its clause writes cons(head, tail) with ih: two constructor fields and a separate hypothesis, here ih : UNat, the length of tail. In append the hypothesis rest is tail appended to ys. The hypotheses come in the order of the recursive fields. Omit with to leave all hypotheses unnamed; if present, it must name exactly one per recursive field. A plain match clause does not accept with. A recursive argument that is a function, as in node(children : UNat -> Tree), has a function as its hypothesis: the result for each child. A path constructor’s clause is written as the point it covers, loop @ i => …, as in a match. When it has hypotheses, the coordinates precede them: c(fields) @ i with ih => ….

The earlier spelling, such as cons(head, tail, ih), remains accepted. Do not combine appended hypotheses with with. Printed proofs use the separate list.

When the result type depends on the value, name the value with as, as for match: in induction xs as v return C(v), the nil clause proves C(nil), and the cons clause proves C(cons(head, tail)) with the hypothesis ih : C(tail). This is a proof by induction:

import unat;

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def append(xs, ys : List(U0, UNat)) : List(U0, UNat) := induction xs return List(U0, UNat) {
  nil => ys;
  cons(head, tail) with rest => cons(head, rest);
};

def append_nil(xs : List(U0, UNat)) : append(xs, nil) = xs := induction xs as v return append(v, nil) = v {
  nil => refl(typed(List(U0, UNat), nil));
  cons(head, tail) with ih => cong(fun (rest : List(U0, UNat)) => typed(List(U0, UNat), cons(head, rest)), ih);
};

The cons clause needs append(cons(head, tail), nil) = cons(head, tail), which computes to cons(head, append(tail, nil)) = cons(head, tail); ih : append(tail, nil) = tail gives it, under cons(head, …). A clause with the wrong number of names is refused, with the numbers it accepts:

import unat;
use unat;

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def first(xs : List(U0, UNat)) : UNat := induction xs return UNat {
  nil => 0;
  cons(head) => head;  // Error: cons takes 2 constructor fields in parentheses; name its 1 induction hypothesis after with, or omit with.
};

In a proof

In a proof block, induction is a closing statement, as match is: it takes its motive from the goal, and each clause is a proof block of the goal at its constructor, with the hypotheses for the recursive arguments in its context.

import unat;

inductive List(U < UU0, A : U) : U {
  nil;
  cons(head : A, tail : List(U, A));
}

def append(xs, ys : List(U0, UNat)) : List(U0, UNat) := induction xs return List(U0, UNat) {
  nil => ys;
  cons(head, tail) with rest => cons(head, rest);
};

def append_assoc(xs, ys, zs : List(U0, UNat)) :
  append(append(xs, ys), zs) = append(xs, append(ys, zs)) {
  induction xs {
    nil => { rfl; }
    cons(head, tail) with ih => {
      // ih : append(append(tail, ys), zs) = append(tail, append(ys, zs))
      exact cong(fun (rest : List(U0, UNat)) => typed(List(U0, UNat), cons(head, rest)), ih);
    }
  }
}

Natural numbers

On natural numbers the general form reads zero => …; succ(k) with h => …;, with k the predecessor and h the hypothesis. Natural numbers also have a form of their own, which the first library uses throughout: the successor clause binds only the hypothesis, succ h, and as names the predecessor as well as the value in the motive:

import unat;
use unat;

def copy(n : UNat) := induction n return UNat {
  zero => 0;
  succ previous => succ(previous);
};

def copy_two : copy(2) = 2 {
  exact refl(2);
}

The zero branch gives the result for 0. In the successor branch, previous is the result for the predecessor, and the branch gives the result for its successor. Each branch is an expression, not a proof block; for a proof block, use the induction statement.

When the result type depends on the number, or the successor branch uses the predecessor, name the number with as. In induction n as k return C(k), the zero branch must have type C(0). In the successor branch, k : UNat is the predecessor and previous : C(k) is the induction hypothesis. The branch must produce C(succ(k)). Without as, as in copy, every branch has the one type after return, and the predecessor is unnamed. An as name that neither the return type nor the successor branch uses draws a warning:

import unat;
use unat;

def copy(n : UNat) := induction n as k return UNat {  // Warning: k is unused: the return type does not mention it and the successor clause does not use it.
  zero => 0;
  succ previous => succ(previous);
};

The motive C(k) is what makes this a proof by induction rather than just recursion. For a theorem, it is the statement at k. For example, n + 0 = n holds with the motive (k + 0) = k:

import unat;
use unat;

def add_zero(x : UNat) := induction x as k return ((k + 0) = k) {
    zero => refl(0);
    succ h => cong((fun (n : UNat) => succ(n)), h);
  };

The zero branch needs 0 + 0 = 0, which holds by computation. The successor branch has h : k + 0 = k and needs succ(k) + 0 = succ(k). That computes to succ(k + 0) = succ(k), which is cong of succ applied to h. When a statement quantifies over further variables, put them inside the motive, as in return (forall y : UNat, …), so the induction hypothesis is general enough.

The order on natural numbers

The module unat defines <= by matching both numbers at once, so that a comparison returns the type x <= y: Unit when it holds and Void when it does not. < is defined from it.

// Order, computed: 0 <= b holds, succ(a) <= 0 does not, and
// succ(a) <= succ(b) is a <= b.
computable def le(x, y : UNat) : U0 := match x, y {
    zero, _ => Unit;
    succ(a), zero => Void;
    succ(a), succ(b) => le(a, b);
  };

// Strict order: n < p is succ(n) <= p.
computable def isLt(n, p : UNat) : U0 := le(succ(n), p);

0 <= y is Unit for every y. succ(a) <= 0 is Void, and succ(a) <= succ(b) calls le again on both predecessors: a recursion on the first value taken apart, with the second taken apart too (patterns). A comparison of numerals therefore computes all the way to Unit or Void, and tt proves a true one.

With a variable, the computation stops at the variable, and a proof goes by induction:

import unat;
use unat;

// 0 <= n computes to Unit.
def zero_le(n : UNat) : 0 <= n {
  exact tt;
}

// n <= succ(n), by induction on n.
def le_succ(n : UNat) := induction n as k return (k <= succ(k)) {
  zero => tt;
  succ h => h;
};

In le_succ, the zero branch needs 0 <= 1, which is Unit. The successor branch has h : k <= succ(k) and needs succ(k) <= succ(succ(k)), which computes to k <= succ(k): exactly h. The library proves n <= n the same way, as unat_le_refl, and so n < succ(n), which computes to n <= n.

A hypothesis whose type mentions the matched number is taken at each constructor, under its own name, by a match expression as by the match statement. In le_zero, h is succ(k) <= 0 in the successor clause, which computes to Void:

import unat;
use unat;

def le_zero(n : UNat, h : n <= 0) : n = 0 := match n {
  zero => refl(0);
  succ(k) => absurd(h);
};

Binary numbers

Unary UNat is simple to reason about, but n takes n constructors. The library's bnat module declares binary numbers, which take one constructor per digit:

inductive BPositive : U0 {
  bp_one;
  bp_even(p : BPositive);
  bp_odd(p : BPositive);
}

inductive BNat : U0 {
  b_zero;
  b_positive(p : BPositive);
}

A positive number is its leading bp_one with its other digits appended, the last digit outermost: bp_even(p) is 2p and bp_odd(p) is 2p + 1. Zero is a constructor of its own, so no number has a leading zero and each has one representation. Functions on binary numbers use match and structural recursion, like functions on UNat:

import bnat_notation;
import unat;
use unat;

def positive_value(p : BPositive) : UNat := match p {
  bp_one => 1;
  bp_even(q) => 2 * positive_value(q);
  bp_odd(q) => succ(2 * positive_value(q));
};

def value(n : BNat) : UNat := match n {
  b_zero => 0;
  b_positive(p) => positive_value(p);
};

def six : value(bnat.(0b110)) = 6 { rfl; }

bnat_notation declares the notation bnat, whose literal rule reads a decimal or binary literal from its characters: bnat.(0b110) has type BNat and computes to b_positive(bp_even(bp_odd(bp_one))), and bnat.(6) to the same bits. bnat.(0b0) is b_zero. Leading zeroes do not affect the value. After 0b only digits 0 and 1 are accepted. The value is accumulated in binary as the characters are read, so no machine number and no unary magnitude holds it. These literals denote nonnegative numbers. Public Nat, from nat, is BNat, and its notation reads the same literals; unat retains structural unary numerals.

nat gives binary Nat its arithmetic, order and factorial. Arithmetic symbols are not overloaded. The radix factorial computes 10! digit by digit in base 10 and in base 2, and carries it from binary along a univalence path, without a unary expansion of 3628800.