A set may be defined as a collection of objects no two of which are equal, according to some equality predicate. A mapping is a set of key-value pairs, and a bag can be understood as a mapping from the objects in the bag to the number of times in which they appear.
The roots of sets and mappings in Scheme are found in SRFI 1, which provides procedures for treating lists as sets and for treating lists of pairs as alists. (Alists themselves go back to Lisp 1.5, and the `assq`, `assv`, and `assoc` functions to R2RS.) SRFI 1 introduces the idea of "linear update" procedures:
Many procedures in this library have "pure" and "linear update" variants. A "pure" procedure has no side-effects, and in particular does not alter its arguments in any way. A "linear update" procedure is allowed -- but not required -- to side-effect its arguments in order to construct its result. "Linear update" procedures are typically given names ending with an exclamation point. [W]e do not call these procedures "destructive" -- because they aren't required to be destructive. They are potentially destructive.
What this means is that you may only apply linear-update procedures to values that you know are "dead" -- values that will never be used again in your program. This must be so, since you can't rely on the value passed to a linear-update procedure after that procedure has been called. It might be unchanged; it might be altered.
For example, SRFI-1 provides a set procedure `lset-union` that is guaranteed not to mutate any of its arguments, and a corresponding `lset-union!` that may or may not do so. Per contra, SRFI 125 provides mappings (known as hash tables) whose update operations *are* guaranteed to mutate them. It is also possible to have objects which are completely immutable, like the ilists of SRFI 116.
A third dimension orthogonal to set/bag/mapping and immutable/mutable/linear-update is the question of what procedures operating on set members or mapping keys are required by the implementation. For the definition of a set, or for the inefficient implementations provided by SRFI 1, an equality predicate suffices. More efficient implementations require either an ordering predicate or a hash function as well (a SRFI 128 comparator packages these three procedures). So we could have as many as 27 implementations of the three container types, such as immutable hash sets or linear-update ordered bags or mutable equality mappings.
What We Have
What we in fact have at present is this:
Lists as sets (SRFI 1): linear-update equality sets
Alists (SRFI 1): linear-update equality mappings
Hash tables (SRFI 69, SRFI 125, SRFI 126): mutable hash mappings
General sets (SRFI 113): linear-update ordered-or-hash sets
General bags (SRFI 113): linear-update ordered-or-hash bags
Mappings (draft SRFI 146): linear-update ordered mappings
Hashmaps (draft SRFI 146): linear-update hash mappings
Immutable sets (draft SRFI 153): immutable ordered sets
Immutable bags (draft SRFI 153): immutable ordered bags
Proposed Amendments:
What I'd like to do is to make everything linear-update with the exception of SRFI 125 (and friends) hash tables. This means that:
1) I will expand SRFI 153 to add linear-update functions.
Furthermore, I'd like to make SRFI 113 and SRFI 153 support hash and ordered sets/bags respectively. This means that:
2) I'm proposing a third post-finalization note for SRFI 113, thus:
<p><b>Post-finalization note 3</b>: Because SRFI 153
supports sets and bags created using a comparator with
an ordering predicate, implementers of this SRFI are
encouraged to make sure to support comparators that
provide a hash function but not an ordering predicate.
The sample implementation already does so.</p>
The wording may need further improvement. This change will have to be revoted by WG2 to become part of the Orange Edition.
This also means that:
3) The additional implementation of SRFI 113 provided with SRFI 146 is no longer compliant (it does not support hash-only comparators) and should be remove. It can be recycled for the implementation of SRFI 153.
4) Finally, as discussed on the SRFI 146 mailing list, the following changes Marc has already agreed to must be consummated: (a) the procedures in (srfi 146 hash) are now to be prefixed with hashmap- instead of -mapping, making it easy to use both types of container together; (b) (srfi 146 hash) is no longer optional (I am writing an implementation of it based on SRFI 125).
The results will be as follows:
Lists as sets (SRFI 1): linear-update equality sets
Alists (SRFI 1): linear-update equality mappings
Hash tables (SRFI 69, SRFI 125, SRFI 126): mutable hash mappings
General sets (SRFI 113): linear-update hash sets
General bags (SRFI 113): linear-update hash bags
Mappings (draft SRFI 146): linear-update ordered mappings
Hashmaps (draft SRFI 146): linear-update hash mappings
Ordered sets (draft SRFI 153): linear-update ordered sets
Ordered bags (draft SRFI 153): linear-update ordered bags
5) I will write a future SRFI supplementing SRFI 1 to contain more alist and list-as-set procedures, as well as alist-as-bag procedures, to put these equality-based containers on a par programmatically with the ordering-based and hash-based varieties.
The result will be a full assortment of equality-, ordering-, and hash-based lists, sets, and bags, all of them linear-update.
--
Sir, I quite agree with you, but what are we two against so many?
--George Bernard Shaw,
to a man booing at the opening of _Arms and the Man_