source: project/wiki/eggref/5/srfi-113 @ 37636

Last change on this file since 37636 was 37311, checked in by Jeremy Steward, 19 months ago

Add chicken 5 docs for srfi-113

File size: 28.3 KB
Line 
1== SRFI-113: Sets and Bags
2
3Sets and bags (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 equality predicate; bags do not.
4
5[[toc:]]
6
7== Installation
8
9 $ chicken-install srfi-113
10or
11
12 $ chicken-install srfi-113 -test
13
14if you want to run the tests for the egg in addition.
15
16== SRFI Description
17
18For a full description of this SRFI, see the full SRFI
19[[http://srfi.schemers.org/srfi-113/srfi-113.html|document]]. This
20documentation covers the API only.
21
22Although this version of SRFI-113 is based on the reference implementation,
23there is one notable difference. As SRFI-114 comparators have been deprecated
24in favour of SRFI-128 comparators, this egg uses SRFI-128 comparators whenever
25a comparator is needed. Thus, this egg depends on
26[[http://wiki.call-cc.org/eggref/4/srfi-128|SRFI-128]].
27
28== Set Procedures
29
30=== Constructors
31
32<procedure>(set comparator element ...)</procedure>
33
34Returns a newly allocated empty set. The comparator argument is a
35[[http://wiki.call-cc.org/eggref/4/srfi-128|SRFI-128]] comparator, which is
36used to control and distinguish the elements of the set. The elements are used
37to initialize the set.
38
39<procedure>(set-unfold comparator stop? mapper successor seed)</procedure>
40
41Create a newly allocated set as if by set using {{comparator}}. If the result
42of applying the predicate {{stop?}} to {{seed}} is true, return the set.
43Otherwise, apply the procedure {{mapper}} to {{seed}}. The value that
44{{mapper}} returns is added to the set. Then get a new seed by applying the
45procedure successor to {{seed}}, and repeat this algorithm.
46
47=== Predicates
48
49<procedure>(set? obj)</procedure>
50
51Returns {{#t}} if {{obj}} is a set, and {{#f}} otherwise.
52
53<procedure>(set-contains? set element)</procedure>
54
55Returns {{#t}} if {{element}} is a member of {{set}} and {{#f}} otherwise.
56
57<procedure>(set-empty? set)</procedure>
58
59Returns {{#t}} if {{set}} has no elements and {{#f}} otherwise.
60
61<procedure>(set-disjoint? set1 set2)</procedure>
62
63Returns {{#t}} if {{set1}} and {{set2}} have no elements in common and {{#f}}
64otherwise.
65
66=== Accessors
67
68<procedure>(set-member set element default)</procedure>
69
70Returns the element of {{set}} that is equal, in the sense of set's equality
71predicate, to {{element}}. If {{element}} is not a member of set, {{default}}
72is returned.
73
74<procedure>(set-element-comparator set)</procedure>
75
76Returns the comparator used to compare the elements of {{set}}.
77
78=== Updaters
79
80<procedure>(set-adjoin set element ...)</procedure>
81
82The {{set-adjoin}} procedure returns a newly allocated set that uses the same
83comparator as {{set}} and contains all the values of {{set}}, and in addition
84each {{element}} unless it is already equal (in the sense of the comparator) to
85one of the existing or newly added members. It is an error to add an element to
86{{set}} that does not return {{#t}} when passed to the type test procedure of
87the comparator.
88
89<procedure>(set-adjoin! set element ...)</procedure>
90
91The {{set-adjoin!}} procedure is the same as {{set-adjoin}}, except that it is
92permitted to mutate and return the {{set}} argument rather than allocating a
93new set.
94
95<procedure>(set-replace set element)</procedure>
96
97The {{set-replace}} procedure returns a newly allocated set that uses the same
98comparator as {{set}} and contains all the values of {{set}} except as follows:
99If {{element}} is equal (in the sense of {{set}}'s comparator) to an existing
100member of {{set}}, then that member is omitted and replaced by {{element}}. If
101there is no such element in {{set}}, then {{set}} is returned unchanged.
102
103<procedure>(set-replace! set element)</procedure>
104
105The {{set-replace!}} procedure is the same as {{set-replace}}, except that it
106is permitted to mutate and return the {{set}} argument rather than allocating a
107new set.
108
109<procedure>(set-delete set element ...)</procedure>
110<procedure>(set-delete! set element ...)</procedure>
111<procedure>(set-delete-all set element-list)</procedure>
112<procedure>(set-delete-all! set element-list)</procedure>
113
114The {{set-delete}} procedure returns a newly allocated set containing all the
115values of {{set}} except for any that are equal (in the sense of {{set}}'s
116comparator) to one or more of the elements. Any {{element}} that is not equal
117to some member of the set is ignored.
118
119The {{set-delete!}} procedure is the same as {{set-delete}}, except that it is
120permitted to mutate and return the {{set}} argument rather than allocating a
121new set.
122
123The {{set-delete-all}} and {{set-delete-all!}} procedures are the same as
124{{set-delete}} and {{set-delete!}}, except that they accept a single argument
125which is a list of elements to be deleted.
126
127<procedure>(set-search! set element failure success)</procedure>
128
129The {{set}} is searched for element. If it is not found, then the {{failure}}
130procedure is tail-called with two continuation arguments, {{insert}} and
131{{ignore}}, and is expected to tail-call one of them. If {{element}} is found,
132then the {{success}} procedure is tail-called with the matching element of
133{{set}} and two continuations, {{update}} and {{remove}}, and is expected to
134tail-call one of them.
135
136The effects of the continuations are as follows (where obj is any Scheme
137object):
138
139* Invoking {{(insert obj)}} causes {{element}} to be inserted into {{set}}.
140* Invoking {{(ignore obj)}} causes {{set}} to remain unchanged.
141* Invoking {{(update new-element obj)}} causes {{new-element}} to be inserted into {{set}} in place of {{element}}.
142* Invoking {{(remove obj)}} causes the matching element of {{set}} to be removed from it.
143
144In all cases, two values are returned: the possibly updated {{set}} and
145{{obj}}.
146
147=== The Whole Set
148
149<procedure>(set-size set)</procedure>
150
151Returns the number of elements in {{set}} as an exact integer.
152
153<procedure>(set-find predicate set failure)</procedure>
154
155Returns an arbitrarily chosen element of {{set}} that satisfies {{predicate}},
156or the result of invoking {{failure}} with no arguments if there is none.
157
158<procedure>(set-count predicate set)</procedure>
159
160Returns the number of elements of {{set}} that satisfy {{predicate}} as an
161exact integer.
162
163<procedure>(set-any? predicate set)</procedure>
164
165Returns {{#t}} if any element of {{set}} satisfies {{predicate}}, or {{#f}}
166otherwise. Note that this differs from the SRFI 1 analogue because it does not
167return an element of the set.
168
169<procedure>(set-every? predicate set)</procedure>
170
171Returns {{#t}} if every element of {{set}} satisfies {{predicate}}, or {{#f}}
172otherwise. Note that this differs from the SRFI 1 analogue because it does not
173return an element of the set.
174
175=== Mapping and Folding
176
177<procedure>(set-map comparator proc set)</procedure>
178
179Applies {{proc}} to each element of set in arbitrary order and returns a newly
180allocated set, created as if by (set comparator), which contains the results of
181the applications. For example:
182
183<enscript highlight="scheme">
184(set-map string-ci-comparator symbol->string (set eq? 'foo 'bar 'baz))
185     => (set string-ci-comparator "foo" "bar" "baz")
186</enscript>
187
188Note that, when {{proc}} defines a mapping that is not 1:1, some of the mapped
189objects may be equivalent in the sense of {{comparator}}'s equality predicate,
190and in this case duplicate elements are omitted as in the {{set}} constructor.
191For example:
192
193<enscript highlight="scheme">
194(set-map (lambda (x) (quotient x 2))
195         integer-comparator
196         (set integer-comparator 1 2 3 4 5))
197 => (set integer-comparator 0 1 2)
198</enscript>
199
200If the elements are the same in the sense of {{eqv?}}, it is unpredictable
201which one will be preserved in the result.
202
203<procedure>(set-for-each proc set)</procedure>
204
205Applies {{proc}} to {{set}} in arbitrary order, discarding the returned values.
206Returns an unspecified result.
207
208<procedure>(set-fold proc nil set)</procedure>
209
210Invokes {{proc}} on each member of {{set}} in arbitrary order, passing the
211result of the previous invocation as a second argument. For the first
212invocation, {{nil}} is used as the second argument. Returns the result of the
213last invocation, or {{nil}} if there was no invocation.
214
215<procedure>(set-filter predicate set)</procedure>
216
217Returns a newly allocated set with the same comparator as {{set}}, containing just the elements of {{set}} that satisfy {{predicate}}.
218
219<procedure>(set-filter! predicate set)</procedure>
220
221A linear update procedure that returns a set containing just the elements of
222{{set}} that satisfy {{predicate}}.
223
224<procedure>(set-remove predicate set)</procedure>
225
226Returns a newly allocated set with the same comparator as {{set}}, containing
227just the elements of {{set}} that do not satisfy {{predicate}}.
228
229<procedure>(set-remove! predicate set)</procedure>
230
231A linear update procedure that returns a set containing just the elements of
232{{set}} that do not satisfy {{predicate}}.
233
234<procedure>(set-partition predicate set)</procedure>
235
236Returns two values: a newly allocated set with the same comparator as {{set}}
237that contains just the elements of {{set}} that satisfy {{predicate}}, and
238another newly allocated set, also with the same comparator, that contains just
239the elements of {{set}} that do not satisfy {{predicate}}.
240
241<procedure>(set-partition! predicate set)</procedure>
242
243A linear update procedure that returns two sets containing the elements of set
244that do and do not, respectively, not satisfy predicate.
245
246=== Copying and Conversion
247
248<procedure>(set-copy set)</procedure>
249
250Returns a newly allocated set containing the elements of {{set}}, and using the
251same comparator.
252
253<procedure>(set->list set)</procedure>
254
255Returns a newly allocated list containing the members of {{set}} in unspecified order.
256
257<procedure>(list->set comparator list)</procedure>
258
259Returns a newly allocated set, created as if by {{set}} using {{comparator}}, that
260contains the elements of {{list}}. Duplicate elements (in the sense of the equality
261predicate) are omitted.
262
263<procedure>(list->set! set list)</procedure>
264
265Returns a set that contains the elements of both {{set}} and {{list}}. Duplicate
266elements (in the sense of the equality predicate) are omitted.
267
268=== Subsets
269
270'''Note:''' The following three predicates do not obey the trichotomy law and
271therefore do not constitute a total order on sets.
272
273<procedure>(set=? set1 set2 ...) </procedure>
274
275Returns {{#t}} if each set contains the same elements.
276
277<procedure>(set<? set1 set2 ...) </procedure>
278
279Returns {{#t}} if each set other than the last is a proper subset of the following
280set, and {{#f}} otherwise.
281
282<procedure>(set>? set1 set2 ...) </procedure>
283
284Returns {{#t}} if each set other than the last is a proper superset of the
285following set, and {{#f}} otherwise.
286
287<procedure>(set<=? set1 set2 ...) </procedure>
288
289Returns {{#t}} if each set other than the last is a subset of the following set,
290and {{#f}} otherwise.
291
292<procedure>(set>=? set1 set2 ...) </procedure>
293
294Returns {{#t}} if each set other than the last is a superset of the following set,
295and {{#f}} otherwise.
296
297=== Set-theory Operations
298
299<procedure>(set-union set1 set2 ...)</procedure>
300<procedure>(set-intersection set1 set2 ...)</procedure>
301<procedure>(set-difference set1 set2 ...)</procedure>
302<procedure>(set-xor set1 set2)</procedure>
303
304Return a newly allocated set that is the union, intersection, asymmetric
305difference, or symmetric difference of the {{sets}}. Asymmetric difference is
306extended to more than two sets by taking the difference between the first set
307and the union of the others. Symmetric difference is not extended beyond two
308sets. Elements in the result set are drawn from the first set in which they
309appear.
310
311<procedure>(set-union! set1 set2 ...)</procedure>
312<procedure>(set-intersection! set1 set2 ...)</procedure>
313<procedure>(set-difference! set1 set2 ...)</procedure>
314<procedure>(set-xor! set1 set2)</procedure>
315
316Linear update procedures returning a set that is the union, intersection,
317asymmetric difference, or symmetric difference of the {{sets}}. Asymmetric
318difference is extended to more than two sets by taking the difference between
319the first set and the union of the others. Symmetric difference is not extended
320beyond two sets. Elements in the result set are drawn from the first set in
321which they appear.
322
323== Bag Procedures
324
325Bags are like sets, but can contain the same object more than once. However, if
326two elements that are the same in the sense of the equality predicate, but not
327in the sense of {{eqv?}}, are both included, it is not guaranteed that they will
328remain distinct when retrieved from the bag. It is an error for a single
329procedure to be invoked on bags with different comparators.
330
331The procedures for creating and manipulating bags are the same as those for
332sets, except that {{set}} is replaced by {{bag}} in their names, and that adjoining an
333element to a bag is effective even if the bag already contains the element. If
334two elements in a bag are the same in the sense of the bag's comparator, the
335implementation may in fact store just one of them.
336
337The {{bag-union}}, {{bag-intersection}}, {{bag-difference}}, and {{bag-xor}}
338procedures (and their linear update analogues) behave as follows when both bags
339contain elements that are equal in the sense of the bags' comparator:
340
341* For {{bag-union}}, the number of equal elements in the result is the largest number of equal elements in any of the original bags.
342* For {{bag-intersection}}, the number of equal elements in the result is the smallest number of equal elements in any of the original bags.
343* For {{bag-difference}}, the number of equal elements in the result is the number of equal elements in the first bag, minus the number of elements in the other bags (but not less than zero).
344* For {{bag-xor}}, the number of equal elements in the result is the absolute value of the difference between the number of equal elements in the first and second bags.
345
346=== Constructors
347
348<procedure>(bag comparator element ...)</procedure>
349
350Returns a newly allocated empty bag. The comparator argument is a
351[[http://wiki.call-cc.org/eggref/4/srfi-128|SRFI-128]] comparator, which is
352used to control and distinguish the elements of the bag. The elements are used
353to initialize the bag.
354
355<procedure>(bag-unfold comparator stop? mapper successor seed)</procedure>
356
357Create a newly allocated bag as if by bag using {{comparator}}. If the result
358of applying the predicate {{stop?}} to {{seed}} is true, return the bag.
359Otherwise, apply the procedure {{mapper}} to {{seed}}. The value that
360{{mapper}} returns is added to the bag. Then get a new seed by applying the
361procedure successor to {{seed}}, and repeat this algorithm.
362
363=== Predicates
364
365<procedure>(bag? obj)</procedure>
366
367Returns {{#t}} if {{obj}} is a bag, and {{#f}} otherwise.
368
369<procedure>(bag-contains? bag element)</procedure>
370
371Returns {{#t}} if {{element}} is a member of {{bag}} and {{#f}} otherwise.
372
373<procedure>(bag-empty? bag)</procedure>
374
375Returns {{#t}} if {{bag}} has no elements and {{#f}} otherwise.
376
377<procedure>(bag-disjoint? bag1 bag2)</procedure>
378
379Returns {{#t}} if {{bag1}} and {{bag2}} have no elements in common and {{#f}}
380otherwise.
381
382=== Accessors
383
384<procedure>(bag-member bag element default)</procedure>
385
386Returns the element of {{bag}} that is equal, in the sense of bag's equality
387predicate, to {{element}}. If {{element}} is not a member of bag, {{default}}
388is returned.
389
390<procedure>(bag-element-comparator bag)</procedure>
391
392Returns the comparator used to compare the elements of {{bag}}.
393
394=== Updaters
395
396<procedure>(bag-adjoin bag element ...)</procedure>
397
398The {{bag-adjoin}} procedure returns a newly allocated bag that uses the same
399comparator as {{bag}} and contains all the values of {{bag}}, and in addition
400each {{element}}. It is an error to add an element to {{bag}} that does not
401return {{#t}} when passed to the type test procedure of the comparator.
402
403<procedure>(bag-adjoin! bag element ...)</procedure>
404
405The {{bag-adjoin!}} procedure is the same as {{bag-adjoin}}, except that it is
406permitted to mutate and return the {{bag}} argument rather than allocating a
407new bag.
408
409<procedure>(bag-replace bag element)</procedure>
410
411The {{bag-replace}} procedure returns a newly allocated bag that uses the same
412comparator as {{bag}} and contains all the values of {{bag}}. If there is no
413such element in {{bag}}, then {{bag}} is returned unchanged.
414
415<procedure>(bag-replace! bag element)</procedure>
416
417The {{bag-replace!}} procedure is the same as {{bag-replace}}, except that it
418is permitted to mutate and return the {{bag}} argument rather than allocating a
419new bag.
420
421<procedure>(bag-delete bag element ...)</procedure>
422<procedure>(bag-delete! bag element ...)</procedure>
423<procedure>(bag-delete-all bag element-list)</procedure>
424<procedure>(bag-delete-all! bag element-list)</procedure>
425
426The {{bag-delete}} procedure returns a newly allocated bag containing all the
427values of {{bag}} Any {{element}} that is not equal to some member of the bag
428is ignored.
429
430The {{bag-delete!}} procedure is the same as {{bag-delete}}, except that it is
431permitted to mutate and return the {{bag}} argument rather than allocating a
432new bag.
433
434The {{bag-delete-all}} and {{bag-delete-all!} procedures are the same as
435{{bag-delete}} and {{bag-delete!}}, except that they accept a single argument
436which is a list of elements to be deleted.
437
438<procedure>(bag-search! bag element failure success)</procedure>
439
440The {{bag}} is searched for element. If it is not found, then the {{failure}}
441procedure is tail-called with two continuation arguments, {{insert}} and
442{{ignore}}, and is expected to tail-call one of them. If {{element}} is found,
443then the {{success}} procedure is tail-called with the matching element of
444{{bag}} and two continuations, {{update}} and {{remove}}, and is expected to
445tail-call one of them.
446
447The effects of the continuations are as follows (where obj is any Scheme
448object):
449
450* Invoking {{(insert obj)}} causes {{element}} to be inserted into {{bag}}.
451* Invoking {{(ignore obj)}} causes {{bag}} to remain unchanged.
452* Invoking {{(update new-element obj)}} causes {{new-element}} to be inserted into {{bag}} in place of {{element}}.
453* Invoking {{(remove obj)}} causes the matching element of {{bag}} to be removed from it.
454
455In all cases, two values are returned: the possibly updated {{bag}} and
456{{obj}}.
457
458=== The Whole bag
459
460<procedure>(bag-size bag)</procedure>
461
462Returns the number of elements in {{bag}} as an exact integer.
463
464<procedure>(bag-find predicate bag failure)</procedure>
465
466Returns an arbitrarily chosen element of {{bag}} that satisfies {{predicate}},
467or the result of invoking {{failure}} with no arguments if there is none.
468
469<procedure>(bag-count predicate bag)</procedure>
470
471Returns the number of elements of {{bag}} that satisfy {{predicate}} as an
472exact integer.
473
474<procedure>(bag-any? predicate bag)</procedure>
475
476Returns {{#t}} if any element of {{bag}} satisfies {{predicate}}, or {{#f}}
477otherwise. Note that this differs from the SRFI 1 analogue because it does not
478return an element of the bag.
479
480<procedure>(bag-every? predicate bag)</procedure>
481
482Returns {{#t}} if every element of {{bag}} satisfies {{predicate}}, or {{#f}}
483otherwise. Note that this differs from the SRFI 1 analogue because it does not
484return an element of the bag.
485
486=== Mapping and Folding
487
488<procedure>(bag-map comparator proc bag)</procedure>
489
490Applies {{proc}} to each element of bag in arbitrary order and returns a newly
491allocated bag, created as if by (bag comparator), which contains the results of
492the applications. For example:
493
494<enscript highlight="scheme">
495(bag-map string-ci-comparator symbol->string (bag eq? 'foo 'bar 'baz))
496     => (bag string-ci-comparator "foo" "bar" "baz")
497</enscript>
498
499<procedure>(bag-for-each proc bag)</procedure>
500
501Applies {{proc}} to {{bag}} in arbitrary order, discarding the returned values.
502Returns an unspecified result.
503
504<procedure>(bag-fold proc nil bag)</procedure>
505
506Invokes {{proc}} on each member of {{bag}} in arbitrary order, passing the
507result of the previous invocation as a second argument. For the first
508invocation, {{nil}} is used as the second argument. Returns the result of the
509last invocation, or {{nil}} if there was no invocation.
510
511<procedure>(bag-filter predicate bag)</procedure>
512
513Returns a newly allocated bag with the same comparator as {{bag}}, containing
514just the elements of {{bag}} that satisfy {{predicate}}.
515
516<procedure>(bag-filter! predicate bag)</procedure>
517
518A linear update procedure that returns a bag containing just the elements of
519{{bag}} that satisfy {{predicate}}.
520
521<procedure>(bag-remove predicate bag)</procedure>
522
523Returns a newly allocated bag with the same comparator as {{bag}}, containing
524just the elements of {{bag}} that do not satisfy {{predicate}}.
525
526<procedure>(bag-remove! predicate bag)</procedure>
527
528A linear update procedure that returns a bag containing just the elements of
529{{bag}} that do not satisfy {{predicate}}.
530
531<procedure>(bag-partition predicate bag)</procedure>
532
533Returns two values: a newly allocated bag with the same comparator as {{bag}}
534that contains just the elements of {{bag}} that satisfy {{predicate}}, and
535another newly allocated bag, also with the same comparator, that contains just
536the elements of {{bag}} that do not satisfy {{predicate}}.
537
538<procedure>(bag-partition! predicate bag)</procedure>
539
540A linear update procedure that returns two bags containing the elements of bag
541that do and do not, respectively, not satisfy predicate.
542
543=== Copying and Conversion
544
545<procedure>(bag-copy bag)</procedure>
546
547Returns a newly allocated bag containing the elements of {{bag}}, and using the
548same comparator.
549
550<procedure>(bag->list bag)</procedure>
551
552Returns a newly allocated list containing the members of {{bag}} in unspecified order.
553
554<procedure>(list->bag comparator list)</procedure>
555
556Returns a newly allocated bag, created as if by {{bag}} using {{comparator}}, that
557contains the elements of {{list}}.
558
559<procedure>(list->bag! bag list)</procedure>
560
561Returns a bag that contains the elements of both {{bag}} and {{list}}.
562
563=== Subbags
564
565<procedure>(bag=? bag1 bag2 ...) </procedure>
566
567Returns {{#t}} if each bag contains the same elements.
568
569<procedure>(bag<? bag1 bag2 ...) </procedure>
570
571Returns {{#t}} if each bag other than the last is a proper subbag of the following
572bag, and {{#f}} otherwise.
573
574<procedure>(bag>? bag1 bag2 ...) </procedure>
575
576Returns {{#t}} if each bag other than the last is a proper superbag of the
577following bag, and {{#f}} otherwise.
578
579<procedure>(bag<=? bag1 bag2 ...) </procedure>
580
581Returns {{#t}} if each bag other than the last is a subbag of the following bag,
582and {{#f}} otherwise.
583
584<procedure>(bag>=? bag1 bag2 ...) </procedure>
585
586Returns {{#t}} if each bag other than the last is a superbag of the following bag,
587and {{#f}} otherwise.
588
589=== Bag-theory Operations
590
591<procedure>(bag-union bag1 bag2 ...)</procedure>
592<procedure>(bag-intersection bag1 bag2 ...)</procedure>
593<procedure>(bag-difference bag1 bag2 ...)</procedure>
594<procedure>(bag-xor bag1 bag2)</procedure>
595
596Return a newly allocated bag that is the union, intersection, asymmetric
597difference, or symmetric difference of the {{bags}}. Asymmetric difference is
598extended to more than two bags by taking the difference between the first bag
599and the union of the others. Symmetric difference is not extended beyond two
600bags.
601
602<procedure>(bag-union! bag1 bag2 ...)</procedure>
603<procedure>(bag-intersection! bag1 bag2 ...)</procedure>
604<procedure>(bag-difference! bag1 bag2 ...)</procedure>
605<procedure>(bag-xor! bag1 bag2)</procedure>
606
607Linear update procedures returning a bag that is the union, intersection,
608asymmetric difference, or symmetric difference of the {{bags}}. Asymmetric
609difference is extended to more than two bags by taking the difference between
610the first bag and the union of the others. Symmetric difference is not extended
611beyond two bags.
612
613=== Additional bag procedures
614
615<procedure>(bag-sum bag1 bag2 ...)</procedure>
616<procedure>(bag-sum! bag1 bag2)</procedure>
617
618The {{bag-sum}} procedure returns a newly allocated bag containing all the
619unique elements in all the bags, such that the count of each unique element in
620the result is equal to the sum of the counts of that element in the arguments.
621It differs from bag-union by treating identical elements as potentially
622distinct rather than attempting to match them up.
623
624The {{bag-sum!}} procedure is equivalent except that it is linear-update.
625
626<procedure>(bag-product n bag)</procedure>
627<procedure>(bag-product! n bag)</procedure>
628
629The {{bag-product}} procedure returns a newly allocated bag containing all the
630unique elements in {{bag}}, where the count of each unique element in the bag
631is equal to the count of that element in {{bag}} multiplied by {{n}}.
632
633The {{bag-product!}} procedure is equivalent except that it is linear-update.
634
635<procedure>(bag-unique-size bag)</procedure>
636
637 Returns the number of unique elements of {{bag}}.
638
639<procedure>(bag-element-count bag element)</procedure>
640
641Returns an exact integer representing the number of times that {{element}} appears in {{bag}}.
642
643<procedure>bag-for-each-unique proc bag)</procedure>
644
645Applies {{proc}} to each unique element of {{bag}} in arbitrary order, passing
646the element and the number of times it occurs in {{bag}}, and discarding the
647returned values. Returns an unspecified result.
648
649<procedure>(bag-fold-unique proc nil bag)</procedure>
650
651Invokes {{proc}} on each unique element of {{bag}} in arbitrary order, passing
652the number of occurrences as a second argument and the result of the previous
653invocation as a third argument. For the first invocation, {{nil}} is used as
654the third argument. Returns the result of the last invocation.
655
656<procedure>(bag-increment! bag element count)</procedure>
657<procedure>(bag-decrement! bag element count)</procedure>
658
659Linear update procedures that return a bag with the same elements as {{bag}}, but with the element count of element in {{bag}} increased or decreased by the exact integer {{count}} (but not less than zero).
660
661<procedure>(bag->set bag)</procedure>
662<procedure>(set->bag set)</procedure>
663<procedure>(set->bag! bag set)</procedure>
664
665The {{bag->set}} procedure returns a newly allocated set containing the unique
666elements (in the sense of the equality predicate) of {{bag}}. The {{set->bag}}
667procedure returns a newly allocated bag containing the elements of {{set}}. The
668{{set->bag!}} procedure returns a bag containing the elements of both {{bag}}
669and {{set}}. In all cases, the comparator of the result is the same as the
670comparator of the argument or arguments.
671
672<procedure>(bag->alist bag)</procedure>
673<procedure>(alist->bag comparator alist)</procedure>
674
675The {{bag->alist}} procedure returns a newly allocated alist whose keys are the unique elements of {{bag}} and whose values are the number of occurrences of each element. The {{alist->bag}} returning a newly allocated bag based on comparator, where the keys of alist specify the elements and the corresponding values of alist specify how many times they occur.
676
677== Comparators
678
679 The following comparators are used to compare sets or bags, and allow sets of
680sets, bags of sets, etc.
681
682<constant>set-comparator</constant>
683
684<constant>bag-comparator</constant>
685
686'''Note:''' that these comparators do not provide comparison procedures, as
687there is no ordering between sets or bags. It is an error to compare sets or
688bags with different element comparators.
689
690== Repository
691
692[[https://github.com/ThatGeoGuy/srfi-113|Github]]
693
694== Version History
695
696; 0.11 : CHICKEN 5 support, with fixed tests
697; 0.10 : Preliminary CHICKEN 5 support, with broken tests :(
698; 0.7 : Adds fix to (set/bag) sob-map argument order
699; 0.6 : Fix for single argument case of {{set-union}}
700; 0.5 : Removes hardcoded .so in setup
701; 0.4 : Adds standard README.org to SRFIs
702; 0.3 : Packages egg without extraneous files
703; 0.2 : Fixes setup file on Windows
704; 0.1 : Initial release.
705
706== License
707
708Copyright (C) John Cowan (2015). All Rights Reserved.
709
710Permission is hereby granted, free of charge, to any person obtaining a copy of
711this software and associated documentation files (the "Software"), to deal in
712the Software without restriction, including without limitation the rights to
713use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
714of the Software, and to permit persons to whom the Software is furnished to do
715so, subject to the following conditions:
716
717The above copyright notice and this permission notice shall be included in all
718copies or substantial portions of the Software.
719
720THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
721IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
722FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
723AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
724LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
725OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
726SOFTWARE.
Note: See TracBrowser for help on using the repository browser.