-
Notifications
You must be signed in to change notification settings - Fork 9
/
srfi-113-1.5.html
462 lines (270 loc) · 31.5 KB
/
srfi-113-1.5.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
<!--
SPDX-FileCopyrightText: 2013 John Cowan <[email protected]>
SPDX-License-Identifier: MIT
-->
<!DOCTYPE HTML PUBLIC "" "-//W3C//DTD HTML 3.2 Final//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<title>SRFI 113: Sets, Bags, Integer Sets</title>
</head>
<body>
<H1>Title</H1>
Sets, bags, integer sets
<H1>Author</H1>
John Cowan
<p>
This SRFI is currently in ``draft'' status.
To see an explanation of
each status that a SRFI can hold, see <a
href="http://srfi.schemers.org/srfi-process.html">here</a>.
To provide input on this SRFI, please
<a href="mailto:srfi minus 113 at srfi dot schemers dot org">mail to
<code><srfi minus 113 at srfi dot schemers dot org></code></a>. See
<a href="../../srfi-list-subscribe.html">instructions here</a> to
subscribe to the list. You can access previous messages via
<a href="mail-archive/maillist.html">the archive of the mailing list</a>.
</p>
<ul>
<li>Received: <a href="http://srfi.schemers.org/srfi-113/srfi-113-1.1.html">2013/05/31</a></li>
<li>Draft: 2013/06/01-2013/08/01</li>
<li>Revised: <a href="http://srfi.schemers.org/srfi-113/srfi-113-1.2.html">2013/06/09</a></li>
<li>Revised: <a href="http://srfi.schemers.org/srfi-113/srfi-113-1.3.html">2013/07/03</a></li>
<li>Revised: <a href="http://srfi.schemers.org/srfi-113/srfi-113-1.4.html">2013/12/04</a></li>
<li>Revised: <a href="http://srfi.schemers.org/srfi-113/srfi-113-1.5.html">2014/03/31</a></li>
</ul>
<H1>Abstract</H1><p><em>Sets</em> and <em>bags</em> (also known as multisets) are unordered collections that can contain any Scheme object. Sets enforce the constraint that no two elements can be the same in the sense of the set's associated <em>equality predicate</em>; bags do not. <em>Integer sets</em> are a variant of sets that can only contain non-negative exact integers that are less than a maximum value specified when the integer set is created, and that always use numerical equality as their equality predicate.
</p>
<H1>Issues</H1>
<p>16. What provisions should we have for controlling which element of a set is preserved when a new element equal to an existing element is added?</p>
<H1>Rationale</H1>
<p>Sets are a standard part of the libraries of many high-level programming languages, including Smalltalk, <a href="http://docs.oracle.com/javase/6/docs/api/java/util/Set.html">Java</a>, and <a href="http://www.cplusplus.com/reference/set/set/">C++</a>. <a href="http://docs.racket-lang.org/reference/sets.html">Racket</a> provides general sets similar to those of this proposal, though with fewer procedures, and there is a Chicken egg called <code>sets</code> (unfortunately undocumented), which provides a minimal set of procedures.</p><p>Bags are useful for counting anything from a fixed set of possibilities, e.g. the number of each type of error in a log file or the number of uses of each word in a lexicon drawn from a body of documents. Although other data structures can serve the same purpose, using bags clearly expresses the programmer's intent and can be optimized.</p>
<p>Although sets subsume integer sets, providing them separately allows for increased implementation efficiency. There are two Chicken eggs that provide integer sets: <a href="http://wiki.call-cc.org/eggref/4/iset#integer-sets"><code>iset</code></a>, which is conceptually similar to the integer sets described here, but using bignums rather than bytevectors; and <a href="http://wiki.call-cc.org/eggref/4/cis"><code>cis</code></a>, which uses lists of integer intervals.</p>
<p>Insofar as possible, the names in this SRFI are harmonized with the names used for ordered collections (lists, strings, vectors, and bytevectors) in Scheme. However, <code>size</code> is used instead of <code>length</code> to express the number of elements in the collection, because <code>length</code> implies order.</p>
<p>Although it's possible to use the general sets of this SRFI to contain characters, the use of <a href="http://srfi.schemers.org/srfi-14/srfi-14.html">SRFI 14</a> is recommended instead. The names in this SRFI are harmonized with SRFI 14, except that SRFI 14 does not contain analogues of the <code>set>>?</code>, <code>set<=?</code>, <code>set>=?</code>, <code>set-remove</code>, or <code>set-partition</code> procedures.</p>
<p>Sets do not have a lexical syntax representation. It's possible to use <a href="http://srfi.schemers.org/srfi-108/srfi-108.html">SRFI 108</a> quasi-literal constructors to create them in code, but this SRFI does not standardize how that is done.</p>
<p>The interface to general sets and bags depends on <a href="http://srfi.schemers.org/srfi-114/srfi-114.html">SRFI 114</a> comparators, despite that SRFI having a higher number than this one (for hysterical raisins). Comparators conveniently package the equality predicate of the set with the hash function or comparison procedure needed to implement the set efficiently.</p>
<p>During the discussion of this SRFI, a new expression type <code>enumeration-case</code> similar to <code>case</code> was proposed. It would dispatch based on a member of an enumeration set, with enumeration-specific error checking? Specifically, an error would be signaled if the cases are not exhaustive, or if any clause datum is not a member of the enumeration set. Unfortunately, due to phasing problems, <code>enumeration-case</code> would only work with enumerations defined using <code>define-enum</code>, and it would be awkward to implement it with <code>syntax-rules</code> only. Therefore, it was not included.</p>
<H1>Specification</H1>
<p>Sets, bags, and integer sets are mutually disjoint, and disjoint from other types of Scheme objects.</p>
<p>It is an error for any procedure defined in this SRFI to be invoked on sets or bags with different comparators.</p>
<h2>Linear update</h2>
<p>The procedures of this SRFI, by default, are "pure functional" — they do not alter their parameters. However, this SRFI defines a set of "linear-update" procedures, all of whose names end in <code>!</code>. 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.</p>
<p>It is an error to rely upon these procedures working by side effect. For example, this is not guaranteed to work:</p>
<pre>
(let* ((set1 (set 'a 'b 'c)) ; set1 = {a,b,c}.
(set2 (set-adjoin! 'd))) ; Add d to {a,b,c}.
set1) ; Could be either {a,b,c} or {a,b,c,d}.
</pre>
<p>However, this is well-defined:</p>
<pre>
(let ((set1 (set 'a 'b 'c)))
(set-adjoin! set1 'd)) ; Add d to {a,b,c}.
</pre>
<p>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").</p>
<p>There are two benefits to this convention:</p>
<ul><li><p>Implementations are free to provide the most efficient possible implementation, either functional or side-effecting.</p></li>
<li><p>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.</p></li></ul>
<p>In practice, these procedures are most useful for efficiently constructing sets 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.</p>
<p>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.</p>
<p>Note that if the implementation is entirely pure functional, it is allowed to return existing sets rather than newly allocated ones, even where this SRFI explicitly says otherwise.</p>
<h2 id="Index">Index</h2>
<ul><li><p><a href="#Constructors">Constructors</a>: <code>set</code>, <code>set-adjoin</code>, <code>set-delete</code>, <code>set-unfold</code></p>
</li><li><p><a href="#Predicates">Predicates</a>: <code>set?</code>, <code>set-contains?</code>, <code>set-empty?</code>, <code>set-disjoint?</code></p>
</li><li><p><a href="#Accessor">Accessor</a>: <code>set-value</code></p>
</li><li><p><a href="#Linearupdateprocedures">Linear update procedures</a>: <code>set-adjoin!</code>, <code>set-delete!</code>, <code>set-intern!</code></p>
</li><li><p><a href="#Thewholeset">The whole set</a>: <code>set-size</code>, <code>set-find</code>, <code>set-count</code>, <code>hash-table-any?</code>, <code>hash-table-every?</code></p>
</li><li><p><a href="#Mappingandfolding">Mapping and folding</a>: <code>set-map</code>, <code>set-for-each</code>, <code>set-fold</code>, <code>hash-table-filter</code>, <code>hash-table-filter!</code>, <code>hash-table-remove</code>, <code>hash-table-partition</code></p>
</li><li><p><a href="#Copyingandconversion">Copying and conversion</a>: <code>set-copy</code>, <code>set-empty-copy</code>, <code>set->list</code>, <code>list->set</code>, <code>list->set!</code></p>
</li><li><p><a href="#Subsets">Subsets</a>: <code>hash-table=?</code>, <code>hash-table<?</code>, <code>hash-table>?</code>, <code>hash-table<=?</code>, <code>hash-table>=?</code></p>
</li><li><p><a href="#Setoperations">Set operations</a>: <code>hash-table-union!</code>, <code>hash-table-intersection!</code>, <code>hash-table-difference!</code></p>
</li><li><p><a href="#Additionalbagprocedures">Additional bag procedures</a>: <code>bag-element-count</code>, <code>bag-for-each-unique</code>, <code>bag-fold-unique</code>, <code>bag-increment!</code>, <code>bag-decrement!</code>, <code>bag->set</code>, <code>set->bag</code>, <code>set->bag!</code></p>
</li><li><p><a href="#Additionalintegersetprocedures">Additional integer set procedures</a>: <code>integer-set</code>, <code>make-universal-integer-set</code>, <code>integer-set-complement</code>, <code>integer-set-complement!</code>, <code>integer-set-min</code>, <code>integer-set-max</code></p>
</li>
</ul>
<h2 id="Setprocedures">Set procedures</h2>
<h3 id="Constructors">Constructors</h3>
<p><code>(set </code><em>comparator</em> <em>element</em> ... <code>)</code></p>
<p>Returns a newly allocated empty set. The <em>comparator</em> argument is a <a href="http://srfi.schemers.org/srfi-114/srfi-114.html">SRFI 114</a> comparator. The <em>elements</em> are used to initialize the set.</p>
<p><code>(set-adjoin </code><em>set</em><code> </code><em>element</em> ... <code>)</code></p>
<p>Returns a newly allocated set that uses the same comparator as <em>set</em> and contains all the values of <em>set</em>, and in addition each <em>element</em> unless it is already the same (in the sense of <em>set's</em> equality predicate) as an existing member. It is an error to add an element to <i>set</i> that does not return <code>#t</code> when passed to the type test procedure of the comparator with which <i>set</i> was defined.</p>
<p><code>(set-delete </code><em>set</em><code> </code><em>element</em> ... <code>)</code></p>
<p>Returns a newly allocated set containing all the values of <em>set</em> except for the <em>elements</em>. Any <em>element</em> that is not a member of the set is ignored.</p>
<p><code>(set-unfold </code><em>comparator continue? mapper successor seed</em><code>)</code></p>
<p>Create a newly allocated set as if by <code>set</code> using <em>comparator</em>. If the result of applying the predicate <em>continue?</em> to <em>seed</em> is <code>#f</code>, return the set. Otherwise, apply the procedure <em>mapper</em> to <em>seed</em>. The value that <em>mapper</em> returns is added to the set. Then get a new seed by applying the procedure <em>successor</em> to <em>seed</em>, and repeat this algorithm.</p>
<h3 id="Predicates">Predicates</h3>
<p><code>(set? </code><em>obj</em><code>)</code></p>
<p>Returns <code>#t</code> if <em>obj</em> is a set, and <code>#f</code> otherwise.</p>
<p><code>(set-member? </code><em>set</em><code> </code><em>element</em><code>)</code></p>
<p>Returns <code>#t</code> if <em>element</em> is a member of <em>set</em> and <code>#f</code> otherwise.</p>
<p><code>(set-empty? </code><em>set</em><code>)</code></p>
<p>Returns <code>#t</code> if <em>set</em> has no elements and <code>#f</code> otherwise.</p>
<p><code>(set-disjoint? </code><em>set<sub>1</sub> set<sub>2</sub></em><code>)</code></p>
<p>Returns <code>#t</code> if <em>set<sub>1</sub></em> and <em>set<sub>2</sub></em> have no elements in common and <code>#f</code> otherwise.</p>
<h3 id="Accessor">Accessor</h3>
<p><code>(set-value </code><em>set</em><code> </code><em>element</em><code>)</code></p>
<p>Returns the element of <em>set</em> that is equal, in the sense of <em>set's</em> equality predicate, to <em>element</em>. If <em>element</em> is not a member of <em>set</em>, it is returned.</p>
<h3 id="Linearupdateprocedures">Linear update procedures</h3>
<p><code>(set-adjoin! </code><em>set</em><code> </code><em>element</em><code>)</code></p>
<p>Returns a set that uses the same comparator as <em>set</em> and contains all the values of <em>set</em>, and in addition each <em>element</em> unless it is already a member. It is an error to add an element to <i>set</i> that does not return <code>#t</code> when passed to the type test procedure of the comparator with which <i>set</i> was defined.</p>
<p><code>(set-delete! </code><em>set</em><code> </code><em>element</em><code>)</code></p>
<p>Returns a set containing all the values of <em>set</em> except for the <em>elements</em>. Any <em>element</em> that is not equal (in the sense of<em>set's</em> equality predicate) to some member of the set is ignored.</p>
<p><code>(set-intern! </code><em>set</em><code> </code><em>element</em><code>)</code></p>
<p>Returns two values. If there is an element of <em>set</em> that is equal, in the sense of <em>set's</em> equality predicate, to <em>element</em>, then that element is returned as the first value and <em>set</em> is returned as the second value. If there is no such element, then the first value is <em>element</em> and the second value is the result of <code>(set-add! </code><em>set element</em><code>)</code>.</p>
<p><code>(set-search! </code><em>set element failure success</em><code>)</code></p>
<p>The <em>set</em> is searched for <em>element</em>. If it is not found, then the <em>failure</em> procedure is tail-called with two continuation arguments, <em>insert</em> and <em>ignore</em>, and is expected to tail-call one of them. If <em>element</em> is found, then the <em>success</em> procedure is tail-called with the matching element of <em>set</em> and two continuations, <em>update</em> and <em>remove</em>, and is expected to tail-call one of them.</p>
<p>The effects of the continuations are as follows (where <em>obj</em> is any Scheme object):</p>
<ul>
<li><p>Invoking <code>(</code><em>insert obj</em><code>)</code> causes <em>element</em> to be inserted into <em>set</em>.</p></li>
<li><p>Invoking <code>(</code><em>ignore obj</em><code>)</code> causes <em>set</em> to remain unchanged.</p></li>
<li><p>Invoking <code>(</code><em>update new-element obj</em><code>)</code> causes <em>new-element</em> to be inserted into <em>set</em>.</p></li>
<li><p>Invoking <code>(</code><em>remove obj</em><code>)</code> causes the matching element of <em>set</em> to be removed from it.</p></li>
</ul>
<p>In all cases, two values are returned: the possibly updated <em>set</em> and <em>obj</em>.</p>
<h3 id="Thewholeset">The whole set</h3><p><code>(set-size </code><em>set</em><code>)</code></p><p>
Returns the number of elements in <em>set</em> as an exact integer.
</p><p><code>(set-count </code><em>predicate</em><code> </code><em>set</em><code>)</code></p><p>
Returns the number of elements of <em>set</em> that satisfy <em>predicate</em> as an exact integer.
</p><p><code>(set-find </code><em>predicate set failure</em><code>)</code></p><p>
Returns an arbitrarily chosen element of <em>set</em> that satisfies <em>predicate</em>, or the result of invoking <em>failure</em> with no arguments if there is none.
</p><p><code>(set-any? </code><em>predicate</em><code> </code><em>set</em><code>)</code></p><p>
Returns <code>#t</code> if any element of <em>set</em> satisfies <em>predicate</em>, or <code>#f</code> otherwise. Note that this differs from the SRFI 1 analogue because it does not return a useful value.
</p><p><code>(set-every? </code><em>predicate</em><code> </code><em>set</em><code>)</code></p><p>
Returns <code>#t</code> if every element of <em>set</em> satisfies <em>predicate</em>, or <code>#f</code> otherwise. Note that this differs from the SRFI 1 analogue because it does not return a useful value.
</p>
<h3 id="Mappingandfolding">Mapping and folding</h3>
<p><code>(set-map </code><em>comparator</em><code> </code><em>proc</em><code> </code><em>set</em><code>)</code></p>
<p>Applies <em>proc</em> to each element of <em>set</em> in arbitrary order and returns a newly allocated set, created as if by <code>set</code>, which contains the results of the applications. For example:</p>
<pre>
(set-map string-ci=? symbol->string (set eq? 'foo 'bar 'baz))
=> (set string-ci=? "foo" "bar" "baz")
</pre>
<p><code>(set-for-each </code><em>proc</em><code> </code><em>set</em><code>)</code></p>
<p>Applies <em>proc</em> to <em>set</em> in arbitrary order, discarding the returned values. Returns an unspecified result.</p>
<p><code>(set-fold </code><em>proc</em><code> </code><em>nil</em><code> </code><em>set</em><code>)</code></p>
<p>Invokes <em>proc</em> on each member of <em>set</em> in arbitrary order, passing the result of the previous invocation as a second argument. For the first invocation, <em>nil</em> is used as the second argument. Returns the result of the last invocation.</p>
<p><code>(set-filter </code><em>predicate</em><code> </code><em>set</em><code>)</code></p>
<p>Returns a newly allocated set, created as if by <code>set-empty-copy</code>, containing just the elements of <em>set</em> that satisfy <em>predicate</em>.</p>
<p><code>(set-filter! </code><em>predicate</em><code> </code><em>set</em><code>)</code></p>
<p>A linear update procedure that returns a set containing just the elements of <em>set</em> that satisfy <em>predicate</em>.</p>
<p><code>(set-remove </code><em>predicate</em><code> </code><em>set</em><code>)</code></p>
<p>
Returns a newly allocated set, created as if by <code>set-empty-copy</code>, containing just the elements of <em>set</em> that do not satisfy <em>predicate</em>.
</p>
<p><code>(set-partition </code><em>predicate</em><code> </code><em>set</em><code>)</code></p>
<p>
Returns two values: a newly allocated set, created as if by <code>set-empty-copy</code>, containing just the elements of <em>set</em> that satisfy <em>predicate</em>, and another newly allocated set, created as if by <code>set-empty-copy</code>, containing just the elements of <em>set</em> that do not satisfy <em>predicate</em>.</p>
<h3 id="Copyingandconversion">Copying and conversion</h3>
<p><code>(set-copy </code><em>set</em><code>)</code></p><p>
Returns a newly allocated set containing the elements of <em>set</em>, and using the same comparator.
</p><p><code>(set-empty-copy </code><em>set</em><code>)</code></p><p>
Returns a newly allocated set containing no elements, and using the same comparator as <em>set</em>.
</p>
<p><code>(set->list </code><em>set</em><code>)</code></p><p>
Returns a newly allocated list containing the members of <em>set</em> in unspecified order. However, repeated calls to this procedure will return a list in the same order until the set is mutated.
</p><p><code>(list->set </code><em>comparator list</em><code>)</code></p><p>
Returns a newly allocated set, created as if by <code>set</code> using <em>comparator</em>, that contains the elements of <em>list</em>.
</p><p><code>(list->set! </code><em>comparator list</em><code>)</code></p><p>
Returns a set using <em>comparator</em> that contains the elements of <em>list</em>.
</p><h3 id="Subsets">Subsets</h3>
<p><code>(set=? </code><em>set</em> ...<code>)</code>
</p><p>
Returns <code>#t</code> if each <em>set</em> contains the same elements.
</p><p><code>(set<? </code><em>set</em> ...<code>)</code>
</p><p>
Returns <code>#t</code> if each <em>set</em> other than the last is a proper subset of the following <em>set</em>, and <code>#f</code> otherwise.
</p><p><code>(set>? </code><em>set</em> ...<code>)</code>
</p><p>
Returns <code>#t</code> if each <em>set</em> other than the last is a proper superset of the following <em>set</em>, and <code>#f</code> otherwise.
</p><p><code>(set<=? </code><em>set</em> ...<code>)</code>
</p><p>
Returns <code>#t</code> if each <em>set</em> other than the last is a subset of the following <em>set</em>, and <code>#f</code> otherwise.
</p><p><code>(set>=? </code><em>set</em> ...<code>)</code>
</p><p>
Returns <code>#t</code> if each <em>set</em> other than the last is a superset of the following <em>set</em>, and <code>#f</code> otherwise.
</p>
<h3 id="Setoperations">Set operations</h3><p><code>(set-union </code><em>set<sub>1</sub></em><code> </code><em>set<sub>2</sub></em> ...<code>)</code>
</p><p><code>(set-intersection </code><em>set<sub>1</sub></em><code> </code><em>set<sub>2</sub></em> ...<code>)</code>
</p><p><code>(set-difference </code><em>set<sub>1</sub></em><code> </code><em>set<sub>2</sub></em> ...<code>)</code>
</p><p><code>(set-xor </code><em>set<sub>1</sub></em><code> </code><em>set<sub>2</sub></em><code>)</code></p><p>
Returns a newly allocated set that is the union, intersection, asymmetric difference, or symmetric difference of the <em>sets</em>. 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.
</p><p><code>(set-union! </code><em>set<sub>1</sub></em><code> </code><em>set<sub>2</sub></em> ...<code>)</code>
</p><p><code>(set-intersection! </code><em>set<sub>1</sub></em><code> </code>set<sub>2</sub><em> ...<code>)</code>
</em></p><p><code>(set-difference! </code><em>set<sub>1</sub></em><code> </code><em>set<sub>2</sub></em> ...<code>)</code>
</p><p><code>(set-xor! </code><em>set<sub>1</sub></em><code> </code><em>set<sub>2</sub></em><code>)</code></p>
<p>Linear update procedures returning a set that is the union, intersection, asymmetric difference, or symmetric difference of the <em>sets</em>. 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.</p>
<h2 id="Bagprocedures">Bag procedures</h2><p>
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 <code>eqv?</code>, are both included, it is not guaranteed that they will remain distinct when retrieved from the bag. It is an error for a single procedure to be invoked on bags with different comparators.
</p><p>
The procedures for creating and manipulating bags are the same as those for sets, except that <code>set</code> is replaced by <code>bag</code> in their names, and that adding an element to a bag is effective even if the bag already contains the element. If two elements in a bag are the same in the sense of the equality predicate, the implementation may in fact store just one of them. There are no procedures named <code>bag-xor</code> or <code>bag-xor!</code>.
</p>
<h3 id="Additionalbagprocedures">Additional bag procedures</h3>
<p><code>(bag-element-count </code><em>bag</em><code> </code><em>element</em><code>)</code></p><p>
Returns an exact integer representing the number of times that <em>element</em> appears in <em>bag</em>.
</p><p><code>(bag-for-each-unique </code><em>proc</em><code> </code><em>bag</em><code>)</code></p><p>
Applies <em>proc</em> to each unique element of <em>bag</em> in arbitrary order, passing the element and the number of times it occurs in <em>bag</em>, and discarding the returned values. Returns an unspecified result.
</p><p><code>(bag-fold-unique </code><em>proc</em><code> </code><em>nil</em><code> </code><em>bag</em><code>)</code></p><p>
Invokes <em>proc</em> on each unique element of <em>bag</em> in arbitrary order, passing the number of occurrences as a second argument and the result of the previous invocation as a third argument. For the first invocation, <em>nil</em> is used as the third argument. Returns the result of the last invocation.
</p><p><code>(bag-increment! </code><em>bag<code> </code>element<code> </code>count</em><code>)</code></p><p><code>(bag-decrement! </code><em>bag<code> </code>element<code> </code>count</em><code>)</code></p><p>
Linear update procedures that return a bag with the same elements as <em>bag</em>, but with the element count of <em>element</em> in <em>bag</em> increased or decreased by the exact integer <em>count</em> (but not less than zero).
</p><p><code>(bag->set </code><em>bag</em><code>)</code></p><p><code>(set->bag </code><em>set</em><code>)</code></p><p>
The <code>bag->set</code> procedure returns a newly allocated set containing the unique elements of <em>bag</em>. The <code>set->bag</code> procedure returns a newly allocated bag containing the elements of <em>set</em>. The comparator of the result is the same as the comparator of the argument.
</p><h2 id="Integersetprocedures">Integer set procedures</h2><p>
The elements of an integer set are non-negative exact integers less than the set's <em>limit</em>, 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 <code>set</code> is replaced by <code>integer-set</code> in their names.</p>
<p>Wherever a newly allocated integer set is returned, it has the same limit as the source sets. It is an error for a single procedure to be invoked on integer sets with different limits.</p>
<p>There are no <code>integer-set-value</code> or <code>integer-set-intern!</code> procedures.</p>
<h3 id="Additionalintegersetprocedures">Additional integer set procedures</h3>
<p><code>(integer-set </code><em>limit element</em> ...<code>)</code></p><p>
Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to <em>limit</em> - 1, where <em>limit</em> is an exact non-negative integer. The set contains the <em>elements</em>.
</p><p><code>(universal-integer-set </code><em>limit</em><code>)</code></p><p>
Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to <em>limit</em> - 1, where <em>limit</em> is an exact non-negative integer. The set contains all possible elements.
</p><p><code>(range->-integer-set </code><em>limit low high</em><code>)</code></p><p>
Returns a newly allocated integer set. The possible elements of the set are the exact integers from 0 to <em>limit</em> - 1, where <em>limit</em> is an exact non-negative integer. The set contains the elements from <em>low</em> (inclusive) to <em>high</em> (exclusive).
</p><p><code>(integer-set-adjoin-range </code><em>integer-set low high</em><code>)</code></p><p>
Returns a newly allocated integer set with the same limit as <em>integer-set</em> and that contains all its values, and in addition each integer from <em>low</em> (inclusive) to <em>high</em> (exclusive) unless it is already equal to an existing member.
</p><p><code>(integer-set-adjoin-range! </code><em>integer-set low high</em><code>)</code></p><p>
A linear update procedure that returns an integer set with the same limit as <em>integer-set</em> and that contains all its values, and in addition each integer from <em>low</em> (inclusive) to <em>high</em> (exclusive) unless it is already equal to an existing member.
</p><p><code>(integer-set-complement </code><em>integer-set</em><code>)</code></p><p>
Returns a newly allocated integer set that is the complement of <em>integer-set</em>.
</p><p><code>(integer-set-complement! </code><em>integer-set</em><code>)</code></p><p>
A linear update procedure that returns a set that is the complement of <em>integer-set</em>.
</p><p><code>(integer-set-min </code><em>integer-set</em><code>)</code></p><p><code>(integer-set-max </code><em>integer-set</em><code>)</code></p><p>
Returns the smallest or largest integer in <i>integer-set</i>, or <code>#f</code> if there is none.
</p><p><code>(integer-set-delete-min! </code><em>integer-set</em><code>)</code></p>
<p><code>(integer-set-delete-max! </code><em>integer-set</em><code>)</code></p><p>
Linear update procedures that return two values: the smallest or largest integer in <em>integer-set</em> or <code>#f</code> if there is none, and a set which contains all the elements of <em>set</em> except the integer being returned.
</p><H1>Implementation</H1>
<p>The implementation places the identifiers defined above into the <code>sets</code> library.</p>
<p>Sets and bags are implemented as a thin veneer over hashtables, and integer sets over bytevectors. For clarity, the integer set implementation stores just one value into each bytevector element rather than the eight that would be possible.</p>
<p>The <a href="sets.tar.gz">sample implementation</a> contains the following files:</p>
<ul><li><code>sets-impl.scm</code> – implementation of general sets</li>
<li><code>bags-impl.scm</code> – implementation of bags</li>
<li><code>isets-impl.scm</code> – implementation of integer sets</li>
<li><code>count.scm</code> – provides macros for conveniently looping over bytevectors</li>
<li><code>srfi-4-shim.scm</code> – minimal implementation of R7RS bytevectors on top of SRFI 4's u8vectors</li>
<li><code>sets.sld</code> – an R7RS library named <code>(sets)</code></li>
<li><code>sets.scm</code> – a Chicken library</li>
<li><code>sets-test.scm</code> – test suite</li></ul>
<p>The test suite will work with the Chicken <code>test</code> egg, which is provided on Chibi as the <code>(chibi test)</code> library.</p>
<H1>Copyright</H1>
<p>Copyright (C) John Cowan 2013. All Rights Reserved.</p>
<p>Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:</p>
<p>The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.</p>
<p>THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.</p>
<hr />
<address>Editor: <a href="mailto:srfi-editors at srfi dot schemers dot org">
Mike Sperber</a></address>
</body>
</html>