2.37.1 Introduction

Sets and bags are mutually disjoint types; they are also disjoint from other types of Scheme objects.

• Sets enforce the constraint that no two elements can be the same in the sense of the set’s associated equality predicate.
• Bags are like sets, but can contain the same object more than once. However, if two elements that are the same in the sense of the equality predicate, but not in the sense of eqv?, are both included, it is not guaranteed that they will remain distinct when retrieved from the bag: if two elements in a bag are the same in the sense of the bag’s comparator, the implementation may in fact store just one of them.

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 adjoining an element to a bag is effective even if the bag already contains the element.

Constraints

The API defined by (srfi :113) imposes usage constraints:

• It is an error for any procedure to be invoked on sets or bags with distinct comparators (in the sense of eq?).
• It is an error to mutate any object while it is contained in a set or bag.
• It is an error to add an object to a set or bag which does not satisfy the type test predicate of the comparator.
• It is an error to add or remove an object from a set or a bag while iterating over it.

Linear update

The procedures of this SRFI, by default, are “pure functional”: they do not alter their parameters. However, this SRFI also defines “linear–update” procedures, all of whose names end in !. They have hybrid pure–functional/side–effecting semantics: they are allowed, but not required, to side–effect one of their parameters in order to construct their result. An implementation may legally implement these procedures as pure, side–effect–free functions, or it may implement them using side effects, depending upon the details of what is the most efficient or simple to implement in terms of the underlying representation.

It is an error to rely upon these procedures working by side effect. For example, this is not guaranteed to work:

(let* ((set1 (set 'a 'b 'c))           ; set1 = {a,b,c}.
       (set2 (set-adjoin! set1 'd)))   ; Add d to {a,b,c}.
  set1) ; Could be either {a,b,c} or {a,b,c,d}.

However, this is well–defined:

(let ((set1 (set 'a 'b 'c)))
  (set-adjoin! set1 'd)) ; Add d to {a,b,c}.

So clients of these procedures write in a functional style, but must additionally be sure that, when the procedure is called, there are no other live pointers to the potentially–modified character set (hence the term “linear update”).

There are two benefits to this convention:

• Implementations are free to provide the most efficient possible implementation, either functional or side–effecting.
• Programmers may nonetheless continue to assume that sets are purely functional data structures: they may be reliably shared without needing to be copied, uniquified, and so forth.

In practice, these procedures are most useful for efficiently constructing sets and bags in a side–effecting manner, in some limited local context, before passing the character set outside the local construction scope to be used in a functional manner.

Scheme provides no assistance in checking the linearity of the potentially side–effected parameters passed to these functions: there’s no linear type checker or run–time mechanism for detecting violations.

Note that if an implementation uses no side effects at all, it is allowed to return existing sets and bags rather than newly allocated ones, even where this SRFI explicitly says otherwise.

Comparator restrictions

Implementations of this SRFI are allowed to place restrictions on the comparators that the procedures accept. In particular, an implementation may require comparators to provide a comparison procedure. Alternatively, an implementation may require comparators to provide a hash function, unless the equality predicate of the comparator is eq?, eqv?, equal?, string=?, or string-ci=?. Implementations must not require the provision of both a comparison procedure and a hash function.