List (abstract Data Type) - Abstract Definition

Abstract Definition

The abstract list type L with elements of some type E (a monomorphic list) is defined by the following functions:

nil: → L

cons: E × L → L

first: L → E

rest: L → L

with the axioms

first (cons (e, l)) = e

rest (cons (e, l)) = l

for any element e and any list l. It is implicit that

cons (e, l) ≠ l

cons (e, l) ≠ e

cons (e₁, l₁) = cons (e₂, l₂) if e₁ = e₂ and l₁ = l₂

Note that first (nil ) and rest (nil ) are not defined.

These axioms are equivalent to those of the abstract stack data type.

In type theory, the above definition is more simply regarded as an inductive type defined in terms of constructors: nil and cons. In algebraic terms, this can be represented as the transformation 1 + E × L → L. first and rest are then obtained by pattern matching on the cons constructor and separately handling the nil case.