Map Index Random Help Topics

## Topic: set operations

topics > mathematics > Group: sets

Topic:
collection class
Topic:
database queries, joins, and relational algebra
Topic:
foreach and for all statements
Topic:
quantified repetition
Topic:
set data type
Topic:
set-oriented languages

#### Summary

Many operations have been defined on sets, usually based on mathematical usage. These include permutations, cross product, set difference, indirect product, reductions, intersection, union, membership, and powerset. An important part of set operations is defining set literals, the null set, and base types. Unordered, duplicated-element sets can be implemented as sequences. Sets with a small base-type can be implemented by a bit string whose length matches the base type's size. (cbb 5/80)

Relational databases allow information processing on sets. (cbb 1/90)

 Quote: assigning to a set is adding a member; accessing a set is removing a member [»millHD2_1986]

Subtopic: set operations

 Quote: in CPL, convert a set into a sorted list Quote: ring operations to insert, remove, copy, foreach forward/backward; no special cases for empty and one member rings [»suthIE5_1963] QuoteRef: grayJC_1973 ;;169 also set size, component type, union, intersection, difference, append QuoteRef: schwJT_1973 ;;502 npow (k,a) set of all subsets of A having k elements QuoteRef: wellMB4_1964 ;;433 set difference by all x such that x=a-b for a in A, b in B, and a-b >= 0 [others do the same on any range i.e., bounded by high and low for the set. QuoteRef: wirtN1_1971 ;;38 operations on powersets -- int, union, difference, membership QuoteRef: grayJC_1973 ;;169 permute (index-set '% set) e.g., [3 2]'%[a b c d] == [c b] QuoteRef: grayJC_1973 ;;170 indirect product of two sets: from all element is set A form a reduction in set B and check number of elements

Subtopic: aggregate operator

 Quote: aggregate operator much simpler than normal programming language; e.g., sum nectar of all flowers [»paneJF9_2002]

Subtopic: implementation

 Quote: set union, intersection, and universal qualifier can be unit-time operations on the Connection Machine [»hillWD_1985] Quote: implement lattice operations in almost constant time by encoding the lattice in binary; greatest lower bound, l.u.b., and relative complement [»aitkH1_1989]

Related Topics

Topic: collection class (11 items)
Topic: database queries, joins, and relational algebra (34 items)
Topic: foreach and for all statements (16 items)
Topic: quantified repetition (11 items)
Topic: set data type (16 items)
Topic: set-oriented languages
(20 items)

Updated barberCB 1/05