InductiveDataTypesAndPatternMatching

See the official user manual pages on data types and pattern matching for the most up-to-date version of the information on this page.

We will begin with a very simple notion, and will then gradually introduce more and more complex classes of data types: parameterized data types, indexed families of data types ("inductive families), and inductive-recursive data types.

1. Simple inductive types
2. Parameterized inductive types
3. Inductive families
4. Inductive-recursive types

Functions can be introduced by giving a type and a definition. For instance, the polymorphic identity function can be defined by

 id : {A : Set} -> A -> A
 id x = x

Note that the implicit argument is left out in the left hand side. As in a lambda abstraction it can be given explicitly by enclosing it in curly braces:

 id : {A : Set} -> A -> A
 id {A} x = x

Datatypes are introduced by data declarations. For instance, the natural numbers can be defined by

 data Nat : Set where
   zero : Nat
   suc  : Nat -> Nat

To ensure normalisation, inductive occurrences must appear in strictly positive positions. For instance, the following datatype is not allowed:

 data Bad : Set where
   bad : (Bad -> Bad) -> Bad

since there is a negative occurrence of Bad in the argument to the constructor.

Functions over elements of a datatype can be defined using pattern matching and structural recursion. The addition function on natural numbers is defined by

 _+_ : Nat -> Nat -> Nat
 zero  + m = m
 suc n + m = suc (n + m)

The operator form can be used both in left hand sides and right hand sides as seen here.

Datatypes can be parametrised over a telescope of parameters. These are written after the name of the datatype and scope over the constructors.

 data List (A : Set) : Set where
   []   : List A
   _::_ : A -> List A -> List A

This will introduce the constructors

 []   : {A : Set} -> List A
 _::_ : {A : Set} -> A -> List A -> List A

We can also define families of datatypes. For instance, the family over natural numbers n of proofs that n is even.

 data IsEven : Nat -> Set where
   evenZ  : IsEven zero
   evenSS : (n : Nat) -> IsEven n -> IsEven (suc (suc n))

Note the difference between the left and the right side of the first :. Types appearing on the left are parameters and scope over the constructors. These have to be unchanged in the return types of the constructors. Types appearing on the right are indices which are not in scope in the constructors, and which take on arbitrary values in the constructor return types.

When pattern matching on an element of an inductive family we get information about the index. To distinguish parts of a pattern which are determined by pattern matching (the inaccessible patterns) and the parts which constitutes the actual pattern matching, the inaccessible patterns are prefixed with a dot. In For instance, we can prove that the sum of two even numbers is also even.

 even+ : (n m : Nat) -> IsEven n -> IsEven m -> IsEven (n + m)
 even+ .zero          m  evenZ        em = em
 even+ .(suc (suc n)) m (evenSS n en) em =
     evenSS (n + m) (even+ n m en em)

The proof is by recursion on the proof that n is even. Pattern matching on this proof will force the value of n and hence the patterns for n are prefixed with a dot to indicate that they are not part of the pattern matching. In this case we can make n and m implicit and write the proof as

 even+ : {n m : Nat} -> IsEven n -> IsEven m -> IsEven (n + m)
 even+  evenZ        em = em
 even+ (evenSS n en) em = evenSS _ (even+ en em)