• Home
• All tickets
• All wiki pages

Source for wiki SetsCowan version 15

author

cowan

comment

ipnr

74.68.121.27

name

SetsCowan

readonly

0

text

== 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, which must be consistent with `eq?`.  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 `''set,,1,,''` `''set,,2,,'' ...`)`

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 `''set,,1,,''` `''set,,2,,'' ...`)`

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 `''set,,1,,''` `''set,,2,,'' ...`)`

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

`(set-xor `''set,,1,,''` `''set,,2,,''`)`

Returns a newly allocated set that is the xor (symmetric difference) of ''set,,1,,'' and ''set,,2,,''.

`(set-union! `''set,,1,,''` `''set,,2,,'' ...`)`

Mutates ''set,,1,,'' 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! `''set,,1,,''` `set,,2,,'' ...`)`

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

`(set-difference! `''set,,1,,''` `''set,,2,,'' ...`)`

Mutates ''set,,1,,'' 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! `''set,,1,,''` `''set,,2,,''`)`

Mutates ''set,,1,,'' to a new set that is the xor (symmetric difference) of ''set,,1,,'' and ''set,,2,,''.  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''.

`(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.

time

2012-12-03 14:55:18

version

15