289: Unordered sets and bags289: Unordered sets and bagsby Wolfgang Corcoran-Mathe (text and test suite), Peter McGoron (sample implementation), and John Cowan (author of SRFI 113)
This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-289@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
Sets and bags (also known as multisets) are unordered collections that contain only objects of a type given by a collection’s SRFI 128 comparator. Every element of a set is unique (in the sense of the set’s comparator), but bags can contain any number of duplicate elements. This SRFI is a revision of SRFI 113 that fixes several infelicities and is more consistent with related SRFIs.
Should bag-delete-all
and its relatives be renamed? In the presence of duplicate
elements, “all” is ambiguous: it could be understood to refer to
the elements of the bag, rather than the elements of the list
argument. The procedure removes at most one element from the
bag for each element in its list argument, e.g.
(bag->list
(bag-delete-all (bag real-comparator 1 2 2 3) '(2)))
⇒ (1 2 3),but its name might lead you to expect
(bag->list
(bag-delete-all (bag real-comparator 1 2 2 3) '(2)))
⇒ (1 3).This SRFI is an elucidated revision of John Cowan’s SRFI 113. John’s post-finalization notes to that SRFI have been incorporated, and some underspecified forms and confusing details have been fixed. Bag procedures specifications are given in full, whereas in SRFI 113 they were mostly defined by analogy. In the process of writing these out, several contradictions were caught and corrected. I hope that the result of this editorial work is a SRFI that is clearer and more complete than its predecessor.
A confusing subtlety of SRFI 113 is its occasional use of
multiple notions of element equality.
Several SRFI 113 procedures
refer to elements that are equal in the sense of a set’s (or
bag’s) comparator, but different in some other sense, implicitly
that of eqv?. This is strange, considering that a
set or bag may use eqv? as its equality predicate.
With sets, the layering of multiple kinds of equality leads to
tricky implementation details and the presence of forms (like
set-replace) that are trivial unless
other kinds of equality is relevant. With bags, the layering
is completely unworkable, since there is no guarantee that a bag
will store multiple equal elements.
This SRFI eliminates this problem by using only one notion of element equality: that given by a collection’s comparator. This simplifies things quite a bit and gives us something much closer to the mathematical concepts of set and multiset. On the downside, it is a breaking change from SRFI 113.
Most of the new names added by this SRFI are aliases of SRFI 113
forms whose original names I considered confusing. The
exceptions are
set-accumulate and
bag-accumulate, which
are modeled on oset-accumulate from
SRFI 153, and the pop
procedures which are based on hashmap-pop from
SRFI 146.
Some forms specified by SRFI 113 are deprecated in this SRFI. A few irreparable forms have been removed. The following list gives some reasons for these changes.
set-memberbag-memberThese accessors are coherent but fairly useless. Unless you are using multiple notions of equality (which is itself deprecated usage), they simply return one of their arguments. Which depends on whether the collection argument contains the given element.
set-replaceset-replace!bag-replace (removed)bag-replace! (removed)Like the member procedures, replace
is a trivial
operation unless the notion of element equality is being
abused. bag-replace was underspecified; its
intended semantics are a mystery, given that it may be
impossible to replace a specific “copy” of an element that
appears multiple times. It has been removed.
set-search!bag-search!These complex procedures can be difficult both to implement and to use. They also iterate over a collection while simultaneously building a copy of it, which can entail unexpected performance costs when only the iteration is needed.
list->set!list->bag!These were arguably miscategorized as conversions.
I prefer the aliases set-adjoin-all! and
bag-adjoin-all!.
The effective exploitation of his powers of abstraction must be regarded as one of the most vital activities of a competent programmer.
— Edsger W. Dijkstra, The Humble Programmer (1972)
There is some question whether we should use sets or bags in our
code instead of more concrete types like hash-tables or binary
trees. My answer is we should, for the same reason we often
use map instead of
explicit recursion: it makes our intentions clearer. Sets and bags
have clear semantics which may be vaguely familiar to
most programmers from set-theory studies. The meaning of a
hash-table in a given program, on the other hand, is not obvious:
it may act as a set, bag, or something else entirely. The
only way to know is to read every part of the program that
interacts with it. Judicious use of abstract types like those
presented in this SRFI can make programs easier to
understand.
The terms must
, may
, etc., though not capitalized
in this document, should be interpreted according to
RFC 2119.
This SRFI provides two Scheme libraries,
(srfi 289 set) and (srfi 289 bag).
Theses libraries may be provided under the usual aliases, e.g.
(srfi :289 set), (srfi srfi-289 set),
etc.
Sets and bags form new types as if they
were created by define-record-type (R7RS
§5.5). Values of both types use a specific
SRFI 128 comparator and
contain elements satisfying that comparator’s
type-test predicate. Sets never contains duplicate elements (in
the sense of their comparator’s equality predicate). Bags, on
the other hand, may contain duplicates, but they are not required
to store each duplicate object explicitly.
Except as noted, whenever two elements of a set or bag are equal
in the sense of the collection’s comparator, those elements
are considered to be the same for all purposes. For
example, since the two strings in the following expression are
the same according to the new set’s comparator, it is unspecified
which one set adds:
(let ((comp (make-comparator string? string=? #f string-hash))
(s1 (string-copy "hello"))
(s2 (string-copy "hello")))
(eqv? s1 (car (set->list (set comp s1 s2)))))
⇒ #t or #fThe procedures of this SRFI that do not observe this rule are deprecated.
The argument-naming conventions of this document are consistent with those of the R7RS. The following naming conventions also imply type restrictions:
bag?)set?)Many procedures in this SRFI begin with a paragraph describing further argument restrictions. If any of the requirements of these paragraphs are violated, it is an error.
Like several other SRFIs, this SRFI defines linear-update procedures, all of whose names end in ‘!’. These procedures are allowed, but not required, to side-effect one of their arguments in order to construct their results. (Unlike similarly-named procedures in the Scheme Reports, these forms return meaningful values.) An implementation may implement linear-update procedures as side-effecting or side-effect-free procedures, depending on what makes the most sense for the underlying representation.
A linear-update procedure is permitted to mutate one of its arguments, and it is an error to reference that value after the procedure has been invoked on it. For example, the following is an error:
(let* ((s (set (make-equal-comparator) 1 2 3))
(s* (set-adjoin! s 4)))
(set->list s))This, however, is well-defined:
(let ((s (set (make-equal-comparator) 1 2 3)))
(set->list (set-adjoin! s 4)))In other words, a user of a linear-update procedures should write in a functional style, but should additionally be sure that there are no “live” references to the value that the procedure is allowed to mutate when the procedure is called.
This section is informational.
Linear-update procedures are confusing and there is every
reason to believe they will be misused. The original test suite
for SRFI 113, for example, incorrectly uses linear-update
forms like
set-adjoin! as
simple mutators. Despite this, they have been retained in the
interest of backward compatibility with SRFI 113 and alignment
with the R7RS Large project’s decision to preserve linear-update
forms in their specifications.
By encompassing both transient and persistent set
implementations, SRFI 113 created a problem for programmers
wishing to write efficient portable code. Should they assume a
persistent implementation and use only functional forms (e.g. set-adjoin), or should they
use the linear-update alternatives, on the assumption of a
transient implementation? The best answer is to have different
interfaces for mutable and immutable collections. But, stuck with a
single interface as we are, a good approach may be to use the
linear-update forms exclusively in portable code.
Hash-table implementations of sets and bags are very
common, and they perform best with linear-update code. Under a
persistent implementation, on the other hand, the linear-update
forms will likely be aliases for their functional counterparts,
so code using them should incur no extra performance costs.
A comparator used by a set or bag must provide an equality procedure. (See SRFI 128.) Implementations of this SRFI may additionally require that comparators provide a hash procedure, but they must not require an ordering procedure.
The examples in this SRFI are non-normative: if an example
contradicts the specification text, the text is right.
They use comparators (especially real-comparator)
defined in SRFI 162.
The identifiers in this section are exported by the
(srfi 289 set) library.
(set comparator element …) →
set
It is an error if any of the element arguments does not satisfy comparator’s type-test predicate.
Returns a newly allocated set using comparator and containing the given elements.
(set->list (set real-comparator 1 2 3))
⇒ (1 3 2) ; order unspecified
(set->list (set eqv-comparator 'foo 'foo 'bar))
⇒ (foo bar) ; order unspecified(set-unfold stop? mapper
successor seed
comparator) → set
seed may be any object. stop? is a predicate taking a single value of seed’s type. mapper and successor are procedures taking a single value of seed’s type and returning a single value. It is an error if mapper returns a value that does not satisfy comparator’s type-test predicate.
Returns a newly allocated set using comparator. The elements of this set are generated by the following process:
The new set is initialized to the empty set.
stop? is applied to the current seed. If the result is true, then the unfolding process halts and the new set is returned. Otherwise, the process continues.
The result of applying mapper to the current seed is added to the set.
successor is applied to the current seed to produce the next seed. Unfolding continues with step 2.
If stop?, mapper, or successor
mutate the values returned by mapper, then
set-unfold returns a set whose contents are
unspecified. If multiple returns occur from
set-unfold, the values returned by earlier returns
are not mutated.
(set->list
(set-unfold (lambda (i) (= i 4))
(lambda (i) (make-string i #\a))
(lambda (i) (+ i 1))
0
string-comparator))
⇒ ("a" "aaa" "aa" "") ; order unspecified(set-accumulate proc comparator
seed1 seed2
…) → set
The seeds may be any objects. proc must accept n arguments, where n is the number of seeds, and return n + 1 values, the first of which must satisfy comparator’s type-test predicate.
Similar to set-unfold,
except that a single procedure controls the unfolding of a new
set. Let n be the number of seeds:
The new set is initialized to the empty set.
Proc is applied to a procedure
terminate and the seeds, in that
order. If terminate is invoked in tail context
on any number of arbitrary values, then the process halts
and the new set along with those values are returned from
set-accumulate.
Otherwise, proc is expected to return n + 1 values: a new set element and n new seeds. The element is added to the new set and the process continues at step two with the new seeds.
It is an error for the number of seeds to vary between steps
of the unfolding process. If proc mutates values
returned by earlier invocations of proc, then
set-accumulate returns a set whose contents are
unspecified. If multiple returns occur from
set-accumulate, the values returned by earlier
returns are not mutated.
(let-values (((set sym)
(set-accumulate (lambda (terminate i)
(if (> i 3)
(terminate 'finished)
(values i (+ i 1))))
(make-real-comparator)
1)))
(values (set->list set) sym))
⇒ (1 2 3) ; or some permutation thereof
finished(set? obj) → boolean
Returns #t if obj is a set, and
#f otherwise.
(set-contains? set element) →
boolean
Returns #t if element is a member of
set and #f otherwise.
(set-contains? (set real-comparator 2 4 6) 2) ⇒ #t
(set-contains? (set real-comparator 1 3 5) 2) ⇒ #f(set-empty? set) → boolean
Returns #t if set has no elements and
#f otherwise.
(set-empty? (set real-comparator)) ⇒ #t
(set-empty? (set real-comparator 1 3 5)) ⇒ #f(set-disjoint? set1
set2) → boolean
It is an error if the comparator
of set1 is not the same (in the sense
of eqv?) as that of set2.
Returns #t if set1 and
set2 have no elements in common and
#f otherwise.
(set-disjoint? (set real-comparator 1 3 5)
(set real-comparator 2 4 6))
⇒ #t
(set-disjoint? (set real-comparator 1 3 4)
(set real-comparator 2 4 6))
⇒ #f[Deprecated] (set-member set
element default) → obj
Default may be any Scheme object.
Returns the element of set that is equal (in the sense of set’s comparator) to element. If element is not a member of set, default is returned instead.
This section is informational.
Unless a notion of element equality other than that given by set’s comparator is relevant, this procedure is equivalent to
(lambda (set element default)
(if (set-contains? set element) element default))(set-element-comparator set) →
comparator
Returns the comparator used to compare the elements of set.
(set-adjoin set element …)
→ set
Returns a newly allocated set that uses the same comparator as set and that contains all its elements in addition to the element arguments.
(set->list (set-adjoin (set real-comparator 0) 1 2))
⇒ (1 2 0) ; order unspecified(set-adjoin! set element …)
→ set
A linear-update variant of
set-adjoin. It is
allowed, but not required, to mutate set to produce
its result.
(set-adjoin-all set list)
→ set
Every element of list must satisfy set’s comparator’s type-test predicate.
Returns a newly allocated set that uses the same comparator as set and that contains all its elements in addition to the elements of list.
(set->list (set-adjoin-all (set real-comparator 0)
'(0 1 2)))
⇒ (1 2 0) ; order unspecified(set-adjoin-all! set list)
→ set
A linear-update variant of
set-adjoin-all. It is
allowed, but not required, to mutate set to produce
its result.
[Deprecated] (set-replace set
element) → set
Returns a newly allocated set that uses the same comparator as set and contains all its elements 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.
This section is informational.
Strictly speaking, this procedure does nothing. It only makes sense to use when some notion of element equality other than that defined by set’s comparator is in play.
[Deprecated] (set-replace! set
element) → set
A linear-update variant of
set-replace. It is
allowed, but not required, to mutate set to produce
its result.
(set-delete set element …)
→ set
Returns a newly allocated set containing all the elements of set except for any that are equal (in the sense of set’s comparator) to one or more of the elements.
(set->list (set-delete (set real-comparator 1 2 3) 2 1))
⇒ (3)
(set->list (set-delete (set real-comparator 4 6) 2 3))
⇒ (4 6) ; order unspecified(set-delete! set element …)
→ set
A linear-update variant of
set-delete. It is
allowed, but not required, to mutate set to produce
its result.
(set-delete-all set
list) → set
It is an error if any element of list does not satisfy the type-test predicate of set’s comparator.
Returns a newly allocated set containing all the elements of set except for any that are equal (in the sense of set’s comparator) to one or more elements of list.
(set->list (set-delete-all (set real-comparator 1 2 3)
'(2 1)))
⇒ (3)(set-delete-all! set
list) → set
A linear-update variant of
set-delete-all. It
is allowed, but not required, to mutate set to
produce its result.
[Deprecated] (set-search! set
element failure
success)
The 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.
(set-pop set [failure])
→ obj …
If failure is provided, it must be a procedure accepting zero arguments. Otherwise, it is an error.
Chooses an arbitrary element x of set and returns two values: a newly allocated set using the same comparator as set and containing all of its elements except x, and x itself. If set is empty and failure is provided, then failure is invoked in tail context on zero arguments. Otherwise, it is an error.
(let-values (((rest x) (set-pop (set real-comparator 1 2 3))))
(values (set->list rest) x))
⇒ (1 3) ; possibly
2(set-pop! set [failure])
→ obj …
Linear-update variant of
set-pop which is allowed,
but not required, to mutate set to produce its
result.
(set-size set) → exact-integer
Returns the number of elements in set.
(set-size (set real-comparator 1 2)) ⇒ 2
(set-size (set real-comparator)) ⇒ 0(set-find pred set
failure) → obj …
Returns an arbitrarily-chosen element of set that satisfies pred. If no such element exists, then failure is invoked in tail context on zero arguments.
(set-find even?
(set real-comparator 1 2 3 4)
(lambda () #f))
⇒ 2 ; or 4
(set-find negative?
(set real-comparator 1 2 3 4)
(lambda () #f))
⇒ #f(set-count pred set) →
exact-integer
Returns the number of elements of set that satisfy pred.
(set-count even? (set real-comparator 1 2 3))
⇒ 1(set-any? pred set) →
boolean
Returns #t if any element of set
satisfies pred. Otherwise, returns
#f.
(set-any? even? (set real-comparator 1 2 3 4))
⇒ #t
(set-any? negative? (set real-comparator 1 2 3 4))
⇒ #f(set-every? pred set) →
boolean
Returns #t if every element of set
satisfies pred. Otherwise, returns
#f.
(set-every? integer? (set real-comparator 1 2 3 4))
⇒ #t
(set-every? even? (set real-comparator 1 2 3 4))
⇒ #f(set-map proc comparator
set) → set
Proc must be a procedure accepting one argument, an element of set, and returning one value which must satisfy comparator’s type-test predicate.
Applies proc to each element of set in
an arbitrary order and returns a newly allocated set, created
as if by (set comparator), which
contains the results of the applications.
(set-map symbol->string
string-comparator
(set eqv-comparator 'foo 'bar 'baz))
≡ (set string-comparator "foo" "bar" "baz")
(set-map (lambda (x) (quotient x 2))
real-comparator
(set real-comparator 1 2 3 4 5))
≡ (set real-comparator 0 1 2)(set-for-each proc set) →
unspecified
Proc must be a procedure accepting one argument, an element of set.
Applies proc to the elements of set in an arbitrary order, discarding the returned values. Returns an unspecified result.
(let ((sum 0))
(set-for-each (lambda (k) (set! sum (+ sum k)))
(set real-comparator 1 2 3 4 5))
sum) ⇒ 15(set-fold proc nil
set) → obj
Proc must be a procedure accepting two arguments and returning a single value. Nil may be any Scheme object.
Invokes proc on each member of set in an 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 proc was not invoked.
(set-fold cons '() (set real-comparator 1 2 3))
⇒ (2 3 1) ; order unspecified(set-filter pred set) →
set
Returns a newly allocated set with the same comparator as set and containing just the elements of set that satisfy pred.
(set->list
(set-filter even? (set real-comparator 1 2 3 4)))
⇒ (4 2) ; order unspecified(set-filter! pred set) →
set
A linear-update variant of
set-filter. It
is allowed, but not required, to mutate set to
produce its result.
(set-remove pred set) →
set
Returns a newly allocated set with the same comparator as set and containing just the elements of set that do not satisfy pred.
(set->list
(set-remove even? (set real-comparator 1 2 3 4)))
⇒ (1 3) ; order unspecified(set-remove! pred set) →
set
A linear-update variant of
set-remove. It
is allowed, but not required, to mutate set to
produce its result.
(set-partition pred
set) → set, set
Returns two values: a newly allocated set with the same comparator as set that contains just the elements of set that satisfy pred, and another newly allocated set, also with the same comparator, that contains just the elements of set that do not satisfy pred.
(let-values (((evens odds)
(set-partition even? (set real-comparator 1 2 3 4))))
(values (set->list evens) (set->list odds)))
⇒ (2 4) ; order unspecified
(1 3)(set-partition! pred
set) → set, set
A linear-update variant of
set-partition. It
is allowed, but not required, to mutate set to
produce its results.
(set-copy set) → set
Returns a newly allocated set containing the elements of set and using the same comparator.
(set->list set) → list
Returns a newly allocated list containing the members of set in unspecified order.
(list->set comparator
list) → set
Every element of list must satisfy comparator’s type-test predicate.
Returns a newly allocated set using comparator and containing the elements of list.
(set->list (list->set real-comparator '(1 2 3)))
⇒ (1 3 2) ; order unspecified
(set->list (list->set eqv-comparator '(foo foo bar)))
⇒ (foo bar) ; order unspecified[Deprecated] (list->set! set
list) → set
Every element of list must satisfy set’s comparator’s type-test predicate.
Alias of
set-adjoin-all!.
It is an error to pass sets to these predicates that do not
share the same comparator (in the sense of
eqv?).
None of these predicates produces a total order on
sets. In particular, sets do not have the trichotomy property
under set=?, set<?,
and set>?: two sets may fail to satisfy all three
of these predicates.
(set=? set1
set2 …) → boolean
Returns #t if each set contains the
same elements.
(set<? set1
set2 …) → boolean
Returns #t if each set other than the
last is a proper subset of the following set, and
#f otherwise.
(set<? (set real-comparator 4 2)
(set real-comparator 2 4 6)
(set real-comparator 2 4 6 8))
⇒ #t
(set<? (set real-comparator 4 2)
(set real-comparator 4 5 6))
⇒ #f
(set<? (set real-comparator 4 2)) ⇒ #t(set>? set1
set2 …) → boolean
Returns #t if each set other than the
last is a proper superset of the following set, and
#f otherwise.
(set>? (set real-comparator 2 4 6 8)
(set real-comparator 2 4 6)
(set real-comparator 4 2))
⇒ #t
(set>? (set real-comparator 4 5 6)
(set real-comparator 4 2))
⇒ #f
(set>? (set real-comparator 4 2)) ⇒ #t(set<=? set1
set2 …) → boolean
Returns #t if each set other than the
last is a subset of the following set, and
#f otherwise.
(set<=? (set real-comparator 4 2)
(set real-comparator 2 4 6)
(set real-comparator 6 2 4))
⇒ #t(set>=? set1
set2 …) → boolean
Returns #t if each set other than the
last is a superset of the following set, and
#f otherwise.
(set>=? (set real-comparator 6 2 4)
(set real-comparator 2 4 6)
(set real-comparator 4 2))
⇒ #t(set-union
set1 set2
…) → set
(set-intersection
set1 set2
…) → set
(set-difference
set1 set2
…) → set
(set-xor set1
set2) → set
The set arguments must all
use the same comparator (in the sense of eqv?).
Otherwise, it is an error.
Return 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.
(set->list (set-union (set real-comparator 1 3 5)
(set real-comparator 0 2 4)))
⇒ (0 5 3 2 1 4) ; order unspecified
(set->list (set-intersection (set real-comparator 1 3 2)
(set real-comparator 1 7 2)))
⇒ (1 2) ; order unspecified
(set->list (set-difference (set real-comparator 1 3 5 7)
(set real-comparator 1 4 6)
(set real-comparator 2 5 9)))
⇒ (7 3) ; order unspecified
(set->list (set-xor (set real-comparator 1 4 5 7)
(set real-comparator 1 4 6)))
⇒ (5 7 6) ; order unspecified(set-union!
set1 set2
…) → set
(set-intersection!
set1 set2
…) → set
(set-difference!
set1 set2
…) → set
(set-xor! set1
set2) → set
These are linear-update variants of the set-theoretical procedures given above. They are allowed, but not required, to mutate set1 to produce their results.
set-comparator
SRFI 128 comparator used to compare sets, which also
allows sets of sets, etc. to be constructed.
Set-comparator is required to provide at least
type-test and equality functions.
It is an error to compare sets with
different comparators (in the sense of eqv?).
The identifiers in this section are exported by the
(srfi 289 bag) library.
(bag comparator element …) →
bag
Returns a newly allocated bag using comparator and containing the given elements. It is an error if any of the element arguments does not satisfy comparator’s type-test predicate.
(bag->list (bag real-comparator)) ⇒ ()
(bag->list (bag real-comparator 1 2 2 3))
⇒ (2 3 1 2) ; order unspecified(bag-unfold stop? mapper
successor seed
comparator) → bag
seed may be any object. stop? is a predicate taking a single value of seed’s type. mapper and successor are procedures taking a single value of seed’s type and returning a single value. It is an error if mapper returns a value that does not satisfy comparator’s type-test predicate.
Returns a newly allocated bag using comparator. The elements of this bag are generated by the following process:
The new bag is initialized to the empty bag.
stop? is applied to the current seed. If the result is true, then the unfolding process halts and the new bag is returned. Otherwise, the process continues.
The result of applying mapper to the current seed is added to the bag.
successor is applied to the current seed to produce the next seed. Unfolding continues with step 2.
If stop?, mapper, or successor
mutate the values returned by mapper, then
bag-unfold returns a bag whose contents are
unspecified. If multiple returns occur from
bag-unfold, the values returned by earlier returns
are not mutated.
(bag->list
(bag-unfold (lambda (i) (> i 2))
abs
(lambda (i) (+ i 1))
-2
real-comparator))
⇒ (2 1 0 2 1) ; order unspecified(bag-accumulate proc comparator
seed1 seed2
…) → bag
The seeds may be any objects. proc must accept n arguments, where n is the number of seeds, and return n + 1 values, the first of which must satisfy comparator’s type-test predicate.
Similar to bag-unfold,
except that a single procedure controls the unfolding of a new
bag. Let n be the number of seeds:
The new bag is initialized to the empty bag.
Proc is applied to a procedure
terminate and the seeds, in that
order. If terminate is invoked in tail context
on any number of arbitrary values, then the process halts
and the new bag along with those values are returned from
bag-accumulate.
Otherwise, proc is expected to return n + 1 values: a new bag element and n new seeds. The element is added to the new bag and the process continues at step two with the new seeds.
It is an error for the number of seeds to vary between steps
of the unfolding process. If proc mutates values
returned by earlier invocations of proc, then
bag-accumulate returns a bag whose contents are
unspecified. If multiple returns occur from
bag-accumulate, the values returned by earlier
returns are not mutated.
(let-values (((bag sym)
(bag-accumulate (lambda (terminate i)
(if (> i 2)
(terminate 'finished)
(values (abs i) (+ i 1))))
(make-real-comparator)
-2)))
(values (bag->list bag) sym))
⇒ (2 0 2 1 1) ; or some permutation thereof
finished(bag? obj) → boolean
Returns #t if obj is a bag, and
#f otherwise.
(bag-contains? bag element) →
boolean
Returns #t if element is a member of
bag and #f otherwise.
(bag-contains? (bag real-comparator 1 3 3) 3) ⇒ #t
(bag-contains? (bag real-comparator 0 2 2) 3) ⇒ #f(bag-empty? bag) → boolean
Returns #t if bag has no elements and
#f otherwise.
(bag-disjoint? bag1
bag2) → boolean
It is an error if the comparator
of bag1 is not the same (in the sense of
eqv?) as that of bag2.
Returns #t if bag1 and
bag2 have no elements in common and
#f otherwise.
(bag-disjoint? (bag real-comparator 1 3 3)
(bag real-comparator 2 6 6 4))
⇒ #t
(bag-disjoint? (bag real-comparator 1 3 3)
(bag real-comparator 3 4 6))
⇒ #f[Deprecated] (bag-member bag
element default) → obj
Default may be any Scheme object.
Returns an element of bag that is equal (in the sense of bag’s comparator) to element. If element is not a member of bag, default is returned instead.
This section is informational.
Unless a notion of element equality other than that given by bag’s comparator is relevant, this procedure is equivalent to
(lambda (bag element default)
(if (bag-contains? bag element) element default)).Even when such a notion is relevant, note that it is
unspecified which “copy” of element is returned
if bag contains more than one. (Under many
implementations, the notion of distinct copies may have no
meaning.) Either avoid bag-member or treat
it as strictly equivalent to the above procedure.
(bag-element-comparator bag) →
comparator
Returns the comparator used to compare the elements of bag.
(bag-adjoin bag element …)
→ bag
Returns a newly allocated bag that uses the same comparator as bag and that contains all its elements in addition to the element arguments.
(bag->list (bag-adjoin (bag real-comparator 1 2) 3 4 3))
⇒ (1 3 2 4 3) ; order unspecified(bag-adjoin! bag element …)
→ bag
A linear-update variant of
bag-adjoin. It is
allowed, but not required, to mutate bag to produce
its result.
(bag-adjoin-all bag list)
→ bag
Every element of list must satisfy bag’s comparator’s type-test predicate.
Returns a newly allocated bag that uses the same comparator as bag and that contains all its elements in addition to the elements of list.
(bag->list (bag-adjoin-all (bag real-comparator 1 2)
'(3 4 3)))
⇒ (1 3 2 4 3) ; order unspecified(bag-adjoin-all! bag list)
→ bag
A linear-update variant of
bag-adjoin-all. It is
allowed, but not required, to mutate bag to produce
its result.
(bag-delete bag element …)
→ bag
Returns a newly allocated bag containing all the elements of
bag but with the elements removed. More
precisely, if bag-delete is passed n
copies of an element e, then the element count of
e in bag is reduced by n to a
minimum of zero.
(bag->list
(bag-delete (bag real-comparator 1 2 2 3) 2 3))
⇒ (1 2)
(bag->list (bag-delete (bag real-comparator 2 4 5) 2 6))
⇒ (4 5)(bag-delete! bag element …)
→ bag
A linear-update variant of
bag-delete. It is
allowed, but not required, to mutate bag to produce
its result.
(bag-delete-all bag
list) → bag
Every element of list must satisfy the type-test predicate of bag’s comparator. Otherwise, it is an error.
Returns a newly allocated bag containing all the elements of bag but with the elements of list removed. More precisely, if list contains n copies of an element e, then the element count of e in bag is reduced by n to a minimum of zero.
(bag->list
(bag-delete-all (bag real-comparator 1 2 2 3) '(2 3)))
⇒ (1 2)
(bag->list (bag-delete (bag real-comparator 2 4 5) '(2 6)))
⇒ (4 5)(bag-delete-all! bag
list) → bag
A linear-update variant of
bag-delete-all. It
is allowed, but not required, to mutate bag to
produce its result.
[Deprecated] (bag-search! bag
element failure
success)
The 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 a 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. (I.e. the count of element
in bag is reduced by one, to a minimum of
zero.)
Invoking (remove obj)
causes the matching element of bag to be
removed from it. (I.e. the count of element
in bag is reduced by one, to a minimum of
zero.)
In all cases, two values are returned: the possibly updated bag and obj.
(bag-pop bag [failure])
→ obj …
If failure is provided, it must be a procedure accepting zero arguments. Otherwise, it is an error.
Chooses an arbitrary element x of bag and returns two values: a newly allocated bag using the same comparator as bag and containing all of its elements except x, and x itself. If bag is empty and failure is provided, then failure is invoked in tail context on zero arguments. Otherwise, it is an error.
(let-values (((rest x) (bag-pop (bag real-comparator 1 2 2 3))))
(values (bag->list rest) x))
⇒ (1 2 3) ; possibly
2(bag-pop! bag [failure])
→ obj …
Linear-update variant of
bag-pop which is allowed,
but not required, to mutate bag to produce its
result.
(bag-size bag) → exact-integer
Returns the number of elements in bag.
(bag-size (bag real-comparator 1 2 2 3)) ⇒ 4(bag-find pred bag
failure) → obj …
Returns an arbitrarily-chosen element of bag that satisfies pred. If no such element exists, then failure is invoked in tail context on zero arguments.
(bag-find even?
(bag real-comparator 1 2 3 4 2)
(lambda () #f))
⇒ 2 ; or 4
(bag-find negative?
(bag real-comparator 1 2 3 4 2)
(lambda () #f))
⇒ #f(bag-count pred bag) →
exact-integer
Returns the number of elements of bag that satisfy pred.
(bag-count even? (bag real-comparator 1 2 3))
⇒ 1(bag-any? pred bag) →
boolean
Returns #t if any element of bag
satisfies pred. Otherwise, returns
#f.
(bag-any? even? (bag real-comparator 1 2 3))
⇒ #t
(bag-any? negative? (bag real-comparator 1 2 3 4))
⇒ #f(bag-every? pred bag) →
boolean
Returns #t if every element of bag
satisfies pred. Otherwise, returns
#f.
(bag-every? integer? (bag real-comparator 1 2 3 4))
⇒ #t
(bag-every? even? (bag real-comparator 1 2 3 4))
⇒ #f(bag-map proc comparator
bag) → bag
Proc must be a procedure accepting one argument, an element of bag, and returning one value which must satisfy comparator’s type-test predicate.
Applies proc to each element of bag in
an arbitrary order and returns a newly allocated bag, created
as if by (bag comparator), which
contains the results of the applications.
(bag->list
(bag-map abs (bag real-comparator -2 -1 0 1 2)))
⇒ (0 1 1 2 2) ; order unspecified(bag-for-each proc bag) →
unspecified
Proc must be a procedure accepting one argument, an element of bag.
Applies proc to the elements of bag in an arbitrary order, discarding the returned values. Returns an unspecified result.
(let ((sum 0))
(bag-for-each (lambda (k) (set! sum (+ sum k)))
(bag real-comparator 1 2 3 3 4))
sum) ⇒ 13(bag-fold proc nil
bag) → obj
Proc must be a procedure accepting two arguments and returning a single value. Nil may be any Scheme object.
Invokes proc on each member of bag in an 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 proc was not invoked.
(bag-fold cons '() (bag real-comparator 1 1 2))
⇒ (1 2 1) ; order unspecified(bag-filter pred bag) →
bag
Returns a newly allocated bag with the same comparator as bag and containing just the elements of bag that satisfy pred.
(bag->list
(bag-filter even? (bag real-comparator 1 1 2 2 3 4 4)))
⇒ (2 4 2 4) ; order unspecified(bag-filter! pred bag) →
bag
A linear-update variant of
bag-filter. It
is allowed, but not required, to mutate bag to
produce its result.
(bag-remove pred bag) →
bag
Returns a newly allocated bag with the same comparator as bag and containing just the elements of bag that do not satisfy pred.
(bag->list
(bag-remove even? (bag real-comparator 1 1 2 2 3 4 4)))
⇒ (1 1 3) ; order unspecified(bag-remove! pred bag) →
bag
A linear-update variant of
bag-remove. It
is allowed, but not required, to mutate bag to
produce its result.
(bag-partition pred
bag) → bag, bag
Returns two values: a newly allocated bag with the same comparator as bag that contains just the elements of bag that satisfy pred, and another newly allocated bag, also with the same comparator, that contains just the elements of bag that do not satisfy pred.
(let-values (((evens odds)
(bag-partition even?
(bag real-comparator 1 1 2 2 3 4 4))))
(values (bag->list evens) (bag->list odds)))
⇒ (2 4 2 4) ; order unspecified
(1 3 3)(bag-partition! pred
bag) → bag, bag
A linear-update variant of
bag-partition. It
is allowed, but not required, to mutate bag to
produce its results.
(bag-copy bag) → bag
Returns a newly allocated bag containing the elements of bag and using the same comparator.
(bag->list bag) → list
Returns a newly allocated list containing the members of bag in unspecified order.
(list->bag comparator
list) → bag
It is an error if any element of list does not satisfy comparator’s type-test predicate.
Returns a newly allocated bag using comparator and containing the elements of list.
(bag->list
(list->bag real-comparator '(1 3 3 3)))
⇒ (3 1 3 3) ; order unspecified[Deprecated] (list->bag! bag
list) → bag
Every element of list must satisfy bag’s comparator’s type-test predicate.
Alias of
bag-adjoin-all!.
(bag->set bag) → set
Returns a newly allocated set using the same comparator as bag and containing all its unique elements.
(set->list
(bag->set (bag real-comparator 1 1 2 3 3 3)))
⇒ (1 3 2) ; order unspecified(set->bag set) → bag
Returns a newly allocated bag using the same comparator as set and containing the same elements.
(bag->list
(set->bag (set real-comparator 1 2 3)))
⇒ (1 2 3) ; order unspecified(set->bag! bag set)
→ bag
Returns a bag using the same comparator as
bag and containing the same elements, in addition
to each element of set. set->bag!
is permitted, but not required, to mutate bag to
produce its result.
(bag->list
(set->bag! (bag real-comparator 1 2 2)
(set real-comparator 2 3 4)))
⇒ (1 2 3 2 4 2) ; order unspecified(bag->alist bag) → alist
Returns a newly allocated list of pairs. Each pair’s car is a unique element of bag and its cdr is the number of occurrences (an exact integer) of that element. The order of the list is unspecified.
(bag->alist
(bag real-comparator 1 1 2 2 2 3))
⇒ ((1 . 2) (3 . 1) (2 . 3)) ; order unspecified(alist->bag comparator
alist) → bag
Each element of alist must be a pair whose car satisfies comparator’s type-test predicate and whose cdr is a non-negative exact integer. Otherwise, it is an error.
Returns a newly allocated bag using comparator, where the keys of alist specify the elements and the corresponding values specify how many times they occur.
(bag->list
(alist->bag real-comparator
'((1 . 2) (2 . 3) (3 . 1))))
⇒ (1 2 1 2 3 2) ; order unspecifiedIt is an error to pass bags to these predicates that do not
share the same comparator (in the sense of
eqv?).
None of these predicates produces a total order on
bags. In particular, bags do not have the trichotomy property
under bag=?, bag<?,
and bag>?: two bags may fail to satisfy all three
of these predicates.
(bag=? bag1
bag2 …) → boolean
Returns #t if each bag contains the
same elements.
(bag=? (bag real-comparator 1 2 3 3) (bag real-comparator 2 3 1 3))
⇒ #t
(bag=? (bag real-comparator 1 3 2) (bag real-comparator 1 3 3 2))
⇒ #f
(bag=? (bag real-comparator 1 2 3) (bag real-comparator 1 6))
⇒ #f(bag<=? bag1
bag2 …) → boolean
Returns true if each bagi other than the
last is included in bagi+1, and
#f otherwise.
A bag A is included in a bag B if and
only if
(<= (bag-element-count A x)
(bag-element-count B x))is true for every element x of A.
(bag<=? (bag real-comparator 1 2 3 3) (bag real-comparator 2 3 1 3))
⇒ #t
(bag<=? (bag real-comparator 1 3 2) (bag real-comparator 1 3 3 2))
⇒ #t
(bag<=? (bag real-comparator 1 3 2) (bag real-comparator 1 3 3 2 4))
⇒ #t
(bag<=? (bag real-comparator 1 3 3 2) (bag real-comparator 1 3 2 4))
⇒ #f
(bag<=? (bag real-comparator 1 2 3) (bag real-comparator 1 6))
⇒ #f(bag<? bag1
bag2 …) → boolean
With two arguments, returns #t if
bag1 is included in
bag2 (in the sense of bag<=?) and
bag1 has fewer elements than
bag2. With a single argument, or with
more than two arguments, bag<? returns
#t if each bagi other than
the last satisfies this relation with
bagi+1. Otherwise, it returns
#f.
(bag<? (bag real-comparator 1 2 3) (bag real-comparator 2 3 1 3))
⇒ #t
(bag<? (bag real-comparator 1 3 3 2) (bag real-comparator 1 3 3 2))
⇒ #f
(bag<? (bag real-comparator 1 3 2) (bag real-comparator 1 3 3 2 4))
⇒ #t
(bag<? (bag real-comparator 1 2 3) (bag real-comparator 1 3 6))
⇒ #f(bag>=? bag1
bag2 …) → boolean
Returns true if each bagi other than the
last includes bagi+1, and
#f otherwise.
A bag A is included in a bag B if and
only if
(bag<=? B A) is true.
(bag>=? (bag real-comparator 1 2 3 3) (bag real-comparator 2 3 1 3))
⇒ #t
(bag>=? (bag real-comparator 1 3 3 2) (bag real-comparator 1 3 2))
⇒ #t
(bag>=? (bag real-comparator 1 3 3 2 4) (bag real-comparator 1 3 2))
⇒ #t
(bag>=? (bag real-comparator 1 3 2) (bag real-comparator 1 2 3 3))
⇒ #f
(bag>=? (bag real-comparator 1 6) (bag real-comparator 1 2 3))
⇒ #f(bag>? bag1
bag2 …) → boolean
With two arguments, returns #t if
bag1 includes
bag2 (in the sense of bag>=?) and
bag1 has more elements than
bag2. With a single argument, or with
more than two arguments, bag>? returns
#t if each bagi other than
the last satisfies this relation with
bagi+1. Otherwise, it returns
#f.
(bag>? (bag real-comparator 1 2 3 3) (bag real-comparator 2 1 3))
⇒ #t
(bag>? (bag real-comparator 1 3 3 2) (bag real-comparator 1 3 3 2))
⇒ #f
(bag>? (bag real-comparator 1 3 3 2 4) (bag real-comparator 1 3 2))
⇒ #t
(bag>? (bag real-comparator 1 3 3 2) (bag real-comparator 1 2 3))
⇒ #t
(bag>? (bag real-comparator 1 2 3) (bag real-comparator 1 6))
⇒ #f(bag-union
bag1 bag2
…) → bag
Returns a newly allocated bag that is the union of the bags. The number of equal elements in the result is equal to the largest number of equal elements in any of the bags.
(bag->list
(bag-union (bag real-comparator 1 3 3)
(bag real-comparator 2 2 4 3))
⇒ (1 2 2 3 3 4) ; order unspecified
(bag->list
(bag-union (bag real-comparator 1 3 3)
(bag real-comparator 2 2 4 3)
(bag real-comparator 1 1 1 4)))
⇒ (1 1 1 2 2 3 3 4) ; order unspecified(bag-intersection
bag1 bag2
…) → bag
Returns a newly allocated bag that is the intersection of the bags. The number of equal elements in the result is equal to the smallest number of equal elements in any of the bags.
(bag->list
(bag-intersection (bag real-comparator 1 2 3 3)
(bag real-comparator 2 2 4 3 3)))
⇒ (2 3 3) ; order unspecified
(bag->list
(bag-intersection (bag real-comparator 1 2 3 3)
(bag real-comparator 2 2 4 3 3)
(bag real-comparator 3 4 5)))
⇒ (3)(bag-difference
bag1 bag2
…) → bag
Returns a newly allocated bag that is the asymmetric difference of the bags. The number of equal elements in the result is equal to the number of equal elements in bag1, minus the number of equal elements in the other bags, but not less than zero.
(bag->list
(bag-difference (bag real-comparator 1 2 3 3 3)
(bag real-comparator 2 2 4 3)))
⇒ (1 3 3) ; order unspecified
(bag->list
(bag-difference (bag real-comparator 1 2 3 3 3)
(bag real-comparator 2 2 4 3)
(bag real-comparator 3 3)))
⇒ (1)(bag-xor
bag1 bag2
…) → bag
Returns a newly allocated bag that is the symmetric difference of the bags. The number of equal elements in the result is equal to the absolute value of the difference between the number of equal elements in bag1 and bag2.
(bag->list
(bag-xor (bag real-comparator 1 1 2 3 3 3)
(bag real-comparator 2 2 3 3)))
⇒ (1 1 2 3) ; order unspecified(bag-union!
bag1 bag2
…) → bag
(bag-intersection!
bag1 bag2
…) → bag
(bag-difference!
bag1 bag2
…) → bag
(bag-xor! bag1
bag2) → bag
These are linear-update variants of the set-theoretical procedures given above. They are allowed, but not required, to mutate bag1 to produce their results.
bag-comparator
SRFI 128 comparator used to compare bags, which also
allows sets of bags, etc. to be constructed.
Bag-comparator is required to provide at least
type-test and equality functions.
It is an error to compare bags with
different comparators (in the sense of eqv?).
(bag-sum bag1
bag2 …) → bag
The bag arguments must all
use the same comparator (in the sense of eqv?).
Returns a newly allocated bag using the same comparator as the bags and 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.
(bag->list
(bag-sum (bag real-comparator 1 2 3)
(bag real-comparator 2 3 4)
(bag real-comparator 3 4 5))
⇒ (1 2 2 3 3 3 4 4 5) ; order unspecified(bag-sum! bag1
bag2 … ) → bag
A linear-update variant of
bag-sum which is allowed,
but not required, to mutate bag1 to
produce its result.
(bag-product k bag)
→ bag
It is an error if k is not a non-negative exact integer.
Returns a newly allocated bag using the same comparator as bag and containing all the unique elements in bag, where the count of each unique element in the resulting bag is equal to the count of that element in bag multiplied by k.
(bag->list
(bag-product 3 (bag real-comparator 1 2))
⇒ (1 1 1 2 2 2) ; order unspecified(bag-product! k
bag) → bag
A linear-update variant of
bag-product which is
allowed, but not required, to mutate bag to produce
its result.
(bag-unique-size bag) →
exact-integer
Returns the number of unique elements of bag.
(bag-unique-size (bag real-comparator 1 1 2 3 3 3)) ⇒ 3(bag-element-count bag
element) → exact-integer
Returns an exact integer representing the number of times that element appears in bag.
(bag-element-count (bag real-comparator 1 1 2) 1) ⇒ 2
(bag-element-count (bag real-comparator 1 1 2) 3) ⇒ 0(bag-for-each-unique proc
bag) → unspecified
Proc must be a procedure accepting two arguments, an element of bag and an exact integer.
Applies proc to each unique element of bag in arbitrary order, passing the element as the first argument and the number of times it occurs in bag as the second, and discarding the returned values. Returns an unspecified result.
(let ((elts '()))
(bag-for-each-unique (lambda (e c)
(set! elts (cons (cons e c) elts)))
(bag real-comparator 1 1 2 3 3 3))
elts)
⇒ ((1 . 2) (2 . 1) (3 . 3)) ; order unspecified(bag-fold-unique proc nil
bag) → obj
Proc must be a procedure accepting three arguments and returning a single value. Nil may be any Scheme object.
Invokes proc on each unique element of bag in arbitrary order, passing the number of occurrences (an exact integer) as the second argument and the result of the previous invocation as the third argument. For the first invocation, nil is used as the third argument. Returns the result of the last invocation.
(bag-fold-unique (lambda (e c elts)
(cons (cons e c elts)))
'()
(bag real-comparator 1 1 2 3 3 3))
⇒ ((1 . 2) (2 . 1) (3 . 3)) ; order unspecified(bag-increment bag element
k) → bag
It is an error if k is not a non-negative exact integer.
Returns a newly allocated bag using the same comparator as bag and containing the same elements, but with k additional copies of element.
(bag->list
(bag-increment (bag real-comparator 1 1 2 3) 2 3))
⇒ (1 1 2 2 2 2 3) ; order unspecified(bag-increment! bag element
k) → bag
A linear-update variant of
bag-increment which
is allowed, but not required, to mutate bag to
produce its result.
(bag-decrement bag element
k) → bag
It is an error if k is not a non-negative exact integer.
Returns a newly allocated bag using the same comparator as bag and containing the same elements, but with k fewer copies of element (minimum zero).
(bag->list
(bag-decrement (bag real-comparator 1 1 1 2 3) 1 2))
⇒ (1 2 3) ; order unspecified
(bag->list
(bag-decrement (bag real-comparator 1 2 3) 1 3))
⇒ (2 3) ; order unspecified
(bag->list
(bag-decrement (bag real-comparator 1 2 3) 4 10))
⇒ (1 2 3) ; order unspecified(bag-decrement! bag element
k) → bag
A linear-update variant of
bag-decrement which
is allowed, but not required, to mutate bag to
produce its result.
A sample implementation in R7RS Scheme can be found
in the
SRFI
repository. It implements sets and bags on top of the
hashmaps of (srfi 146 hash). In addition to SRFI 146,
the implementation requires SRFIs 1, 128, and 151. To run the
included test suite you will also need SRFIs 64 and 132.
Thanks to John Cowan for creating SRFIs 113 and 153. His work provided the template for this SRFI.
Thanks to those who provided feedback on this SRFI via the SRFI mailing list or the #scheme IRC channel, including:
Of course, none of the above should be taken to mean that any of these people endorse the SRFI’s final draft.
S. Bradner, Key words for use in RFCs to Indicate Requirement Levels (RFC 2119), 1997. https://datatracker.ietf.org/doc/html/rfc2119
John Cowan. SRFI 113: Sets and bags. https://srfi.schemers.org/srfi-113/, 2014.
John Cowan. SRFI 128: Comparators (reduced). https://srfi.schemers.org/srfi-128/, 2016.
Arthur A. Gleckler and Marc Nieper-Wißkirchen, SRFI 146: Mappings. https://srfi.schemers.org/srfi-146/, 2018.
John Cowan. SRFI 153: Ordered sets. https://srfi.schemers.org/srfi-153/, 2023.
John Cowan. SRFI 162: Comparators sublibrary. https://srfi.schemers.org/srfi-162/, 2019.
Alex Shinn, John Cowan, & Arthur A. Gleckler, eds., Revised7 Report on the Algorithmic Language Scheme (R7RS Small), 2013. https://small.r7rs.org
© 2026 Wolfgang Corcoran-Mathe and John Cowan.
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 (including the next paragraph) 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.