►Rebellion
▼4 Collections
►4.9 Multisets
On this page:
multiset?
multiset
empty-multiset
4.9.1 Querying Multisets
multiset-size
multiset-frequency
multiset-frequencies
multiset-contains?
multiset-unique-elements
4.9.2 Persistently Updating Multisets
multiset-add
multiset-add-all
multiset-remove
multiset-set-frequency
4.9.3 Multiset Iteration and Comprehension
in-multiset
into-multiset
for/  multiset
for*/  multiset
4.9.4 Multiset Conversions
multiset->list
sequence->multiset
7.7
  top  ← prev  up  next → 

4.9 Multisets

 (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

(multiset? v) → boolean?

  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

empty-multiset : multiset? = (multiset)

The empty multiset, which contains no elements.

4.9.1 Querying 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

(multiset-unique-elements set) → set?

  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 13 8)

4.9.2 Persistently 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 1 1 1 3 3 0 2 2 4)

> (multiset-add-all (multiset 1 2 3) (multiset 1 2 3))

(multiset 1 1 3 3 2 2)

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 'red 'red 'blue 'blue 'green)

> (multiset-remove set 'red #:copies 2)

(multiset 'red 'blue 'blue '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 'red 'red 'red 'blue 'blue '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 'red 'red 'blue 'blue 'blue 'blue 'green)

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

(multiset 'red 'red 'green)

4.9.3 Multiset 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))

5

5

3

8

8

8

value

into-multiset : (reducer/c any/c multiset?)

A reducer that collects elements into a multiset.

Example:
> (reduce-all into-multiset (in-string "happy birthday!"))

(multiset #\p #\p #\t #\y #\y #\r #\space #\d #\h #\h #\! #\a #\a #\i #\b)

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

 'whitespace

 'lowercase-letter

 'lowercase-letter

 'lowercase-letter

 'lowercase-letter

 'lowercase-letter

 'lowercase-letter

 'lowercase-letter

 'lowercase-letter

 'uppercase-letter

 'uppercase-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 #\k #\o #\o #\w #\t #\x #\q #\u #\n #\r #\c #\h #\e #\i #\b #\f)

4.9.4 Multiset 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))

'(a a d c c c b)

procedure

(sequence->multiset seq) → multiset?

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

Example:
> (sequence->multiset (in-range 5))

(multiset 1 3 0 2 4)

  top  ← prev  up  next →