Inductively Defined Lists and Proofs

In this post, we will explore an inductive data structure as a type for lists of elements. We define two recursive functions that can be applied to lists of this type; namely, an operation to append two lists and an operation to reverse a list. With these definitions, we set out to mathematically prove a number of properties that should hold for these functions by means of induction.

A list is a data structure of a collection of elements in a certain order. A list can be defined in multiple ways. One way is to define a list as being an element (the “head” of the list) followed by another list (the “tail” of the list). Inductively, this could be formalized as follows:

This means that a list l with elements of type  a is either cons x tail, with x of type  a and with tail of type list a, or l is the empty list nil. Let’s look at some example lists with elements of the whole numbers.

Note that because we have lists of integers, following our definition the list l is of type list integer.

Multiple list operations can be defined, such as append and reverse. We defined our list inductively, and so it would make sense to define these operations inductively (also known as recursively) as well. Because of our neat data structure and operations, we should then be able to prove that certain properties of the operations hold.

Let’s first define append. By appending two lists, we create a new list where the elements in the first list are followed by the elements in the second. This can easily be defined as follows:

Thus, our function append is a function that takes two parameters of type list a and returns something of type list a. We defined it in two steps: if the first list is empty (nil), we return the second list. If the first list is not empty, we create a new list with the same head as the first, and with as tail the second list appended to the tail of the first list. Note that the parentheses around nil, k, and cons head tail in the above definition are optional; I added them for clarity. Let’s append the lists [1,2,3] and [4,5]:

We want to prove that the following properties of this function hold:

With the first lemma we state that the result of appending a list and an empty list is equal to the first list. With the second lemma we state that first appending lists k and l, and then appending m to the result is equal to appending the result of appending l and m to k.

Proof of the First Lemma

Let’s prove the first lemma. We will prove that the lemma is true with induction on l.

First, consider l = nil. Thus,

Thus, for l = nil we have append l nil = l, and so the property holds.

Now, we assume that the property holds for the list tail. Thus, append tail nil = tail. Consider l = cons head tail.

As such, if the property holds for tail we have append (cons head tail) nil = cons head tail for any arbitrary head. Thus, with structural induction on l, we have shown that the first lemma holds for all finite lists.

Proof of the Second Lemma

Now, we will prove the second lemma. We will again prove this by induction.

First, consider arbitrary l and m, with k = nil.

Thus, with k = nil the property holds. Now, we assume the property holds for some list tail. Thus, append (append tail l) m = append tail (append l m). Consider k = cons head tail.

As such, if the property holds for tail we have append ((cons head tail) l) m = append (cons head tail) (append l m) for any arbitrary head. So, the property holds for cons head tail as well. We have shown, with structural induction on k, that the second lemma holds for all lists.

Reversing Lists

Now, we define a new operation; reverse.

Let’s take the reverse of the list [1,2,3]:

Now, we want to prove that the following property of our reversal and append functions hold:

This lemma states that reversing the result of appending lists l and m is equal to appending the reversals of lists m and l. We will prove this by induction on l. First, consider l = nil.

Thus, with l = nil the property holds. Now, assume the property holds for tail; thus, reverse (append tail m) = append (reverse m) (reverse tail). Consider l = cons head tail.

As such, if the property holds for tail, we have reverse (append (cons head tail) m) = append (reverse m) (reverse (cons head tail)) for any arbitrary head. Thus, the property also holds for cons head tail. So, with structural induction on l, the property holds for all lists.

Leave a Reply

Your email address will not be published. Required fields are marked *