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 (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 × L → L. 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 definition, abstract and/or definition:
“What is important, then, is not that the critic should possess a correct abstract definition of beauty for the intellect, but a certain kind of temperament, the power of being deeply moved by the presence of beautiful objects.”
—Walter Pater (1839–1894)
“Rights! There are no rights whatever without corresponding duties. Look at the history of the growth of our constitution, and you will see that our ancestors never upon any occasion stated, as a ground for claiming any of their privileges, an abstract right inherent in themselves; you will nowhere in our parliamentary records find the miserable sophism of the Rights of Man.”
—Samuel Taylor Coleridge (1772–1834)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)