• Home
• All tickets
• All wiki pages

Source for wiki SetsCowan version 39

author

cowan

comment

ipnr

108.182.78.175

name

SetsCowan

readonly

0

text

== Sets, bags, integer sets, and enumeration sets ==

''Sets'' and ''bags'' (also known as multisets) are mutable collections that can contain any Scheme object.  Sets enforce the constraint that an object can appear in them only once; bags do not.  ''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 `-delete!` 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-delete! `''set''` `''element''`)`

Deletes ''element'' from ''set'' if it is 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 `''set,,1,,''` `''set,,2,,'' ...`)`

`(set-intersection `''set,,1,,''` `''set,,2,,'' ...`)`

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

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

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

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

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

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

The same as `set-union`, `set-intersection`, `set-difference`, and `set-xor` respectively, but may destroy the ''set,,1,,'' 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''`)`

Returns and deletes 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 [http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-15.html R6RS enumerations], but with the addition of reified enumeration types along the lines suggested by [http://www.r6rs.org/formal-comments/comment-262.txt 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.

2. 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.

3. Should there be a mechanism to convert between integer sets and integers as bitvectors, as defined in SRFI 33, SRFI 60, and R6RS?

4. 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?

5. How about `set-intern`, which is like `set-value` but adds the element to the set if it's not already there?

time

2013-05-18 22:18:33

version

39