A treatment of collection data as constructor algebras

Abstract

This paper gives algebraic definitions of various types of nested variable-length “collections” of elements, usable as data structures. First of all, however, the paper introduces constructor algebras through an integer sequences data type. It then begins with the fundamental CONS algebra of N-tuples and a variant with “negative" elements, complementing it and subsequent homogeneous algebras by heterogeneous ones. For such list algebras, the paper postulates axioms embodying the three “basic properties“ [Commutativity‚ Idempotence, Associativity], and uses these to define the remaining seven "basic collections" [strings‚ communes, acommunes, bags, abags, sets, heaps]. Proceeding to ”non-basic collections", it then introduces "adsorption" properties [”complementary" to absorption], which are characteristic for graphs, and postulates them as axioms in algebras of ordinary graphs and of directed recursive labelnode hypergraphs [DRLHs]. Finally, it defines the property of "Similpotence" [“weaker” than Idempotence] and postulates it for DRLHs with contact labelnodes, as applied in knowledge representation.