wiki:SetsCowan

Version 16 (modified by cowan, 5 years ago) (diff)

--

Sets, bags, integer sets, and enumeration sets

Sets and bags (multisets) are mutable collections that can contain any Scheme object. Integer sets are mutable collections that can contain non-negative exact integers that are less than a maximum value specified when the integer set is created. Enumeration sets are mutable collections that can contain symbols chosen from a set of symbols represented by an enumeration type.

Sets and bags (multisets) are intended to be a thin veneer over hashtables, and integer sets are a thin veneer over bytevectors considered as sequences of bits. In turn, enumeration sets are a thin veneer over integer sets. Consequently, the -member?, -add!, and -remove! procedures are required to have an amortized cost of O(1).

Sets, bags, integer sets, enumeration sets, and enumeration types are mutually disjoint, and disjoint from other types of Scheme objects.

Set procedures

It is an error to operate on sets with different equality procedures.

(make-set =)

Returns a newly allocated empty set. = is the equality procedure for the set. If = is other than eq?, equal, string=?, or string-ci=?, the implementation MAY signal an error. Issue: possibly add eqv? to this list if hash tables support it.

(set = element ...)

Returns a newly allocated set with equality procedure = and containing the elements.

(set-copy set)

Returns a newly allocated set containing the elements of set, with the same equality procedure.

(set? obj)

Returns #t if obj is a set, and #f otherwise.

(set-length? set)

Returns the number of elements in set.

(set-member? set element)

Returns #t if element is a member of set and #f otherwise.

(set-add! set element)

Adds element to set unless it is already a member. Returns an unspecified value.

(set-remove! set element)

Removes element from set unless it is not a member. Returns an unspecified value.

(set-map = proc set)

Applies proc to each element of set in arbitrary order and returns a newly allocated set with the equality predicate = which contains the results of the applications.

(set-for-each proc set)

Applies proc to set in arbitrary order, discarding the returned values. Returns unspecified results.

(set-fold proc nil set)

Invokes proc on each member of set in arbitrary order, passing the result of the previous invocation as a second argument. For the first invocation, nil is used as the second argument. Returns the result of the last invocation.

(set->list set)

Returns a newly allocated list containing the members of set in unspecified order. However, repeated calls to this procedure will return a list in the same order until the set is mutated.

(list->set list)

Returns a newly allocated set containing the elements of list.

(set=? set ...)

Returns #t if each set contains the same elements.

(set<? set ...)

Returns #t if each set other than the last is a proper subset of the following set, and #f otherwise.

(set>? set ...)

Returns #t if each set other than the last is a proper superset of the following set, and #f otherwise.

(set<=? set ...)

Returns #t if each set other than the last is a subset of the following set, and #f otherwise.

(set>=? set ...)

Returns #t if each set other than the last is a superset of the following set, and #f otherwise.

(set-union set1 set2 ...)

Returns a newly allocated set that is the union of the sets. It is an error if the sets do not have the same equality predicate.

(set-intersection set1 set2 ...)

Returns a newly allocated set that is the intersection of the sets. It is an error if the sets do not have the same equality predicate.

(set-difference set1 set2 ...)

Returns a newly allocated set that is the asymmetric difference of set1 and the union of the other sets. It is an error if the sets do not have the same equality predicate.

(set-xor set1 set2)

Returns a newly allocated set that is the xor (symmetric difference) of set1 and set2.

(set-union! set1 set2 ...)

Mutates set1 to a set that is the union of the sets. It is an error if the sets do not have the same equality predicate.

(set-intersection! set1 set2 ...)

Mutates set1 to a set that is the asymmetric difference of set1 and the union of the other sets. It is an error if the sets do not have the same equality predicate.

(set-difference! set1 set2 ...)

Mutates set1 to a set that is the difference of the sets. It is an error if the sets do not have the same equality predicate.

(set-xor! set1 set2)

Mutates set1 to a new set that is the xor (symmetric difference) of set1 and set2. It is an error if the sets do not have the same equality predicate.

Bag procedures

The procedures for creating and manipulating bags are the same as those for sets, except that set is replaced by bag in their names, and that adding an element to a bag is effective even if the bag already contains the element. However, bag-xor and bag-xor! do not exist.

(bag-count bag element)

Returns an exact integer representing the number of times that element appears in bag; if it does not appear, returns 0.

(bag-increment bag element count)

(bag-decrement bag element count)

Increases or decreases the count of element in bag by the exact integer count.

Integer set procedures

Except as noted below, the procedures for creating and manipulating integer sets are the same as those for sets, except that set is replaced by integer-set in their names. Wherever a newly allocated integer set is returned, it has the same limit as the source sets. It is an error to operate on integer sets with different limits.

(make-integer-set limit)

Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to limit - 1, where limit is an exact non-negative integer. The set is empty.

(make-universal-integer-set limit)

Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to limit - 1, where limit is an exact non-negative integer. The set contains all possible elements.

(integer-set limit element ...)

Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to limit - 1. The set is initialized to contain the elements.

(list->integer-set limit list)

Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to limit - 1. The set is initialized to contain the elements of list in increasing numerical order.

(integer-set-complement integer-set)

Returns a newly allocated integer set that is the complement of integer-set.

(integer-set-complement! integer-set)

Mutates integer-set to a new set that is the complement of integer-set.

(integer-set-least integer-set)

(integer-set-most integer-set)

Returns the smallest or largest integer in integer-set, or #f if there is none.

(integer-set-least! integer-set)

(integer-set-most! integer-set)

Removes and returns the smallest or largest integer in integer-set, or #f if there is none.

(integer->integer-set limit integer )

Creates a newly allocated integer set with the specified limit initialized from the bits of integer, which must be exact, considered as a bit vector.

(integer-set->integer integer-set)

Returns the exact integer which, considered as a bit vector, is equivalent to integer-set.

Enumeration sets

Except as noted below, the procedures for creating and manipulating enumeration sets are the same as those for sets, except that set is replaced by enum-set in their names. Wherever a newly allocated enumeration set is returned, it has the same enumeration type as the source sets. It is an error to operate on enumeration sets of different types.

(make-enum-type symbol-list)

Returns an enumeration type suitable for constructing enumeration sets whose members are the symbols in symbol-list. These symbols are said to be in the enumeration type. Issue: are enumeration types the same if they have the same symbols?

(make-enum-set enum-type)

Returns a newly allocated enumeration set. The possible elements of the set are the symbols in enum-type. The set is empty.

(make-universal-enum-set enum-type)

Returns a newly allocated enumeration set. The possible elements of the set are the symbols in enum-type. The set contains all possible elements.

(enum-set enum-type element ...)

Returns a newly allocated enumeration set. The possible elements of the set are the symbols in enum-type. The set is initialized to contain the elements.

(list->enum-set enum-type list)

Returns a newly allocated enumeration set. The possible elements of the set are the symbols in enum-type. The set is initialized to contain the elements of list.

(enum-set-complement enum-set)

Returns a newly allocated enumeration set that is the complement of enum-set.

(enum-set-complement! enum-set)

Mutates enum-set to a new set that is the complement of enum-set.

(enum-set-projection enum-set enum-type)

Returns a newly allocated enumeration set of type enum-type. Its elements are the symbols belonging to enum-set, ignoring any symbols which are not in enum-type.

(define-enumeration <type-name> (<symbol> ...) <constructor>)

Defines a newly allocated enumeration type and provides macros for constructing its members and sets. It is a definition and can appear anywhere that other definitions can appear. The <symbol>s are in the enumeration type. Issue: do we need define-enumeration?

The identifier <type-name> is bound to a syntax definition which accepts a symbol as its argument and returns the symbol if it is in the enumeration type. It is a syntax error if the symbol is not in the enumeration type.

The identifier <constructor> is bound to a syntax definition which accepts symbols as its arguments and returns an enumeration set containing those symbols. It is a syntax error if any of the symbols are not in the enumeration type.

Conversions

The basic set is used as the pivot between different kinds of specialized sets. In particular, set->bag, set->integer-set, set->bag, bag->set, integer-set->set, and enum-set->set take one argument and do the obvious thing. set->integer-set takes two arguments, limit and the set. set->enum-set also takes two arguments, enum-type and the set.