►Rebellion
▼4 Collections
►4.9 Multisets
On this page:
multiset?
multiset
multiset-of-frequencies
empty-multiset
4.9.1 Querying Multisets
multiset-size
multiset-frequency
multiset-frequencies
multiset-contains?
multiset-contains-all?
multiset-contains-any?
multiset-contains-none?
multiset-unique-elements
4.9.2 Persistently Updating Multisets
multiset-add
multiset-add-all
multiset-remove
multiset-remove-all
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
8.12
  top  contents    up   

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)

procedure

(multiset-of-frequencies frequency ...) → multiset?

  frequency : (entry/c any/c natural?)
Constructs a multiset where each frequency entry specifies how many copies of an element the multiset should contain. The element to add is specified by the key of the frequency entry, while the mapped value in the entry is the count. Each frequency should be for a unique element, or else a contract exception is raised.

Example:
> (multiset-of-frequencies (entry 'apple 2) (entry 'banana 3))

(multiset 'apple 'apple 'banana 'banana 'banana)

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 #true if set contains v, #false 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-contains-all? set seq) → boolean?

  set : multiset?
  seq : (sequence/c any/c)
Returns #true if set contains every element of seq, returns #false otherwise. The quantity of duplicate elements in set and seq does not affect the result. This function is equivalent to looping over seq with multiset-contains?, except it can be faster if seq is also a multiset.

Examples:
> (multiset-contains-all? (multiset 1 1 1 2 3 3) (list 1 2 3))

#t

> (multiset-contains-all? (multiset 1 1 1 2 3 3) (list 1 2 3 4))

#f

> (multiset-contains-all? (multiset 1 1 1 2 3 3) (list 1 1 1 1 1 1 1))

#t

procedure

(multiset-contains-any? set seq) → boolean?

  set : multiset?
  seq : (sequence/c any/c)
Returns #true if set contains at least one element of seq, returns #false otherwise. Returns #false if seq is empty.

Examples:
> (multiset-contains-any? (multiset 1 2 3) (list 2 4 6))

#t

> (multiset-contains-any? (multiset 1 2 3) (list 10 20 30))

#f

procedure

(multiset-contains-none? set seq) → boolean?

  set : multiset?
  seq : (sequence/c any/c)
Returns #true if set does not contain any element of seq, returns #false otherwise. Returns #true if seq is empty.

Examples:
> (multiset-contains-none? (multiset 1 2 3) (list 2 4 6))

#f

> (multiset-contains-none? (multiset 1 2 3) (list 10 20 30))

#t

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

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. This function is equivalent to looping over seq with multiset-add, except it can be faster if seq is also a multiset.

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-remove-all set seq) → multiset?

  set : multiset?
  seq : (sequence/c any/c)
Removes each element of seq from set, returning an updated multiset. The original set is not mutated. This function is equivalent to looping over seq with multiset-remove, except it can be faster if seq is also a multiset.

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

(multiset 1)

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

(multiset 3 3 2)

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

8

8

8

5

5

3

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 #\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.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))

'(c c c b a a d)

procedure

(sequence->multiset seq) → multiset?

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

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

(multiset 4 3 2 1 0)

  top  contents    up