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.
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.
See the SRFI document for more information.
Constructors
Predicates
set?
setcontains?
setempty?
setdisjoint?
bag?
bagcontains?
bagempty?
bagdisjoint?
Accessors
setmember
setelementcomparator
bagmember
bagelementcomparator
Updaters
setadjoin
setadjoin!
setreplace
setreplace!
setdelete
setdelete!
setdeleteall
setdeleteall!
setsearch!
bagadjoin
bagadjoin!
bagreplace
bagreplace!
bagdelete
bagdelete!
bagdeleteall
bagdeleteall!
bagsearch!
The whole set
setsize
setfind
setcount
setany?
setevery?
bagsize
bagfind
bagcount
bagany?
bagevery?
Mapping and folding
setmap
setforeach
setfold
setfilter
setfilter!
setremove
setremove!
setpartition
setpartition!
bagmap
bagforeach
bagfold
bagfilter
bagfilter!
bagremove
bagremove!
bagpartition
bagpartition!
Copying and conversion
setcopy
set>list
list>set
list>set!
bagcopy
bag>list
list>bag
list>bag!
Subsets
set=?
set<?
set>?
set<=?
set>=?
bag=?
bag<?
bag>?
bag<=?
bag>=?
Set theory operations
setunion
setintersection
setdifference
setxor
setunion!
setintersection!
setdifference!
setxor!
bagunion
bagintersection
bagdifference
bagxor
bagunion!
bagintersection!
bagdifference!
bagxor!
Additional bag procedures
bagsum
bagsum!
bagproduct
bagproduct!
baguniquesize
bagelementcount
bagforeachunique
bagfoldunique
bagincrement!
bagdecrement!
bag>set
set>bag
set>bag!
bag>alist
alist>bag
Comparators
set
(set comparator element ...)
Returns a newly allocated empty set. The comparator argument is a SRFI 114 comparator, which is used to control and distinguish the elements of the set. The elements are used to initialize the set.
setunfold
(setunfold comparator stop? mapper successor seed)
Create 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.
bag
(bag comparator element ...)
Returns a newly allocated empty bag. The comparator argument is a SRFI 114 comparator, which is used to control and distinguish the elements of the bag. The elements are used to initialize the bag.
bagunfold
(bagunfold comparator stop? mapper successor seed)
Create 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.
set?
(set? obj)
Returns #t
if obj
is a set, and #f
otherwise.
setcontains?
(setcontains? set element)
Returns #t
if element
is a member of set
and #f
otherwise.
setempty?
(setempty? set)
Returns #t
if set
has no elements and #f
otherwise.
setdisjoint?
(setdisjoint? set1 set2)
Returns #t
if set1
and set2
have no elements in common and #f
otherwise.
bag?
(bag? obj)
Returns #t
if obj
is a bag, and #f
otherwise.
bagcontains?
(bagcontains? bag element)
Returns #t
if element
is a member of bag
and #f
otherwise.
bagempty?
(bagempty? bag)
Returns #t
if bag
has no elements and #f
otherwise.
bagdisjoint?
(bagdisjoint? bag1 bag2)
Returns #t
if bag1
and bag2
have no elements in common and #f
otherwise.
setmember
(setmember set element default)
Returns 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.
setelementcomparator
(setelementcomparator set)
Returns the comparator used to compare the elements of set
.
bagmember
(bagmember bag element default)
Returns 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.
bagelementcomparator
(bagelementcomparator bag)
Returns the comparator used to compare the elements of bag
.
#setadjoin
(setadjoin set element ...)
The setadjoin 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.
setadjoin!
(setadjoin! set element ...)
The setadjoin! procedure is the same as setadjoin, except that it is permitted to mutate and return the set argument rather than allocating a new set.
setreplace
(setreplace set element)
The setreplace 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.
setreplace!
(setreplace! set element)
The setreplace! procedure is the same assetreplace, except that it is permitted to mutate and return the set argument rather than allocating a new set.
setdelete
(setdelete set element ...)
The setdelete 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.
setdelete!
(setdelete! set element ...)
The setdelete! procedure is the same as setdelete, except that it is permitted to mutate and return the set argument rather than allocating a new set.
setdeleteall
(setdeleteall set elementlist)
The setdeleteall and setdeleteall! procedures are the same as setdelete and setdelete!, except that they accept a single argument which is a list of elements to be deleted.
setdeleteall!
(setdeleteall! set elementlist)
The setdeleteall and setdeleteall! procedures are the same as setdelete and setdelete!, except that they accept a single argument which is a list of elements to be deleted.
setsearch!
(setsearch! set element failure success)
The set is searched for element. If it is not found, then the failure procedure is tailcalled with two continuation arguments, insert and ignore, and is expected to tailcall one of them. If element is found, then the success procedure is tailcalled with the matching element of set and two continuations, update and remove, and is expected to tailcall 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 newelement obj) causes newelement 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.
bagadjoin
(bagadjoin bag element ...)
The bagadjoin 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 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 bag that does not return #t when passed to the type test procedure of the comparator.
bagadjoin!
(bagadjoin! bag element ...)
The bagadjoin! procedure is the same as bagadjoin, except that it is permitted to mutate and return the bag argument rather than allocating a new bag.
bagreplace
(bagreplace bag element)
The bagreplace procedure returns a newly allocated bag that uses the same comparator as bag and contains all the values of bag except as follows: If element is equal (in the sense of bag’s comparator) to an existing member of bag, then that member is omitted and replaced by element. If there is no such element in bag, then bag is returned unchanged.
bagreplace!
(bagreplace! bag element)
The bagreplace! procedure is the same as bagreplace, except that it is permitted to mutate and return the bag argument rather than allocating a new bag.
bagdelete
(bagdelete bag element ...)
The bagdelete procedure returns a newly allocated bag containing all the values of bag except for any that are equal (in the sense of bag’s comparator) to one or more of the elements. Any element that is not equal to some member of the bag is ignored.
bagdelete!
(bagdelete! bag element ...)
The bagdelete! procedure is the same as bagdelete, except that it is permitted to mutate and return the bag argument rather than allocating a new bag.
bagdeleteall
(bagdeleteall bag elementlist)
The bagdeleteall and bagdeleteall! procedures are the same as bagdelete and bagdelete!, except that they accept a single argument which is a list of elements to be deleted.
bagdeleteall!
(bagdeleteall! bag elementlist)
The bagdeleteall and bagdeleteall! procedures are the same as bagdelete and bagdelete!, except that they accept a single argument which is a list of elements to be deleted.
bagsearch!
(bagsearch! bag element failure success)
The bag is searched for element. If it is not found, then the failure procedure is tailcalled with two continuation arguments, insert and ignore, and is expected to tailcall one of them. If element is found, then the success procedure is tailcalled with the matching element of bag and two continuations, update and remove, and is expected to tailcall 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 newelement obj) causes newelement 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.
setsize
(setsize set)
Returns the number of elements in set as an exact integer.
setfind
(setfind predicate set failure)
Returns an arbitrarily chosen element of set that satisfies predicate, or the result of invoking failure with no arguments if there is none.
setcount
(setcount predicate set)
Returns the number of elements of set that satisfy predicate as an exact integer.
setany?
(setany? predicate set)
Returns #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.
setevery?
(setevery? predicate set)
Returns #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.
bagsize
(bagsize bag)
Returns the number of elements in bag as an exact integer.
bagfind
(bagfind predicate bag failure)
Returns an arbitrarily chosen element of bag that satisfies predicate, or the result of invoking failure with no arguments if there is none.
bagcount
(bagcount predicate bag)
Returns the number of elements of bag that satisfy predicate as an exact integer.
bagany?
(bagany? predicate bag)
Returns #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.
bagevery?
(bagevery? predicate bag)
setmap
(setmap comparator proc set)
Applies 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:
(setmap stringcicomparator symbol>string (set eq? 'foo 'bar 'baz))
=> (set stringcicomparator "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:
(setmap (lambda (x) (quotient x 2))
integercomparator
(set integercomparator 1 2 3 4 5))
=> (set integercomparator 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.
setforeach
(setforeach proc set)
Applies proc to set in arbitrary order, discarding the returned values. Returns an unspecified result.
setfold
(setfold proc nil set)
Invokes 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.
setfilter
(setfilter predicate set)
Returns a newly allocated set with the same comparator as set, containing just the elements of set that satisfy predicate.
setfilter!
(setfilter! predicate set)
A linear update procedure that returns a set containing just the elements of set that satisfy predicate.
setremove
(setremove predicate set)
Returns a newly allocated set with the same comparator as set, containing just the elements of set that do not satisfy predicate.
setremove!
(setremove! predicate set)
A linear update procedure that returns a set containing just the elements of set that do not satisfy predicate.
setpartition
(setpartition predicate set)
Returns 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.
setpartition!
(setpartition! predicate set)
A linear update procedure that returns two sets containing the elements of set that do and do not, respectively, not satisfy predicate.
bagmap
(bagmap comparator proc bag)
Applies 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:
(bagmap stringcicomparator symbol>string (bag eq? 'foo 'bar 'baz))
=> (bag stringcicomparator "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 bag constructor. For example:
(bagmap (lambda (x) (quotient x 2))
integercomparator
(bag integercomparator 1 2 3 4 5))
=> (bag integercomparator 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.
bagforeach
(bagforeach proc bag)
Applies proc to bag in arbitrary order, discarding the returned values. Returns an unspecified result.
bagfold
(bagfold proc nil bag)
Invokes 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.
bagfilter
(bagfilter predicate bag)
Returns a newly allocated bag with the same comparator as bag, containing just the elements of bag that satisfy predicate.
bagfilter!
(bagfilter! predicate bag)
A linear update procedure that returns a bag containing just the elements of bag that satisfy predicate.
bagremove
(bagremove predicate bag)
Returns a newly allocated bag with the same comparator as bag, containing just the elements of bag that do not satisfy predicate.
bagremove!
(bagremove! predicate bag)
A linear update procedure that returns a bag containing just the elements of bag that do not satisfy predicate.
bagpartition
(bagpartition predicate bag)
Returns 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.
bagpartition!
(bagpartition! predicate bag)
A linear update procedure that returns two bags containing the elements of bag that do and do not, respectively, not satisfy predicate.
setcopy
(setcopy set)
Returns a newly allocated set containing the elements of set, and using the same comparator.
set>list
(set>list set)
Returns a newly allocated list containing the members of set in unspecified order.
list>set
(list>set comparator list)
Returns 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!
(list>set! set list)
Returns a set that contains the elements of both set and list. Duplicate elements (in the sense of the equality predicate) are omitted.
bagcopy
(bagcopy bag)
Returns a newly allocated bag containing the elements of bag, and using the same comparator.
bag>list
(bag>list bag)
Returns a newly allocated list containing the members of bag in unspecified order.
list>bag
(list>bag comparator list)
Returns a newly allocated bag, created as if by bag using comparator, that contains the elements of list. Duplicate elements (in the sense of the equality predicate) are omitted.
list>bag!
(list>bag! bag list)
Returns a bag that contains the elements of both bag and list. Duplicate elements (in the sense of the equality predicate) are omitted.
set=?
(set=? set1 set2 ...)
Returns #t if each set contains the same elements.
Note: The following subset predicates do not obey the trichotomy law and therefore do not constitute a total order on sets.
set<?
(set<? set1 set2 ...)
Returns #t if each set other than the last is a proper subset of the following set, and #f otherwise.
set>?
(set>? set1 set2 ...)
Returns #t if each set other than the last is a proper superset of the following set, and #f otherwise.
set<=?
(set<=? set1 set2 ...)
Returns #t if each set other than the last is a subset of the following set, and #f otherwise.
set>=?
(set>=? set1 set2 ...)
Returns #t if each set other than the last is a superset of the following set, and #f otherwise.
bag=?
(bag=? bag1 bag2 ...)
Returns #t if each bag contains the same elements.
bag<?
(bag<? bag1 bag2 ...)
Returns #t if each bag other than the last is a proper subset of the following bag, and #f otherwise.
bag>?
(bag>? bag1 bag2 ...)
Returns #t if each bag other than the last is a proper superset of the following bag, and #f otherwise.
bag<=?
(bag<=? bag1 bag2 ...)
Returns #t if each bag other than the last is a subset of the following bag, and #f otherwise.
bag>=?
(bag>=? bag1 bag2 ...)
Returns #t if each bag other than the last is a superset of the following bag, and #f otherwise.
setunion
(setunion set1 set2 ...)
Return a newly allocated set that is the union of the sets.
setintersection
(setintersection set1 set2 ...)
Return a newly allocated set that is the intersection of the sets.
setdifference
(setdifference set1 set2 ...)
Return a newly allocated set that is the asymmetric 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.
setxor
(setxor set1 set2)
Return a newly allocated set that is the symmetric difference of the sets.
Symmetric difference is not extended beyond two sets. Elements in the result set are drawn from the first set in which they appear.
setunion!
(setunion! set1 set2 ...)
Linear update procedures returning a set that is the union of the sets.
setintersection!
(setintersection! set1 set2 ...)
Linear update procedures returning a set that is the intersection of the sets.
setdifference!
(setdifference! set1 set2 ...)
Linear update procedures returning a set that is the asymmetric 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.
setxor!
(setxor! set1 set2)
Linear update procedures returning a set that is the symmetric difference of the sets.
Symmetric difference is not extended beyond two sets. Elements in the result set are drawn from the first set in which they appear.
bagunion
(bagunion bag1 bag2 ...)
Return a newly allocated bag that is the union of the bags.
The number of equal elements in the result is the largest number of equal elements in any of the original bags.
bagintersection
(bagintersection bag1 bag2 ...)
Return a newly allocated bag that is the intersection of the bags.
The number of equal elements in the result is the smallest number of equal elements in any of the original bags.
bagdifference
(bagdifference bag1 bag2 ...)
Return a newly allocated bag that is the asymmetric 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.
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).
bagxor
(bagxor bag1 bag2)
Return a newly allocated bag that is the symmetric difference of the bags.
Symmetric difference is not extended beyond two bags. Elements in the result bag are drawn from the first bag in which they appear.
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.
bagunion!
(bagunion! bag1 bag2 ...)
Linear update procedures returning a bag that is the union of the bags.
The number of equal elements in the result is the largest number of equal elements in any of the original bags.
bagintersection!
(bagintersection! bag1 bag2 ...)
Linear update procedures returning a bag that is the intersection of the bags.
The number of equal elements in the result is the smallest number of equal elements in any of the original bags.
bagdifference!
(bagdifference! bag1 bag2 ...)
Linear update procedures returning a bag that is the asymmetric 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.
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).
bagxor!
(bagxor! bag1 bag2)
Linear update procedures returning a bag that is the symmetric difference of the bags.
Symmetric difference is not extended beyond two bags. Elements in the result bag are drawn from the first bag in which they appear.
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.
bagsum
(bagsum set1 set2 ... )
The bagsum 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 bagunion by treating identical elements as potentially distinct rather than attempting to match them up.
bagsum!
(bagsum! bag1 bag2 ... )
The bagsum! procedure is equivalent except that it is linearupdate.
bagproduct
(bagproduct n bag)
The bagproduct 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.
bagproduct!
(bagproduct! n bag)
The bagproduct! procedure is equivalent except that it is linearupdate.
baguniquesize
(baguniquesize bag)
Returns the number of unique elements of bag.
bagelementcount
(bagelementcount bag element)
Returns an exact integer representing the number of times that element appears in bag.
bagforeachunique
(bagforeachunique proc bag)
Applies 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.
bagfoldunique
(bagfoldunique proc nil bag)
Invokes 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.
bagincrement!
(bagincrement! bag element count)
Linear update procedure that returns a bag with the same elements as bag, but with the element count of element in bag increased by the exact integer count (but not less than zero).
bagdecrement!
(bagdecrement! bag element count)
Linear update procedure that returns a bag with the same elements as bag, but with the element count of element in bag decreased by the exact integer count (but not less than zero).
bag>set
(bag>set bag)
The bag>set procedure returns a newly allocated set containing the unique elements (in the sense of the equality predicate) of bag.
set>bag
(set>bag set)
The set>bag procedure returns a newly allocated bag containing the elements of set.
set>bag!
(set>bag! bag 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>alist bag)
The 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.
alist>bag
(alist>bag comparator alist)
The alist>bag returns 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.
setcomparator
These comparators are used to compare sets or bags, and allow sets of sets, bags of sets, etc.
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.
bagcomparator
These comparators are used to compare sets or bags, and allow sets of sets, bags of sets, etc.
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.