srfi-113 | chickadee

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.

Installation

$ chicken-install srfi-113

$ 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 ...procedure: Returns 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 seedprocedure: 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.

Predicates

set? objprocedure: Returns #t if obj is a set, and #f otherwise.

set-contains? set elementprocedure: Returns #t if element is a member of set and #f otherwise.

set-empty? setprocedure: Returns #t if set has no elements and #f otherwise.

set-disjoint? set1 set2procedure: Returns #t if set1 and set2 have no elements in common and #f otherwise.

Accessors

set-member set element defaultprocedure: 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.

set-element-comparator setprocedure: Returns the comparator used to compare the elements of set.

Updaters

set-adjoin set element ...procedure: The 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 ...procedure: The 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 elementprocedure: The 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 elementprocedure: The 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-listprocedure

set-delete-all! set element-listprocedure

The 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 successprocedure

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.

The Whole Set

set-size setprocedure: Returns the number of elements in set as an exact integer.

set-find predicate set failureprocedure: Returns 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 setprocedure: Returns the number of elements of set that satisfy predicate as an exact integer.

set-any? predicate setprocedure: 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.

set-every? predicate setprocedure: 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.

Mapping and Folding

set-map comparator proc setprocedure

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:

(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 setprocedure: Applies proc to set in arbitrary order, discarding the returned values. Returns an unspecified result.

set-fold proc nil setprocedure: 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.

set-filter predicate setprocedure: Returns a newly allocated set with the same comparator as set, containing just the elements of set that satisfy predicate.

set-filter! predicate setprocedure: A linear update procedure that returns a set containing just the elements of set that satisfy predicate.

set-remove predicate setprocedure: Returns a newly allocated set with the same comparator as set, containing just the elements of set that do not satisfy predicate.

set-remove! predicate setprocedure: A linear update procedure that returns a set containing just the elements of set that do not satisfy predicate.

set-partition predicate setprocedure: 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.

set-partition! predicate setprocedure: A 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 setprocedure: Returns a newly allocated set containing the elements of set, and using the same comparator.

set->list setprocedure: Returns a newly allocated list containing the members of set in unspecified order.

list->set comparator listprocedure: 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! set listprocedure: Returns 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 ...procedure: Returns #t if each set contains the same elements.

set<? set1 set2 ...procedure: Returns #t if each set other than the last is a proper subset of the following set, and #f otherwise.

set>? set1 set2 ...procedure: Returns #t if each set other than the last is a proper superset of the following set, and #f otherwise.

set<=? set1 set2 ...procedure: Returns #t if each set other than the last is a subset of the following set, and #f otherwise.

set>=? set1 set2 ...procedure: Returns #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 set2procedure: 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. 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 set2procedure: Linear 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 ...procedure: Returns 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 seedprocedure: 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.

Predicates

bag? objprocedure: Returns #t if obj is a bag, and #f otherwise.

bag-contains? bag elementprocedure: Returns #t if element is a member of bag and #f otherwise.

bag-empty? bagprocedure: Returns #t if bag has no elements and #f otherwise.

bag-disjoint? bag1 bag2procedure: Returns #t if bag1 and bag2 have no elements in common and #f otherwise.

Accessors

bag-member bag element defaultprocedure: 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.

bag-element-comparator bagprocedure: Returns the comparator used to compare the elements of bag.

Updaters

bag-adjoin bag element ...procedure: The 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 ...procedure: The 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 elementprocedure: The 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 elementprocedure: The 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-listprocedure

bag-delete-all! bag element-listprocedure

The 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 successprocedure

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

The Whole bag

bag-size bagprocedure: Returns the number of elements in bag as an exact integer.

bag-find predicate bag failureprocedure: Returns 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 bagprocedure: Returns the number of elements of bag that satisfy predicate as an exact integer.

bag-any? predicate bagprocedure: 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.

bag-every? predicate bagprocedure: Returns #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 bagprocedure

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:

(bag-map string-ci-comparator symbol->string (bag eq? 'foo 'bar 'baz))
     => (bag string-ci-comparator "foo" "bar" "baz")

bag-for-each proc bagprocedure: Applies proc to bag in arbitrary order, discarding the returned values. Returns an unspecified result.

bag-fold proc nil bagprocedure: 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.

bag-filter predicate bagprocedure: Returns a newly allocated bag with the same comparator as bag, containing just the elements of bag that satisfy predicate.

bag-filter! predicate bagprocedure: A linear update procedure that returns a bag containing just the elements of bag that satisfy predicate.

bag-remove predicate bagprocedure: Returns a newly allocated bag with the same comparator as bag, containing just the elements of bag that do not satisfy predicate.

bag-remove! predicate bagprocedure: A linear update procedure that returns a bag containing just the elements of bag that do not satisfy predicate.

bag-partition predicate bagprocedure: 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.

bag-partition! predicate bagprocedure: A 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 bagprocedure: Returns a newly allocated bag containing the elements of bag, and using the same comparator.

bag->list bagprocedure: Returns a newly allocated list containing the members of bag in unspecified order.

list->bag comparator listprocedure: Returns a newly allocated bag, created as if by bag using comparator, that contains the elements of list.

list->bag! bag listprocedure: Returns a bag that contains the elements of both bag and list.

Subbags

bag=? bag1 bag2 ...procedure: Returns #t if each bag contains the same elements.

bag<? bag1 bag2 ...procedure: Returns #t if each bag other than the last is a proper subbag of the following bag, and #f otherwise.

bag>? bag1 bag2 ...procedure: Returns #t if each bag other than the last is a proper superbag of the following bag, and #f otherwise.

bag<=? bag1 bag2 ...procedure: Returns #t if each bag other than the last is a subbag of the following bag, and #f otherwise.

bag>=? bag1 bag2 ...procedure: Returns #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 bag2procedure: Return 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 bag2procedure: Linear 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 bag2procedure

The 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 bagprocedure

bag-product! n bagprocedure

The 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 bagprocedure

Returns the number of unique elements of {{bag}}.

bag-element-count bag elementprocedure: Returns an exact integer representing the number of times that element appears in bag.

bag-for-each-uniqueprocedure: 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.

bag-fold-unique proc nil bagprocedure: 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.

bag-increment! bag element countprocedure
bag-decrement! bag element countprocedure: Linear 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 bagprocedure
set->bag setprocedure
set->bag! bag setprocedure: The 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 bagprocedure
alist->bag comparator alistprocedure: 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. 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-comparatorconstant

bag-comparatorconstant: 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! comparatorprocedure: Sets the comparator used when using read-syntax to declare a set or bag. Defaults to (make-default-comparator).

Repository

Github

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

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.

chickadee » srfi-113

Identifier search

SRFI-113: Sets and Bags

TOC »

Installation

SRFI Description

Set Procedures

Constructors

Predicates

Accessors

Updaters

The Whole Set

Mapping and Folding

Copying and Conversion

Subsets

Set-theory Operations

Bag Procedures

Constructors

Predicates

Accessors

Updaters

The Whole bag

Mapping and Folding

Copying and Conversion

Subbags

Bag-theory Operations

Additional bag procedures

Comparators

Non-standard Extensions

Repository

Version History

License

Contents »