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 × LL
first: LE
rest: LL

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 (e1, l1) = cons (e2, l2) if e1 = e2 and l1 = l2

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 × LL. first and rest are then obtained by pattern matching on the cons constructor and separately handling the nil case.

Read more about this topic:  List (abstract Data Type)

Famous quotes containing the words abstract and/or definition:

    ... my whole existence is governed by abstract ideas.... the ideal must be preserved regardless of fact.
    Mary Corinna Putnam (1842–1906)

    Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.
    Nadine Gordimer (b. 1923)