8.0

#### 4.9Multisets

 (require rebellion/collection/multiset) package: rebellion

A multiset is an unordered collection, like a set, except it can contain duplicate elements. Elements are always compared with equal?.

 procedure v : any/c
A predicate for multisets.

 procedure(multiset v ...) → multiset? v : any/c
Constructs a multiset containing the given vs.

Examples:
 > (multiset 'apple 'orange 'banana) (multiset 'apple 'banana 'orange) > (multiset 'apple 'orange 'orange 'banana) (multiset 'apple 'banana 'orange 'orange) > (multiset) (multiset)

 value
The empty multiset, which contains no elements.

##### 4.9.1Querying Multisets

 procedure(multiset-size set) → natural? set : multiset?
Returns the total number of elements in set, including duplicates.

Examples:
 > (define set (multiset 5 8 8 8)) > (multiset-size set) 4

 procedure(multiset-frequency set v) → natural? set : multiset? v : any/c
Returns the number of times that set contains v.

Examples:
 > (define set (multiset 5 8 8 8)) > (multiset-frequency set 5) 1 > (multiset-frequency set 8) 3 > (multiset-frequency set 'apple) 0

 procedure(multiset-frequencies set) → (immutable-hash/c any/c exact-positive-integer?) set : multiset?
Returns a hash mapping the unique elements of set to the number of times they occur in set.

Example:
 > (multiset-frequencies (multiset 'red 'red 'red 'blue 'green 'green 'green 'green))

'#hash((blue . 1) (green . 4) (red . 3))

 procedure(multiset-contains? set v) → boolean? set : multiset? v : any/c
Returns #t if set contains v, #f otherwise.

Examples:
 > (define set (multiset 'apple 'orange 'orange)) > (multiset-contains? set 'apple) #t > (multiset-contains? set 'orange) #t > (multiset-contains? set 42) #f

 procedure set : multiset?
Removes all duplicate elements from set, returning the resulting set.

Example:
 > (multiset-unique-elements (multiset 5 8 8 8 13 13)) (set 5 8 13)

##### 4.9.2Persistently Updating Multisets

Multisets are always immutable. The following update operations return new multisets and leave the input multiset unchanged. However, multisets are implemented with an efficient persistent data structure that allows the modified multisets to share their structure with the input multiset. The precise performance characteristics of these operations are not specified at this time, but their running times are all sublinear in the number of distinct elements in the modified multiset.

procedure

 (multiset-add set element [ #:copies num-copies]) → multiset?
set : multiset?
element : any/c
num-copies : natural? = 1
Adds element to set, returning an updated multiset. If copies is specified, then element is added num-copies times instead of only once.

Examples:
 > (multiset-add (multiset 'apple 'orange 'banana) 'grape) (multiset 'grape 'apple 'banana 'orange) > (multiset-add (multiset 'apple 'orange 'banana) 'orange) (multiset 'apple 'banana 'orange 'orange) > (multiset-add (multiset 'apple 'orange 'banana) 'orange #:copies 5) (multiset 'apple 'banana 'orange 'orange 'orange 'orange 'orange 'orange)

 procedure(multiset-add-all set seq) → multiset? set : multiset? seq : (sequence/c any/c)
Adds seq elements into set, returning an updated multiset. The original set is not mutated.

Examples:
 > (multiset-add-all (multiset 1 1 2 3) (in-range 0 5)) (multiset 4 3 3 2 2 1 1 1 0) > (multiset-add-all (multiset 1 2 3) (multiset 1 2 3)) (multiset 3 3 2 2 1 1)

procedure

 (multiset-remove set element [ #:copies num-copies]) → multiset?
set : multiset?
element : any/c
num-copies : (or/c natural? +inf.0) = 1
Removes a single element from set, returning an updated multiset. If num-copies is specified then instead that many copies of element are removed from set, removing all occurrences if num-copies is +inf.0 or if set contains fewer occurrences of element than num-copies.

Examples:
 (define set (multiset 'blue 'blue 'red 'red 'red 'green)) > (multiset-remove set 'red) (multiset 'blue 'blue 'red 'red 'green) > (multiset-remove set 'red #:copies 2) (multiset 'blue 'blue 'red 'green) > (multiset-remove set 'red #:copies 5) (multiset 'blue 'blue 'green) > (multiset-remove set 'blue #:copies +inf.0) (multiset 'red 'red 'red 'green) > (multiset-remove set 'orange) (multiset 'blue 'blue 'red 'red 'red 'green)

procedure

 (multiset-set-frequency set element frequency) → multiset?
set : multiset?
element : any/c
frequency : natural?
Adds or removes copies of element to or from set until it occurs exactly frequency times in set. If frequency is zero, this is equivalent to removing all copies of element from set.

Examples:
 > (multiset-set-frequency (multiset 'red 'red 'blue 'green) 'blue 4) (multiset 'blue 'blue 'blue 'blue 'red 'red 'green) > (multiset-set-frequency (multiset 'red 'red 'blue 'green) 'blue 0) (multiset 'red 'red 'green)

##### 4.9.3Multiset Iteration and Comprehension

 procedure(in-multiset set) → sequence? set : multiset?
Returns a sequence that iterates over the elements of set, including duplicates.

Examples:
> (define set (multiset 5 8 8 8 5 3))
 > (for ([v (in-multiset set)]) (displayln v))
 8 8 8 5 5 3

 value
A reducer that collects elements into a multiset.

Example:
 > (reduce-all into-multiset (in-string "happy birthday!")) (multiset #\h #\h #\y #\y #\i #\t #\d #\r #\b #\a #\a #\! #\p #\p #\space)

 syntax(for/multiset (for-clause ...) body-or-break ... body)
Like for, but collects the iterated values into a multiset.

Example:
 > (for/multiset ([char (in-string "Hello World")]) (cond [(char-whitespace? char) 'whitespace] [(char-upper-case? char) 'uppercase-letter] [else 'lowercase-letter]))
 (multiset 'uppercase-letter 'uppercase-letter 'whitespace 'lowercase-letter 'lowercase-letter 'lowercase-letter 'lowercase-letter 'lowercase-letter 'lowercase-letter 'lowercase-letter 'lowercase-letter)

 syntax(for*/multiset (for-clause ...) body-or-break ... body)
Like for*, but collects the iterated values into a multiset.

Example:
 > (for*/multiset ([str (in-list (list "the" "quick" "brown" "fox"))] [char (in-string str)]) char)

(multiset #\o #\o #\n #\k #\i #\w #\f #\t #\c #\q #\x #\h #\u #\e #\r #\b)

##### 4.9.4Multiset Conversions

 procedure(multiset->list set) → list? set : multiset?
Returns a list of all the elements of set. Duplicate elements are adjacent in the returned list, but the order of unequal elements is unspecified and should not be relied upon.

Example:
 > (multiset->list (multiset 'a 'a 'b 'c 'c 'c 'd)) '(c c c b a a d)

 procedure seq : sequence?
Returns a multiset containing the elements of seq, including duplicates.

Example:
 > (sequence->multiset (in-range 5)) (multiset 4 3 2 1 0)