## SRFI-113: Sets and Bags

Sets 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.

## TOC »

## Installation

$ chicken-install srfi-113

or

$ chicken-install srfi-113 -test

if you want to run the tests for the egg in addition.

## SRFI Description

For a full description of this SRFI, see the full SRFI document. This documentation covers the API only.

Although this version of SRFI-113 is based on the reference implementation, there is one notable difference. As SRFI-114 comparators have been deprecated in favour of SRFI-128 comparators, this egg uses SRFI-128 comparators whenever a comparator is needed. Thus, this egg depends on SRFI-128.

## Set Procedures

### Constructors

`set``comparator``element``...`procedureReturns a newly allocated empty set. The comparator argument is a SRFI-128 comparator, which is used to control and distinguish the elements of the set. The elements are used to initialize the set.

`set-unfold``comparator``stop?``mapper``successor``seed`procedureCreate a newly allocated set as if by set using

`comparator`. If the result of applying the predicate`stop?`to`seed`is true, return the set. Otherwise, apply the procedure`mapper`to`seed`. The value that`mapper`returns is added to the set. Then get a new seed by applying the procedure successor to`seed`, and repeat this algorithm.

### Predicates

`set?``obj`procedureReturns

`#t`if`obj`is a set, and`#f`otherwise.

`set-contains?``set``element`procedureReturns

`#t`if`element`is a member of`set`and`#f`otherwise.

`set-empty?``set`procedureReturns

`#t`if`set`has no elements and`#f`otherwise.

`set-disjoint?``set1``set2`procedureReturns

`#t`if`set1`and`set2`have no elements in common and`#f`otherwise.

### Accessors

`set-member``set``element``default`procedureReturns the element of

`set`that is equal, in the sense of set's equality predicate, to`element`. If`element`is not a member of set,`default`is returned.

`set-element-comparator``set`procedureReturns the comparator used to compare the elements of

`set`.

### Updaters

`set-adjoin``set``element``...`procedureThe

`set-adjoin`procedure returns a newly allocated set that uses the same comparator as`set`and contains all the values of`set`, and in addition each`element`unless it is already equal (in the sense of the comparator) to one of the existing or newly added members. It is an error to add an element to`set`that does not return`#t`when passed to the type test procedure of the comparator.

`set-adjoin!``set``element``...`procedureThe

`set-adjoin!`procedure is the same as`set-adjoin`, except that it is permitted to mutate and return the`set`argument rather than allocating a new set.

`set-replace``set``element`procedureThe

`set-replace`procedure returns a newly allocated set that uses the same comparator as`set`and contains all the values of`set`except as follows: If`element`is equal (in the sense of`set`'s comparator) to an existing member of`set`, then that member is omitted and replaced by`element`. If there is no such element in`set`, then`set`is returned unchanged.

`set-replace!``set``element`procedureThe

`set-replace!`procedure is the same as`set-replace`, except that it is permitted to mutate and return the`set`argument rather than allocating a new set.

`set-delete``set``element``...`procedure`set-delete!``set``element``...`procedure`set-delete-all``set``element-list`procedure`set-delete-all!``set``element-list`procedureThe

`set-delete`procedure returns a newly allocated set containing all the values of`set`except for any that are equal (in the sense of`set`'s comparator) to one or more of the elements. Any`element`that is not equal to some member of the set is ignored.The

`set-delete!`procedure is the same as`set-delete`, except that it is permitted to mutate and return the`set`argument rather than allocating a new set.The

`set-delete-all`and`set-delete-all!`procedures are the same as`set-delete`and`set-delete!`, except that they accept a single argument which is a list of elements to be deleted.

`set-search!``set``element``failure``success`procedureThe

`set`is searched for element. If it is not found, then the`failure`procedure is tail-called with two continuation arguments,`insert`and`ignore`, and is expected to tail-call one of them. If`element`is found, then the`success`procedure is tail-called with the matching element of`set`and two continuations,`update`and`remove`, and is expected to tail-call one of them.The effects of the continuations are as follows (where obj is any Scheme object):

- Invoking
`(insert obj)`causes`element`to be inserted into`set`. - Invoking
`(ignore obj)`causes`set`to remain unchanged. - Invoking
`(update new-element obj)`causes`new-element`to be inserted into`set`in place of`element`. - Invoking
`(remove obj)`causes the matching element of`set`to be removed from it.

In all cases, two values are returned: the possibly updated

`set`and`obj`.- Invoking

### The Whole Set

`set-size``set`procedureReturns the number of elements in

`set`as an exact integer.

`set-find``predicate``set``failure`procedureReturns an arbitrarily chosen element of

`set`that satisfies`predicate`, or the result of invoking`failure`with no arguments if there is none.

`set-count``predicate``set`procedureReturns the number of elements of

`set`that satisfy`predicate`as an exact integer.

`set-any?``predicate``set`procedureReturns

`#t`if any element of`set`satisfies`predicate`, or`#f`otherwise. Note that this differs from the SRFI 1 analogue because it does not return an element of the set.

`set-every?``predicate``set`procedureReturns

`#t`if every element of`set`satisfies`predicate`, or`#f`otherwise. Note that this differs from the SRFI 1 analogue because it does not return an element of the set.

### Mapping and Folding

`set-map``comparator``proc``set`procedureApplies

`proc`to each element of set in arbitrary order and returns a newly allocated set, created as if by (set comparator), which contains the results of the applications. For example:(set-map string-ci-comparator symbol->string (set eq? 'foo 'bar 'baz)) => (set string-ci-comparator "foo" "bar" "baz")

Note that, when

`proc`defines a mapping that is not 1:1, some of the mapped objects may be equivalent in the sense of`comparator`'s equality predicate, and in this case duplicate elements are omitted as in the`set`constructor. For example:(set-map (lambda (x) (quotient x 2)) integer-comparator (set integer-comparator 1 2 3 4 5)) => (set integer-comparator 0 1 2)

If the elements are the same in the sense of

`eqv?`, it is unpredictable which one will be preserved in the result.

`set-for-each``proc``set`procedureApplies

`proc`to`set`in arbitrary order, discarding the returned values. Returns an unspecified result.

`set-fold``proc``nil``set`procedureInvokes

`proc`on each member of`set`in arbitrary order, passing the result of the previous invocation as a second argument. For the first invocation,`nil`is used as the second argument. Returns the result of the last invocation, or`nil`if there was no invocation.

`set-filter``predicate``set`procedureReturns a newly allocated set with the same comparator as

`set`, containing just the elements of`set`that satisfy`predicate`.

`set-filter!``predicate``set`procedureA linear update procedure that returns a set containing just the elements of

`set`that satisfy`predicate`.

`set-remove``predicate``set`procedureReturns a newly allocated set with the same comparator as

`set`, containing just the elements of`set`that do not satisfy`predicate`.

`set-remove!``predicate``set`procedureA linear update procedure that returns a set containing just the elements of

`set`that do not satisfy`predicate`.

`set-partition``predicate``set`procedureReturns two values: a newly allocated set with the same comparator as

`set`that contains just the elements of`set`that satisfy`predicate`, and another newly allocated set, also with the same comparator, that contains just the elements of`set`that do not satisfy`predicate`.

`set-partition!``predicate``set`procedureA linear update procedure that returns two sets containing the elements of set that do and do not, respectively, not satisfy predicate.

### Copying and Conversion

`set-copy``set`procedureReturns a newly allocated set containing the elements of

`set`, and using the same comparator.

`set->list``set`procedureReturns a newly allocated list containing the members of

`set`in unspecified order.

`list->set``comparator``list`procedureReturns a newly allocated set, created as if by

`set`using`comparator`, that contains the elements of`list`. Duplicate elements (in the sense of the equality predicate) are omitted.

`list->set!``set``list`procedureReturns a set that contains the elements of both

`set`and`list`. Duplicate elements (in the sense of the equality predicate) are omitted.

### Subsets

**Note:** The following three predicates do not obey the trichotomy law and therefore do not constitute a total order on sets.

`set=?``set1``set2``...`procedureReturns

`#t`if each set contains the same elements.

`set<?``set1``set2``...`procedureReturns

`#t`if each set other than the last is a proper subset of the following set, and`#f`otherwise.

`set>?``set1``set2``...`procedureReturns

`#t`if each set other than the last is a proper superset of the following set, and`#f`otherwise.

`set<=?``set1``set2``...`procedureReturns

`#t`if each set other than the last is a subset of the following set, and`#f`otherwise.

`set>=?``set1``set2``...`procedureReturns

`#t`if each set other than the last is a superset of the following set, and`#f`otherwise.

### Set-theory Operations

`set-union``set1``set2``...`procedure`set-intersection``set1``set2``...`procedure`set-difference``set1``set2``...`procedure`set-xor``set1``set2`procedureReturn a newly allocated set that is the union, intersection, asymmetric difference, or symmetric difference of the

`sets`. 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.

`set-union!``set1``set2``...`procedure`set-intersection!``set1``set2``...`procedure`set-difference!``set1``set2``...`procedure`set-xor!``set1``set2`procedureLinear update procedures returning a set that is the union, intersection, asymmetric difference, or symmetric difference of the

`sets`. 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.

## Bag Procedures

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. It is an error for a single procedure to be invoked on bags with different comparators.

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. 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 `bag-union`, `bag-intersection`, `bag-difference`, and `bag-xor` procedures (and their linear update analogues) behave as follows when both bags contain elements that are equal in the sense of the bags' comparator:

- For
`bag-union`, the number of equal elements in the result is the largest number of equal elements in any of the original bags. - For
`bag-intersection`, the number of equal elements in the result is the smallest number of equal elements in any of the original bags. - 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). - 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.

### Constructors

`bag``comparator``element``...`procedureReturns a newly allocated empty bag. The comparator argument is a SRFI-128 comparator, which is used to control and distinguish the elements of the bag. The elements are used to initialize the bag.

`bag-unfold``comparator``stop?``mapper``successor``seed`procedureCreate a newly allocated bag as if by bag using

`comparator`. If the result of applying the predicate`stop?`to`seed`is true, return the bag. Otherwise, apply the procedure`mapper`to`seed`. The value that`mapper`returns is added to the bag. Then get a new seed by applying the procedure successor to`seed`, and repeat this algorithm.

### Predicates

`bag?``obj`procedureReturns

`#t`if`obj`is a bag, and`#f`otherwise.

`bag-contains?``bag``element`procedureReturns

`#t`if`element`is a member of`bag`and`#f`otherwise.

`bag-empty?``bag`procedureReturns

`#t`if`bag`has no elements and`#f`otherwise.

`bag-disjoint?``bag1``bag2`procedureReturns

`#t`if`bag1`and`bag2`have no elements in common and`#f`otherwise.

### Accessors

`bag-member``bag``element``default`procedureReturns the element of

`bag`that is equal, in the sense of bag's equality predicate, to`element`. If`element`is not a member of bag,`default`is returned.

`bag-element-comparator``bag`procedureReturns the comparator used to compare the elements of

`bag`.

### Updaters

`bag-adjoin``bag``element``...`procedureThe

`bag-adjoin`procedure returns a newly allocated bag that uses the same comparator as`bag`and contains all the values of`bag`, and in addition each`element`. It is an error to add an element to`bag`that does not return`#t`when passed to the type test procedure of the comparator.

`bag-adjoin!``bag``element``...`procedureThe

`bag-adjoin!`procedure is the same as`bag-adjoin`, except that it is permitted to mutate and return the`bag`argument rather than allocating a new bag.

`bag-replace``bag``element`procedureThe

`bag-replace`procedure returns a newly allocated bag that uses the same comparator as`bag`and contains all the values of`bag`. If there is no such element in`bag`, then`bag`is returned unchanged.

`bag-replace!``bag``element`procedureThe

`bag-replace!`procedure is the same as`bag-replace`, except that it is permitted to mutate and return the`bag`argument rather than allocating a new bag.

`bag-delete``bag``element``...`procedure`bag-delete!``bag``element``...`procedure`bag-delete-all``bag``element-list`procedure`bag-delete-all!``bag``element-list`procedureThe

`bag-delete`procedure returns a newly allocated bag containing all the values of`bag`Any`element`that is not equal to some member of the bag is ignored.The

`bag-delete!`procedure is the same as`bag-delete`, except that it is permitted to mutate and return the`bag`argument rather than allocating a new bag.The

`bag-delete-all`and`bag-delete-all!} procedures are the same as {{bag-delete`and`bag-delete!`, except that they accept a single argument which is a list of elements to be deleted.

`bag-search!``bag``element``failure``success`procedureThe

`bag`is searched for element. If it is not found, then the`failure`procedure is tail-called with two continuation arguments,`insert`and`ignore`, and is expected to tail-call one of them. If`element`is found, then the`success`procedure is tail-called with the matching element of`bag`and two continuations,`update`and`remove`, and is expected to tail-call one of them.The effects of the continuations are as follows (where obj is any Scheme object):

- Invoking
`(insert obj)`causes`element`to be inserted into`bag`. - Invoking
`(ignore obj)`causes`bag`to remain unchanged. - Invoking
`(update new-element obj)`causes`new-element`to be inserted into`bag`in place of`element`. - Invoking
`(remove obj)`causes the matching element of`bag`to be removed from it.

In all cases, two values are returned: the possibly updated

`bag`and`obj`.- Invoking

### The Whole bag

`bag-size``bag`procedureReturns the number of elements in

`bag`as an exact integer.

`bag-find``predicate``bag``failure`procedureReturns an arbitrarily chosen element of

`bag`that satisfies`predicate`, or the result of invoking`failure`with no arguments if there is none.

`bag-count``predicate``bag`procedureReturns the number of elements of

`bag`that satisfy`predicate`as an exact integer.

`bag-any?``predicate``bag`procedureReturns

`#t`if any element of`bag`satisfies`predicate`, or`#f`otherwise. Note that this differs from the SRFI 1 analogue because it does not return an element of the bag.

`bag-every?``predicate``bag`procedureReturns

`#t`if every element of`bag`satisfies`predicate`, or`#f`otherwise. Note that this differs from the SRFI 1 analogue because it does not return an element of the bag.

### Mapping and Folding

`bag-map``comparator``proc``bag`procedureApplies

`proc`to each element of bag in arbitrary order and returns a newly allocated bag, created as if by (bag comparator), which contains the results of the applications. For example:(bag-map string-ci-comparator symbol->string (bag eq? 'foo 'bar 'baz)) => (bag string-ci-comparator "foo" "bar" "baz")

`bag-for-each``proc``bag`procedureApplies

`proc`to`bag`in arbitrary order, discarding the returned values. Returns an unspecified result.

`bag-fold``proc``nil``bag`procedureInvokes

`proc`on each member of`bag`in arbitrary order, passing the result of the previous invocation as a second argument. For the first invocation,`nil`is used as the second argument. Returns the result of the last invocation, or`nil`if there was no invocation.

`bag-filter``predicate``bag`procedureReturns a newly allocated bag with the same comparator as

`bag`, containing just the elements of`bag`that satisfy`predicate`.

`bag-filter!``predicate``bag`procedureA linear update procedure that returns a bag containing just the elements of

`bag`that satisfy`predicate`.

`bag-remove``predicate``bag`procedureReturns a newly allocated bag with the same comparator as

`bag`, containing just the elements of`bag`that do not satisfy`predicate`.

`bag-remove!``predicate``bag`procedureA linear update procedure that returns a bag containing just the elements of

`bag`that do not satisfy`predicate`.

`bag-partition``predicate``bag`procedureReturns two values: a newly allocated bag with the same comparator as

`bag`that contains just the elements of`bag`that satisfy`predicate`, and another newly allocated bag, also with the same comparator, that contains just the elements of`bag`that do not satisfy`predicate`.

`bag-partition!``predicate``bag`procedureA linear update procedure that returns two bags containing the elements of bag that do and do not, respectively, not satisfy predicate.

### Copying and Conversion

`bag-copy``bag`procedureReturns a newly allocated bag containing the elements of

`bag`, and using the same comparator.

`bag->list``bag`procedureReturns a newly allocated list containing the members of

`bag`in unspecified order.

`list->bag``comparator``list`procedureReturns a newly allocated bag, created as if by

`bag`using`comparator`, that contains the elements of`list`.

`list->bag!``bag``list`procedureReturns a bag that contains the elements of both

`bag`and`list`.

### Subbags

`bag=?``bag1``bag2``...`procedureReturns

`#t`if each bag contains the same elements.

`bag<?``bag1``bag2``...`procedureReturns

`#t`if each bag other than the last is a proper subbag of the following bag, and`#f`otherwise.

`bag>?``bag1``bag2``...`procedureReturns

`#t`if each bag other than the last is a proper superbag of the following bag, and`#f`otherwise.

`bag<=?``bag1``bag2``...`procedureReturns

`#t`if each bag other than the last is a subbag of the following bag, and`#f`otherwise.

`bag>=?``bag1``bag2``...`procedureReturns

`#t`if each bag other than the last is a superbag of the following bag, and`#f`otherwise.

### Bag-theory Operations

`bag-union``bag1``bag2``...`procedure`bag-intersection``bag1``bag2``...`procedure`bag-difference``bag1``bag2``...`procedure`bag-xor``bag1``bag2`procedureReturn a newly allocated bag that is the union, intersection, asymmetric difference, or symmetric difference of the

`bags`. Asymmetric difference is extended to more than two bags by taking the difference between the first bag and the union of the others. Symmetric difference is not extended beyond two bags.

`bag-union!``bag1``bag2``...`procedure`bag-intersection!``bag1``bag2``...`procedure`bag-difference!``bag1``bag2``...`procedure`bag-xor!``bag1``bag2`procedureLinear update procedures returning a bag that is the union, intersection, asymmetric difference, or symmetric difference of the

`bags`. Asymmetric difference is extended to more than two bags by taking the difference between the first bag and the union of the others. Symmetric difference is not extended beyond two bags.

### Additional bag procedures

`bag-sum``bag1``bag2``...`procedure`bag-sum!``bag1``bag2`procedureThe

`bag-sum`procedure returns a newly allocated bag containing all the unique elements in all the bags, such that the count of each unique element in the result is equal to the sum of the counts of that element in the arguments. It differs from bag-union by treating identical elements as potentially distinct rather than attempting to match them up.The

`bag-sum!`procedure is equivalent except that it is linear-update.

`bag-product``n``bag`procedure`bag-product!``n``bag`procedureThe

`bag-product`procedure returns a newly allocated bag containing all the unique elements in`bag`, where the count of each unique element in the bag is equal to the count of that element in`bag`multiplied by`n`.The

`bag-product!`procedure is equivalent except that it is linear-update.

`bag-unique-size``bag`procedureReturns the number of unique elements of {{bag}}.

`bag-element-count``bag``element`procedureReturns an exact integer representing the number of times that

`element`appears in`bag`.

`bag-for-each-unique`procedureApplies

`proc`to each unique element of`bag`in arbitrary order, passing the element and the number of times it occurs in`bag`, and discarding the returned values. Returns an unspecified result.

`bag-fold-unique``proc``nil``bag`procedureInvokes

`proc`on each unique element of`bag`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,`nil`is used as the third argument. Returns the result of the last invocation.

`bag-increment!``bag``element``count`procedure`bag-decrement!``bag``element``count`procedureLinear 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).

`bag->set``bag`procedure`set->bag``set`procedure`set->bag!``bag``set`procedureThe

`bag->set`procedure returns a newly allocated set containing the unique elements (in the sense of the equality predicate) of`bag`. The`set->bag`procedure returns a newly allocated bag containing the elements of`set`. The`set->bag!`procedure returns a bag containing the elements of both`bag`and`set`. In all cases, the comparator of the result is the same as the comparator of the argument or arguments.

`bag->alist``bag`procedure`alist->bag``comparator``alist`procedureThe

`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.

## Comparators

The following comparators are used to compare sets or bags, and allow sets of

sets, bags of sets, etc.

`set-comparator`constant

`bag-comparator`constant**Note:**that these comparators do not provide comparison procedures, as there is no ordering between sets or bags. It is an error to compare sets or bags with different element comparators.

## Non-standard Extensions

As of version 0.15, this egg also provides CHICKEN-specific read and print syntax. You can use it as follows:

(define my-set #!set(1 2 3)) (set-union #!set(1 2 3) #!set(2 3 4)) ;=> #!set(1 2 3 4) (define my-bag #!bag(1 1 2 2 3 4)) #!bag(1 1 2 2 3 4) ;=> #!bag(1 1 2 2 3 4)

`set-sob-read-syntax-comparator!``comparator`procedureSets the comparator used when using read-syntax to declare a set or bag. Defaults to

`(make-default-comparator)`.

## Repository

## Version History

- 1.1
- Fix broken S-expr from dyadic-sob<? (bad merge?)
- 1.0
- Fix pure-subset comparison, dyadic-sob<? and dyadic-sob>? (thanks shirok) [BROKEN]
- 0.15
- Adds read & printer syntax, as well as
`set-sob-read-syntax-comparator!` - 0.14
- Fixes tests
- 0.13
- Adds srfi-113.scm to .meta file (for CHICKEN 4)
- 0.12
- Adds .egg file to .meta list (for CHICKEN 4)
- 0.11
- CHICKEN 5 support, with fixed tests
- 0.10
- Preliminary CHICKEN 5 support, with broken tests :(
- 0.7
- Adds fix to (set/bag) sob-map argument order
- 0.6
- Fix for single argument case of
`set-union` - 0.5
- Removes hardcoded .so in setup
- 0.4
- Adds standard README.org to SRFIs
- 0.3
- Packages egg without extraneous files
- 0.2
- Fixes setup file on Windows
- 0.1
- Initial release.

## License

Copyright (C) John Cowan (2015). All Rights Reserved.

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:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

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.