This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home. For a version of this page that may be more recent, see SetsCowan in WG2's repo for R7RS-large.

Sets­Cowan

cowan
2013-05-15 22:23:22
36history
source

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 are intended to be a thin veneer over hashtables, and integer sets are a thin veneer over bytevectors. It is implementation-dependent whether an integer set packs eight values into each bytevector element or (as the reference implementation does) just one. 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.

(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 #t if the element was a member, #f if not.

(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 with equality predicate = 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 ...)

(set-intersection set1 set2 ...)

(set-difference set1 set2 ...)

(set-xor set1 set2)

Returns a newly allocated set that is the union, intersection, asymmetric difference, or symmetric difference of the sets. Asymmetric difference is extended to more than two sets by taking the difference between the first set and the union of the others. Symmetric difference is not extended beyond two sets. Elements in the result set are drawn from the first set in which they appear. It is an error if all the sets do not have the same equality predicate.

(set-union! set1 set2 ...)

(set-intersection! set1 set,,2,,'' ...)

(set-difference! set1 set2 ...)

(set-xor! set1 set2)

The same as set-union, set-intersection, set-difference, and set-xor respectively, but may destroy the set1 argument.

(set-value set element)

Returns the element of set that is equal, in the sense of the equality predicate, to element. If element is not a member of the set, it is returned.

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, bag-xor!, and bag-value are not included.

(bag-count bag element)

Returns an exact integer representing the number of times that element appears in bag.

(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

The elements of an integer set are non-negative exact integers less than the set's limit, which is specified when it is created. 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, and references to equality predicates are replaced by limits, as the equality function is always =. 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.

The procedure integer-set-value is just the identity function, so it is not provided.

(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-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-min integer-set)

(integer-set-max integer-set)

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

(integer-set-min! integer-set)

(integer-set-max! integer-set)

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

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.

This design is founded on R6RS enumerations, but with the addition of reified enumeration types along the lines suggested by R6RS Formal Comment #262. The prefix enum is used in all cases instead of using both enum and enumeration as R6RS does.

The procedure enum-set-value is just the identity function, so it is not provided.

(make-enum-type symbol-list)

Returns a newly allocated 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. In R6RS the function of this procedure is provided as part of make-enumeration.

(enum-type-symbols enum-type)

Return a newly allocated list of the symbols in enum-type in the original order.

(enum-type-index enum-type symbol)

Return an exact integer corresponding to the position of symbol in the original list that created enum-type, or #f if it was not one of those symbols. The R6RS equivalent is the procedure returned by enum-type-indexer when applied to an enum-set belonging to enum-type.

(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. The approximate R6RS equivalents are enum-set-constructor and make-enumeration.

(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. The approximate R6RS equivalent is enum-set-universe.

(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. There is no R6RS equivalent.

(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. There is no R6RS equivalent.

(enum-set-complement enum-set)

Returns a newly allocated enumeration set that is the complement of enum-set. This procedure is also in R6RS.

(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. This procedure is also in R6RS, but uses a second enum-set in place of enum-type.

Issues

  1. We should consider adding eqv? to the list of equality predicates guaranteed valid. For some bizarre reason, SRFI 69 does not support it.
  1. R6RS provides define-enumeration to help set up enum-types. Is this worth having? Possible syntax is:

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

This would bind <type-name> to the enum-type, and constructor to a curried version of make-enum-set that already knows what type to use.

  1. Should there be a mechanism to convert between integer sets and integers as bitvectors, as defined in SRFI 33, SRFI 60, and R6RS?
  1. Currently you can convert one set type to another via lists. Are conversions directly through sets (or bags) useful enough to justify enlarging the SRFI? What about direct conversions between other types?
  1. How about set-intern, which is like set-value but adds the element to the set if it's not already there?