As promised, here is my suggestion for revising the collection
procedures. I tried to remain faithful to the original, and I tried to
avoid even minor changes. No, really! Nevertheless, I'm sure that it
will look like a big change. Therefore, let me preface my revision with
some rationales. Feel free to question or reject them -- as you've
already seen, I'm amenable to leaving things the way they are if you
have a good reason to do so.

Organization - With the new attributes like reversible, it was too
difficult to organize procedures by collection type. Instead, I list
them all by procedure type (constructor, accessor, etc.) with a "defined
for:" clause below each usage example. I think I correctly specified all
of the interfaces, but please double-check them if you decide to use
this.

Dictionaries - I generalized the collection-building procedures to work
well with dictionaries. For example, *-add can now build a dictionary;
just give it a (cons key value) pair, like you do in the dictionary
constructor. Likewise, *-remove can remove a mapped value; it returns
the removed key and value as a pair. There's also a specialized
*-add-key (for convenience's sake) and *-remove-key (for necessity's
sake). I removed the *-put function, but added a note to *-set-key that
some dictionaries may permit key addition via that procedure. In other
words, the "add-or-set" operation is optional.

Removal and deletion - All remove-type procedures now return the
modified collection and the removed value. If it's a dictionary, remove
returns a key-value pair.

Set! compatible with R5RS - The original specification for *-set! was
incompatible with R5RS vector-set!, which modifies the vector in-place
and returns an unspecified value. I changed *-set! to match that, and I
changed *-set (the functional version) to return the modified collection
and the previous value.

*=? and <=?: I added question marks for consistency with functions like
string=?. I also removed the elt= argument and changed the definition so
that it was no longer necessary. I was reluctant to make this change,
but I felt that the original version just wasn't viable. The main
problem, once again, is that a single equivalence predicate just doesn't
work for dictionaries. I considered passing (cons key=? val=?) to the
procedure, but that wouldn't work for non-dictionaries. In the end, I
went with the *=? interface, partly because it makes for a trivial
implementation of string=?.

I think that's all of the major changes. Here's the revision:

PROCEDURES

Many procedures accept an optional procedure (thunk) to handle failure.
If a procedure cannot perform the requested operation (because the
collection has a fixed size, is immutable, does not permit duplicate
values, does not contain a requested value, would become unordered,
etc.), it returns the value of invoking the thunk with no arguments. The
default thunk signals an error.

CONSTRUCTORS

procedure: make-% {key<? | key=?} {val<? | val=?} => %
defined for: all collections

Constructs a new % collection. Some collections may require ordering or
equivalence functions during construction. Dictionaries may require
comparison functions for both keys and values. (Ordered collections
should derive their equivalence functions from the ordering function
whenever possible.)

procedure: % {key<? | key=?} {val<? | val=?} value ... => %
defined for: all collections

Constructs a new % collection with the values as its contents. Some
collections may require ordering or equivalence functions during
construction. Dictionaries may require comparison functions for both
keys and values. (Ordered collections should derive their equivalence
functions from the ordering function whenever possible.)

procedure: *-copy * => *
defined for: all collections

Returns a new collection of the same type as the argument with the same
contents but distinct storage. The copy is shallow; that is, it copies
values in a way that preserves object identity.

TYPE PREDICATES

procedure: collection? value => value
procedure: %? value => value
defined for: all collections

Returns a true value iff the provided value supports the interface for
the type (%) named in the predicate.

CARDINALITY OPERATORS

procedure: *-empty? collection => boolean

Returns a true value iff the collection is known to be empty. This
function should return false if it is known that there are values within
the collection, or if it is unknown whether any values exist.

procedure: *-size collection => exact integer
defined for: all collections

If the collection has a concept of size, this function returns the
number of values or mappings in the collection. If it does not, #f must
be returned. If possible, this should return the number of times
collection-fold will call the fold-function before halting.

procedure: *-count * value => exact integer
defined for: all collections

Counts the number of times value occurs in the collection, according to
the collection's equivalence function.

procedure: *-key-count * value => exact integer
defined for: dictionaries

Counts the number of times key occurs in the collection, according to
the collection's key-equivalence function.

EQUIVALENCE AND TOTAL ORDERING RELATIONS

procedure: *=? *... => boolean
defined for: all collections

Returns a true value if all collections are equal. Two collections are
equal if they have the same equivalence function (if any) and the same
*-count for each value. Dictionaries must also have the same
key-equivalence function (if any), the same *-key-count for each key,
and the same value mapped to each key. Sequences and ordered collections
must have the same ordering. When comparing types of collections with
different equality rules, use the least strict rule.

procedure: *<? *... => boolean
defined for: all collections

Returns a true value if all collections are ordered from least to
greatest, using an implementation-defined total order.

procedure: *-equivalence-function * => procedure
defined for: bags, sets, and dictionaries

Returns the value equivalence function for the collection.

procedure: *-key-equivalence-function * => procedure
defined for: dictionaries

Returns the key equivalence function for the dictionary.

procedure: *-ordering-function * => procedure
defined for: ordered bags, sets, and dictionaries

Returns the value ordering function for the collection.

procedure: *-key-ordering-function * => procedure
defined for: ordered dictionaries

Returns the key ordering function for the dictionary.

ENUMERATIONS

procedure: collection-fold collection f seed ... => seed ...
defined for: all collections

Enumerates all values in the sequence in an arbitrary order. For
sequences and ordered collections, this may be the same as *-fold-left,
or it may be the most efficient order.

procedure: *-fold-left * f seed ... => seed ...
defined for: sequences and ordered collections

Enumerates all values from left to right (least to greatest, if ordered).

procedure: *-fold-right * f seed ... => seed ...
defined for: sequences and ordered collections

Enumerates all values from right to left (greatest to least, if ordered).

procedure: *-fold-keys * f seed ... => seed ...
defined for: dictionaries

Enumerates all dictionary keys and values in an arbitrary order.

procedure: *-fold-keys-left * f seed ... => seed ...
defined for: sequential and ordered dictionaries

Enumerates all dictionary keys and values from left to right (least to
greatest, if ordered).

procedure: *-fold-keys-right * f seed ... => seed ...

Enumerates all dictionary keys and values from right to left (greatest
to least, if ordered).

procedure: *->list collection => list
defined for: all collections

Returns a newly allocated list containing the collection's values. If
the collection is a sequence or an ordered collection, the list must
contain the values in the same order as a left enumeration.

procedure: *-keys->list collection => list
defined for: dictionaries

Returns a newly allocated list containing the collection's keys. If the
dictionary is also a sequence or an ordered collection, the list must
contain the keys in the same order as a left key enumeration.

ACCESSORS

procedure: *-get * [thunk] => value
defined for: all collections

Returns an arbitrary value from a collection.

procedure: *-get-key * key [thunk] => value
defined for: dictionaries

Returns the value mapped by the given key.

procedure: *-get-left * [thunk] => value
defined for: sequences and ordered collections

Returns the leftmost value in the sequence or the least value in the
ordered collection.

procedure: *-get-right * [thunk] => value
defined for: reversible sequences and reversible ordered collections

Returns the rightmost value in the sequence or the greatest value in the
ordered collection.

procedure: *-ref * position [thunk] => value
defined for: sequences and ordered collections

Returns the value stored in the sequence in the given position, which
must be an exact integer between 0 and one less than the collection's
size. (Some sequences may extend the range of allowed positions.)

procedure: *-contains? * value => boolean
defined for: bags, sets, and dictionaries

Returns a true value if the collection contains any instances of the
requested value.

VALUE MUTATORS

procedure: *-set * position new-value [thunk] => * value
procedure: *-set! * position new-value [thunk] => unspecified
defined for: sequences and ordered collections

Replaces the value stored in the sequence in the given position, which
must be an exact integer between 0 and one less than the collection's
size. (Some sequences may extend the range of allowed positions.)

The *-set procedure returns two values: the modified collection and the
position's previous value. The *-set! procedure modifies the original
collection destructively and returns an unspecified value.

procedure: *-set-key * key new-value [thunk] => * value
procedure: *-set-key! * key new-value [thunk] => unspecified
defined for: sequences and ordered collections

Replaces the value mapped to the key, which must already exist.

The *-set-key procedure returns two values: the modified collection and
the key's previous mapped value. The *-set-key! procedure modifies the
original collection destructively and returns an unspecified value.

procedure: *-update * position f [thunk] => *
procedure: *-update! * position f [thunk] => unspecified
defined for: sequences and ordered collections

Updates the value stored in the sequence in the given position to the
result of applying the one-argument function f to the previous value.
(An update may be more efficient than the equivalent get-f-set
expression, and it may permit atomic or thread-safe operation.)

The *-update procedure returns the modified collection. The *-update!
procedure modifies the original collection and returns an unspecified
value.

procedure: *-update-key * key f [thunk] => *
procedure: *-update-key! * key f [thunk] => unspecified
defined for: sequences and ordered collections

Updates the value mapped by key to the result of applying the
one-argument function f to the previous value. (An update may be more
efficient than the equivalent get-f-set expression, and it may permit
atomic or thread-safe operation.)

The *-update-key procedure returns the modified collection. The
*-update-key! procedure modifies the original collection and returns an
unspecified value.

COLLECTION MUTATORS

When adding or inserting a value into a dictionary, the new value must
be a key-value pair, unless the procedure is specifically defined for
dictionaries. Likewise, when removing or deleting a dictionary value,
the returned value is a key-value pair. A key-value pair is a Scheme
pair whose car is the key and whose cdr is the mapped value:
(cons key value).

procedure: *-clear[!] * [thunk] => *
defined for: all collections

Returns an empty collection of the same type as the argument.

procedure: *-add[!] * new-value [thunk] => *
defined for: all collections

Returns a collection of the same type with the new value added.

procedure: *-add-each[!] * source-collection [thunk] => *
defined for: all collections

As *-add, except that it adds each of the values in the source
collection. If the source collection contains duplicate values, it adds
each duplicate individually. If the destination collection is a
dictionary, the source must provide key-value pairs.

procedure: *-add-key[!] * new-key mapped-value [thunk] => *
defined for: dictionaries

Returns a collection of the same type with the new key mapped to the
given value.

procedure: *-remove[!] * value [thunk] => * value
defined for: all collections except those with fixed size

Removes a single instance of the given value. Returns the modified
collection and the removed value.

procedure: *-remove-every[!] * value => * list
defined for: all collections

Removes every instance of the given value. Returns the modified
collection and the removed value. Note: If the collection contains no
matching values, the procedure does not invoke the failure thunk; it
returns (values * '()).

procedure: *-remove-each-from[!] * source-collection [thunk] => % list
procedure: *-remove-every-from[!] * source-collection [thunk] => % list
defined for: all collections

As *-remove and *-remove-every, repeated for each value in the source
collection. If the source collection has duplicate values, the
*-remove-each-from procedure will remove those values multiple times.
Duplicate values have no effect on the *-remove-every-from procedure.

procedure: *-remove-left[!] * [thunk] => * value
defined for: flexible sequences and ordered collections

Removes the leftmost value in the sequence or the least value in the
ordered collection. Returns the updated collection and the value
removed.

procedure: *-remove-right[!] * [thunk] => * value
defined for: reversible sequences and reversible ordered collections

Removes the rightmost value in the sequence or the greatest value in the
ordered collection. Returns the updated collection and the value
removed.

procedure: *-remove-key[!] * key [thunk] => * pair
defined for: dictionaries

Removes a single mapping with the given key. Returns the modified
dictionary and the removed key-value pair.

procedure: *-remove-every-key[!] * key [thunk] => * list
defined for: dictionaries

Removes every mapping with the given key. Returns the modified
dictionary and a list of the removed key-value pairs. Like
*-remove-every, this procedure returns an empty list instead of invoking
the failure thunk.

procedure: *-remove-each-key-from[!] * source [thunk] => * list
procedure: *-remove-every-key-from[!] * source [thunk] => * list
defined for: dictionaries

As *-remove-key and *-remove every-key, except that they remove each key
found in the source collection. If the source collection is another
dictionary, use its keys as the source; otherwise, use the source
collection's values. Examples:

    (dictionary-remove-every-key-from dict1 dict2)
    Removes every key from dict1 that is also a key of dict2.

    (dictionary-remove-every-key-from my-dict my-bag)
    Removes every key from my-dict that is a value of my-bag.

    (dictionary-remove-every-key-from my-dict '(hello goodbye))
    Removes the mappings keyed to 'hello and 'goodbye.

These procedures return two values: The modified dictionary and a list
of key-value pairs.

procedure: *-insert[!] * position new-value [thunk] => *
defined for: flexible sequences

Returns a collection of the same type with the new value inserted before
the given position, increasing the collection's size by one. If the
position is not equal to the collection's initial size, the procedure
will shift all previous values right by one, starting at the insertion
point.

procedure: *-insert-left * new-value [thunk] => *
defined for: flexible sequences

As *-insert, except that it inserts the new value at position 0.

procedure: *-insert-right * new-value [thunk] => *
defined for: reversible sequences

As *-insert, except that it inserts the new value at the end of the
sequence.

procedure: *-delete[!] * n [thunk] => * value
defined for: flexible sequences and ordered collections

Deletes the nth position in the collection (which may shift subsequent
values to the left). Returns the resulting collection and the value at
the deleted position. The position must be an exact integer within the
collection's range.

procedure: *-delete-left * [thunk] => *
defined for: flexible sequences and ordered collections

As *-delete, except that it deletes the value at position 0.

procedure: *-delete-right * [thunk] => *
defined for: reversible sequences and reversible ordered collections

As *-delete, except that it deletes the value at the end of the
sequence.

SET OPERATIONS

procedure: *-union[!] * ... => *
defined for: sets

Returns the set union of one or more sets. The resulting set contains
the values of all input sets.

procedure: *-intersection[!] * ... => *
defined for: sets

Returns the set intersection of one or more sets. The resulting set
contains the values common to all input sets.

procedure: *-difference[!] * ... => *
defined for: sets

Returns the set difference between the first set and the union of all
subsequent sets. The resulting set contains the values of the first set
which appear in no subsequent set. Returns an empty set if given no
arguments.
--
Bradd W. Szonye
http://www.szonye.com/bradd