Next: , Up: srfi sets-and-bags   [Index]


2.37.1 Introduction

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

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:

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:

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.


Next: , Up: srfi sets-and-bags   [Index]