In computer science, a set is an abstract data type that can store distinct values, without any particular order. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set. Some set data structures are designed for static or frozen sets that do not change after they are constructed. Static sets allow only query operations on their elements — such as checking whether a given value is in the set, or enumerating the values in some arbitrary order. Other variants, called dynamic or mutable sets, allow also the insertion and deletion of elements from the set. A multiset is a special kind of set in which an element can appear multiple times in the set.
Type theory In type theory, sets are generally identified with their indicator function (characteristic function): accordingly, a set of values of type A {\displaystyle A} may be denoted by 2 A {\displaystyle 2^{A}} or P ( A ) {\displaystyle {\mathcal {P}}(A)} . (Subtypes and subsets may be modeled by refinement types, and quotient sets may be replaced by setoids.) The characteristic function F {\displaystyle F} of a set S {\displaystyle S} is defined as:
F ( x ) = { 1 , if x ∈ S 0 , if x ∉ S {\displaystyle F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases}}}
In theory, many other abstract data structures can be viewed as set structures with additional operations and/or additional axioms imposed on the standard operations. For example, an abstract heap can be viewed as a set structure with a min(S) operation that returns the element of smallest value.
Operations
Core set-theoretical operations One may define the operations of the algebra of sets:
union(S,T): returns the union of sets S and T. intersection(S,T): returns the intersection of sets S and T. difference(S,T): returns the difference of sets S and T. subset(S,T): a predicate that tests whether the set S is a subset of set T.
Static sets Typical operations that may be provided by a static set structure S are:
is_element_of(x,S): checks whether the value x is in the set S. is_empty(S): checks whether the set S is empty. size(S) or cardinality(S): returns the number of elements in S. iterate(S): returns a function that returns one more value of S at each call, in some arbitrary order. enumerate(S): returns a list containing the elements of S in some arbitrary order. build(x1,x2,…,xn,): creates a set structure with values x1,x2,...,xn. create_from(collection): creates a new set structure containing all the elements of the given collection or all the elements returned by the given iterator.
Dynamic sets Dynamic set structures typically add:
create(): creates a new, initially empty set structure. create_with_capacity(n): creates a new set structure, initially empty but capable of holding up to n elements. add(S,x): adds the element x to S, if it is not present already. remove(S, x): removes the element x from S, if it is present. capacity(S): returns the maximum number of values that S can hold. Some set structures may allow only some of these operations. The cost of each operation will depend on the implementation, and possibly also on the particular values stored in the set, and the order in which they are inserted.
Additional operations There are many other operations that can (in principle) be defined in terms of the above, such as:
pop(S): returns an arbitrary element of S, deleting it from S. pick(S): returns an arbitrary element of S. Functionally, the mutator pop can be interpreted as the pair of selectors (pick, rest), where rest returns the set consisting of all elements except for the arbitrary element. Can be interpreted in terms of iterate. map(F,S): returns the set of distinct values resulting from applying function F to each element of S. filter(P,S): returns the subset containing all elements of S that satisfy a given predicate P. fold(A0,F,S): returns the value A|S| after applying Ai+1 := F(Ai, e) for each element e of S, for some binary operation F. F must be associative and commutative for this to be well-defined. clear(S): delete all elements of S. equal(S1', S2'): checks whether the two given sets are equal (i.e. contain all and only the same elements). hash(S): returns a hash value for the static set S such that if equal(S1, S2) then hash(S1) = hash(S2) Other operations can be defined for sets with elements of a special type:
sum(S): returns the sum of all elements of S for some definition of "sum". For example, over integers or reals, it may be defined as fold(0, add, S). collapse(S): given a set of sets, return the union. For example, collapse({{1}, {2, 3}}) == {1, 2, 3}. May be considered a kind of sum. flatten(S): given a set consisting of sets and atomic elements (elements that are not sets), returns a set whose elements are the atomic elements of the original top-level set or elements of the sets it contains. In other words, remove a level of nesting – like collapse, but allow atoms. This can be done a single time, or recursively flattening to obtain a set of only atomic elements. For example, flatten({1, {2, 3}}) == {1, 2, 3}. nearest(S,x): returns the element of S that is closest in value to x (by some metric). min(S), max(S): returns the minimum/maximum element of S.
… excerpt ends here. Continue reading the full article.
