Next: Comparators, Previous: Portable runtime environment inquiry, Up: Library modules - SRFIs [Contents][Index]

`srfi-113`

- Sets and bags- Module:
**srfi-113** -
Sets and bags are unordered collection of Scheme values. A set doesn’t count duplicates; if you add an item which is already in a set, you still have one item of the kind. A bag counts duplicates; if you add an item which is already in a bag, you have two items of the kind.

To check whether the items are “the same”, sets and bags takes a comparator at constrution time. The comparator doesn’t need to have an ordering predicate (we don’t need to order the elements) but has to have a hash function. See Basic comparators, for the details of comparators.

As a Gauche’s extension, sets and bags implement collection protocol (see Collection framework, for the details), and generic collection operations can be applied.

(coerce-to <list> (set eq-comparator 'a 'b 'a 'b)) ⇒ (a b) ; order may differ (coerce-to <list> (bag eq-comparator 'a 'b 'a 'b)) ⇒ (a a b b) ; order may differ

- Function:
**set***comparator elt …* - Function:
**bag***comparator elt …* Creates a new set and bag from given elements

`elt`…. Given`comparator`will be used to compare equality of elements.(set->list (set eq-comparator 'a 'b 'a 'b)) ⇒ (a b) (bag->list (bag eq-comparator 'a 'b 'a 'b)) ⇒ (a a b b)

- Function:
**set-unfold***stop? mapper successor seed comparator* - Function:
**bag-unfold***stop? mapper successor seed comparator* Procedurally creates a set or a bag. The first three arguments,

`stop?`,`mapper`and`successor`, are all procedures that takes one argument, the current seed value. It may be easier to know their types:seed :: Seed stop? :: Seed -> Boolean mapper :: Seed -> ElementType successor :: Seed -> Seed

The

`stop?`

procedure takes the current seed value and returns a boolean value - if it is true, iteration stops.The

`mapper`

procedure takes the current seed value and returns an item, which is to be included in the resulting set or bag.The

`successor`

procedure takes the current seed value and returns the next seed value.And the

`seed`

argument gives the initial seed value.(set->list (set-unfold (^s (= s 75)) integer->char (^s (+ s 1)) 65 eqv-comparator)) ⇒ (#\D #\H #\A #\E #\I #\J #\B #\F #\C #\G)

- Function:
**set-contains?***set obj* - Function:
**bag-contains?***bag obj* Check if

`obj`is in the set or the bag.

- Function:
**set-empty?***set* - Function:
**bag-empty?***bag* Returns

`#t`

iff the given set or bag is empty.

- Function:
**set-disjoint?***set1 set2* - Function:
**bag-disjoint?***bag1 bag2* Returns

`#t`

iff the given arguments (sets or bags) don’t have common items. Both arguments must have the same comparator—otherwise an error is signaled.

- Function:
**set-member***set obj default* - Function:
**bag-member***bag obj default* Returns an element in the given set or bag which is equal to

`obj`in terms of the set’s or the bag’s comparator. If no such element is found,`default`will be returned.Note that the returned object doesn’t need to be “the same” as

`obj`in a usual sense. See the following example:(let s (set string-ci-comparator "abc" def") (set-member s "ABC" #f)) ⇒ "abc"

- Function:
**set-element-comparator***set* - Function:
**bag-element-comparator***bag* Returns the comparator used to compare the elements for the set or the bag.

- Function:
**set-adjoin***set elt …* - Function:
**bag-adjoin***bag elt …* Returns a newly created set or bag that contains all the elements in the original set/bag, plus given elements. The new set/bag’s comparator is the same as the original set/bag’s one.

- Function:
**set-replace***set elt* - Function:
**bag-replace***bag elt* Returns a newly created set/bag with the same comparator with the original set/bag, and the same elements, except that the elements equal to

`elt`(in terms of set/bag’s comparator) is replaced by`elt`. If the original set/bag doesn’t contain an element equal to`elt`, the original one is returned.(let ((s (set string-ci-comparator "ABC" "def"))) (set->list (set-replace s "abc"))) ⇒ ("abc" "def")

- Function:
**set-delete***set elt …* - Function:
**bag-delete***bag elt …* Returns a newly created set or bag that has the same comparator and the same elements in the original set/bag, except that the item which is equal to

`elt`.

- Function:
**set-delete-all***set elt-list* - Function:
**bag-delete-all***bag elt-list* Returns a newly created set or bag with the same comparator of the original set/bag, with the elements of the original set/bag except the ones listed in

`elt-list`.

- Function:
**set-adjoin!***set elt …* - Function:
**bag-adjoin!***bag elt …* - Function:
**set-replace!***set elt* - Function:
**bag-replace!***bag elt* - Function:
**set-delete!***set elt …* - Function:
**bag-delete!***bag elt …* - Function:
**set-delete-all!***set elt-list* - Function:
**bag-delete-all!***bag elt-list* These are the linear update versions of their counterparts. It works just like the ones without

`!`

, except that the original set/bag*may*be reused to produce the result, instead of new one being allocated.Note that it’s not guaranteed that the original set/bag is modified, so you should use the return value of them, instead of relying on the side effects.

- Function:
**set-search!***set elt failure success* - Function:
**bag-search!***bag elt failure success* Lookup-and-modify procedures. The

`failure`and`success`arguments are procedures.First, they search

`elt`in the given set/bag. If an item that matches`elt`is found, the`success`procedure is called with three arguments, as follows:(success item update remove)

The

`update`argument is a procedure that takes two arguments, as`(update new-item retval)`

. It replaces the matching`item`in the set/bag with`new-item`, and returns`retval`. The`remove`argument is a procedure that takes one argument, as`(remove retval)`

. It removes the mathing`item`in the set/bag, and returns`retval`.If an item that matches

`elt`is not found, the`failure`procedure is called with two arguments, as follows:(failure insert ignore)

The

`insert`argument is a procedure that takes one argument, as`(insert retval)`

. It inserts`elt`into the set/bag, and returns`retval`. The`ignore`argument is a procedure that takes one argument, as`(ignore retval)`

. It just returns`retval`.The return values of

`set-search!`

and`bag-search!`

is the modified set/bag (which may or may not be`eq?`

to the passed one), and the value returned by`success`or`failure`procedures.Note that

`retval`isn’t used in this process; it is just to provide one of the return values of`set-search!`

/`bag-search!`

, for the procedures passed to`success`or`failure`are expected to be tail-called.If there are more than one item that matches

`elt`in a bag,`bag-search!`

only invokes`success`for the first item it finds. You can recurse into`bag-search!`

in the`failure`procedure to visit all matching items. It is guaranteed that`success`and`failure`procedures are tail-called.

- Function:
**set-size***set* - Function:
**bag-size***bag* Returns the number of items in the set/bag.

- Function:
**set-find***pred set failure* - Function:
**bag-find***pred bag failure* Apply

`pred`on each item in the set/bag, and returns the first item on which`pred`returns true. Since sets and bags are unordered, if there are more than one items that satisfy`pred`, you won’t know which one will be returned.If there’re no items that satisfy

`pred`, a thunk`failure`

is called and its result is returned.

- Function:
**set-count***pred set* - Function:
**bag-count***pred bag* Returns the number of items that satisfy

`pred`in the set/bag.

- Function:
**set-any?***pred set* - Function:
**bag-any?***pred bag* Returns true iff any item in the set/bag satisfy

`pred`.

- Function:
**set-every?***pred set* - Function:
**bag-every?***pred bag* Returns true iff every item in the set/bag satisfy

`pred`.

- Function:
**set-map***comparator proc set* - Function:
**bag-map***comparator proc bag* Create and return a new set/bag with the comparator

`comparator`, whose items are calculated by applying`proc`to each element in the original set/bag.

- Function:
**set-for-each***proc set* - Function:
**bag-for-each***proc bag* Apply

`proc`to each element in the set/bag. The result of`proc`is ignored. Return value is undefined.

- Function:
**set-fold***proc seed set* - Function:
**bag-fold***proc seed bag* For each item in the set/bag, call

`proc`with two arguments, an item and a seed value. What`proc`returns becomes the next seed value. The`seed`argument gives the initial seed value, and the last return value of`proc`will be the result of`set-fold`

/`bag-fold`

.(bag-fold + 0 (bag eqv-comparator 1 1 2 2 3 3 4 4)) ⇒ 20

- Function:
**set-filter***pred set* - Function:
**bag-filter***pred bag* Returns a newly created set/bag with the same comparator of the original set/bag, and its content consists of items from the original set/bag that satisfy

`pred`.(set->list (set-filter odd? (set eqv-comparator 1 2 3 4 5))) ⇒ (1 3 5)

- Function:
**set-remove***pred set* - Function:
**bag-remove***pred bag* Returns a newly created set/bag with the same comparator of the original set/bag, and its content consists of items from the original set/bag that does not satisfy

`pred`.(set->list (set-remove odd? (set eqv-comparator 1 2 3 4 5))) ⇒ (2 4)

- Function:
**set-partition***pred set* - Function:
**bag-partition***pred bag* Returns two sets or bags, both have the same comparator of the original set or bag. The first one consists of the items from the original set/bag that satisfy

`pred`, and the second one consists of the items that don’t.`(receive (in out) (set-remove odd? (set eqv-comparator 1 2 3 4 5)) (values (set->list in) (set->list out))) ⇒ (1 3 5) and (2 4)`

- Function:
**set-filter!***pred set* - Function:
**bag-filter!***pred bag* - Function:
**set-remove!***pred set* - Function:
**bag-remove!***pred bag* - Function:
**set-partition!***pred set* - Function:
**bag-partition!***pred bag* Linear update versions of their counterparts (the procedures without

`!`

). They work like their respective counterpart, but they are allowed (but not required) to reuse the original set/bag to produce the result(s).Note that it is not guaranteed that the original set/bag is modified, so you have to use the return value(s) instead of relying on the side effects.

- Function:
**set-copy***set* - Function:
**bag-copy***bag* Returns a copy of the set/bag.

- Function:
**set->list***set* - Function:
**bag->list***bag* Returns a list of all items in the set/bag. Since sets and bags are unordered, there’s no guarantee on the order of items.

- Function:
**list->set***comparator elt-list* - Function:
**list->bag***comparator elt-list* Creates a set or a bag with the given comparator, and the list of element. Functionally equivalent to the followings:

(apply set comparator elt-list) (apply bag comparator elt-list)

- Function:
**list->set!***set elt-list* - Function:
**list->bag!***bag elt-list* Add items in

`elt-list`to the existing set/bag, and returns the updated set/bag. The original set/bag is also modified. Functionally equivalent to the followings:(apply set-adjoin! set elt-list) (apply bag-adjoin! bag elt-list)

- Function:
**bag->set***bag* - Function:
**set->bag***set* Conversions between a bag and a set. Returns a newly created bag or set, respectively.

If

`bag`has duplicated items,`bag->set`

coerces them to one item.

- Function:
**set->bag!***bag set* Adds all items in

`set`to`bag`, and returns`bag`. Both`bag`and`set`must have the same comparator.

- Function:
**bag->alist***bag* Returns a list of

`(item . count)`

, where`item`is an item in`bag`, and`count`is the number of that item in the bag.

- Function:
**alist->bag***comparator alist* Creates a new bag with

`comparator`, and fills it according to`alist`, which must be a list of`(item . count)`

.If there’s duplicate items in

`alist`, only fist one counts.

- Function:
**set=?***set1 set2 …* - Function:
**bag=?***bag1 bag2 …* Returns true iff all sets/bags have exactly same items.

The comparators of the argument sets/bags are not checked, but assumed to be the same, in terms of the equality of items.

- Function:
**set<?***set1 set2 …* - Function:
**bag<?***bag1 bag2 …* - Function:
**set>?***set1 set2 …* - Function:
**bag>?***bag1 bag2 …* - Function:
**set<=?***set1 set2 …* - Function:
**bag<=?***bag1 bag2 …* - Function:
**set>=?***set1 set2 …* - Function:
**bag>=?***bag1 bag2 …* Returs true iff each preceding set/bag is a proper subset of, a proper superset of, a subset of, or a superset of the following set/bags, respectively.

Again, the comparators of the argument sets/bags are not checked, but assumed to be the same, in terms of the equality of items.

- Function:
**set-union***set1 set2 …* - Function:
**bag-union***bag1 bag2 …* Returns a newly allocated set or bag which is a union of all the sets/bags.

- Function:
**set-intersection***set1 set2 …* - Function:
**bag-intersection***bag1 bag2 …* Returns a newly allocated set or bag which is an intersection of all the sets/bags.

- Function:
**set-difference***set1 set2 …* - Function:
**bag-difference***bag1 bag2 …* Returns a newly created set or bag that contains items in

`set1`/`bag1`except those are also in`set2`/`bag2`….(sort (set->list (set-difference (set eqv-comparator 1 2 3 4 5 6 7) (set eqv-comparator 3 5 7 9 11 13) (set eqv-comparator 4 8 16 32)))) ⇒ (1 2 6)

- Function:
**set-xor***set1 set2* - Function:
**bag-xor***bag1 bag2* Returns a newly created set or bag that consists of items that are either in

`set1`/`bag1`or`set2`/`bag2`, but not in both.(sort (set->list (set-xor (set eqv-comparator 2 3 5 7 11 13 17) (set eqv-comparator 3 5 7 9 11 13 15)))) ⇒ (2 9 15 17)

- Function:
**set-union!***set1 set2 …* - Function:
**bag-union!***bag1 bag2 …* - Function:
**set-intersection!***set1 set2 …* - Function:
**bag-intersection!***bag1 bag2 …* - Function:
**set-difference!***set1 set2 …* - Function:
**bag-difference!***bag1 bag2 …* - Function:
**set-xor!***set1 set2* - Function:
**bag-xor!***bag1 bag2* Linear update versions of their corresponding procedures. Those procedures works like their

`!`

-less counterparts, except that they are allowed to, but not required to, reuse`set1`/`bag1`to produce the result.The caller should always use the returned set/bag instead of relying on the side effects.

- Function:
**bag-sum***bag1 bag2 …* - Function:
**bag-sum!***bag1 bag2 …* Returns a bag that gathers all the items in given bags, counting duplicates. The functional version

`bag-sum`

always creates new bag to return. The linear update version`bag-sum!`

is allowed to, but not required to, modify`bag1`to produce the result.(sort (bag->list (bag-sum (bag eqv-comparator 1 1 2 4 5 5 6) (bag eqv-comparator 3 3 5 9)))) ⇒ (1 1 2 3 3 4 5 5 5 6 9)

Note the difference from

`bag-union`

:(sort (bag->list (bag-union (bag eqv-comparator 1 1 2 4 5 5 6) (bag eqv-comparator 3 3 5 9)))) ⇒ (1 1 2 3 3 4 5 5 6 9)

- Function:
**bag-product***n bag* - Function:
**bag-product!***n bag* Returns a bag that contains every item as

`n`-times many as the original bag. A fresh bag is created and returned by`bag-product`

, while`bag-product!`

may reuse`bag`to produce the result.(sort (bag->list (bag-product 2 (bag eq-comparator 'a 'b 'r 'a)))) ⇒ (a a a a b b r r)

- Function:
**bag-unique-size***bag* Returns the number of unique elements in

`bag`.(bag-unique-size (bag eqv-comparator 1 1 2 2 3 3 4)) ⇒ 4

- Function:
**bag-element-count***bag elt* Returns the number of specified element

`elt`in`bag`.(bag-element-count (bag eqv-comparator 1 1 2 2 2 3 3) 2) ⇒ 3

- Function:
**bag-for-each-unique***proc bag* For each unique item in

`bag`, calls`proc`

with two arguments: The item, and the count of the item in the bag.

- Function:
**bag-fold-unique***proc seed bag* For each unique item in

`bag`, calls`proc`with three arguments: The item, the count of the item, and the previous seed value. The`seed`argument provides the initial seed value; the result of`proc`is used for the next seed value, and the last result of`proc`

is returned from`bag-fold-unique`

.(sort (bag-fold-unique acons '() (bag equal-comparator "a" "a" "b" "b" "b" "c" "d")) string<? car) ⇒ (("a" . 2) ("b" . 3) ("c" . 1) ("d" . 1))

- Function:
**bag-increment!***bag elt count* - Function:
**bag-decrement!***bag elt count* Linear update

`bag`to increase or decrease the count of`elt`in it by`count`, which must be an exact integer. Note that the element count won’t get below zero; if a bag has two`a`

’s, and you call`(bag-decrement! bag 'a 100)`

, you get a bag with zero`a`

’s.

- Comparator:
**set-comparator** - Comparator:
**bag-comparator** Comparators to be used to compare sets or bags. They don’t provide comparison procedure, for you cannot define a total order among sets or bags. They do provide hash functions.