For Gauche 0.9.5

Next: , Previous: , Up: Library modules - SRFIs   [Contents][Index]

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

Constructors

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

Predicates

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.

Accessors

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.

Updaters

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

The whole set

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.

Mapping and folding

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.

Copying and conversion

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

Subsets

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.

Set theory operations

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.

Bag-specific procedures

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.

Comparators

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.

Next: , Previous: , Up: Library modules - SRFIs   [Contents][Index]