►Rebellion
▼4 Collections
►4.10 Multidicts
On this page:
multidict?
multidict
empty-multidict
empty-multidict?
nonempty-multidict?
4.10.1 Persistently Updating Multidicts
multidict-add
multidict-add-entry
multidict-remove
multidict-remove-entry
multidict-replace-values
4.10.2 Querying Multidicts
multidict-size
multidict-ref
multidict-keys
multidict-values
multidict-unique-keys
multidict-unique-values
multidict-entries
multidict-inverse
multidict-contains-key?
multidict-contains-value?
multidict-contains-entry?
4.10.3 Multidict Conversions
multidict->hash
4.10.4 Multidict Iterations and Comprehensions
in-multidict-entries
for/  multidict
for*/  multidict
into-multidict
7.7
  top  ← prev  up  next → 

4.10 Multidicts

 (require rebellion/collection/multidict)
  package: rebellion

A multidict is an unordered collection of key-value mappings, where multiple unique values for the same key are allowed. The implementation of multidicts behaves similarly to a hash from keys to nonempty sets, but the interface is based on a flattened collection of key-value pairs.

procedure

(multidict? v) → boolean?

  v : any/c
A predicate for multidicts.

procedure

(multidict k v ... ...) → multidict?

  k : any/c
  v : any/c
Constructs a multidict containing a mapping from each k to each v. Multiple values are allowed for the same key, but duplicate values for a key are removed. The order of key-value pairs is insignificant. Two multidicts are equal if they contain the same mappings.

Examples:
> (multidict 'a 1 'b 2 'c 3)

(multidict 'a 1 'c 3 'b 2)

> (multidict 'a 1 'a 2 'a 3)

(multidict 'a 1 'a 3 'a 2)

> (multidict 'a 1 'a 1 'b 1)

(multidict 'a 1 'b 1)

value

empty-multidict : empty-multidict?

The empty multidict, which contains nothing.

procedure

(empty-multidict? v) → boolean?

  v : any/c
A predicate for empty multidicts. Implies multidict?.

procedure

(nonempty-multidict? v) → boolean?

  v : any/c
A predicate for nonempty multidicts. Implies multidict?.

4.10.1 Persistently Updating Multidicts

procedure

(multidict-add dict k v) → multidict?

  dict : multidict?
  k : any/c
  v : any/c
Adds a mapping from k to v in dict, returning a new updated multidict. If dict already contains an entry for k and v, then dict is returned unchanged.

Examples:
> (multidict-add (multidict 'a 1) 'b 2)

(multidict 'a 1 'b 2)

> (multidict-add (multidict 'a 1) 'a 2)

(multidict 'a 1 'a 2)

> (multidict-add (multidict 'a 1) 'a 1)

(multidict 'a 1)

procedure

(multidict-add-entry dict e) → multidict?

  dict : multidict?
  e : entry?
Like multidict-add, but with the key and value wrapped in the entry e.

Examples:
> (multidict-add-entry (multidict 'a 1) (entry 'b 2))

(multidict 'a 1 'b 2)

> (multidict-add-entry (multidict 'a 1) (entry 'a 2))

(multidict 'a 1 'a 2)

> (multidict-add-entry (multidict 'a 1) (entry 'a 1))

(multidict 'a 1)

procedure

(multidict-remove dict k v) → multidict?

  dict : multidict?
  k : any/c
  v : any/c
Removes the mapping from k to v from dict, returning an updated multidict. If dict does not contain an entry for k and v, then dict is returned unchanged.

Examples:
> (multidict-remove (multidict 'a 1 'a 2) 'a 1)

(multidict 'a 2)

> (multidict-remove (multidict 'a 1 'a 2) 'b 1)

(multidict 'a 1 'a 2)

procedure

(multidict-remove-entry dict e) → multidict?

  dict : multidict?
  e : entry?
Like multidict-remove, but with the key and value wrapped in the entry e.

Examples:
> (multidict-remove-entry (multidict 'a 1 'a 2) (entry 'a 1))

(multidict 'a 2)

> (multidict-remove-entry (multidict 'a 1 'a 2) (entry 'b 1))

(multidict 'a 1 'a 2)

procedure

(multidict-replace-values dict k vs) → multidict?

  dict : multidict?
  k : any/c
  vs : (sequence/c any/c)
Removes all mappings for k from dict and adds a mapping from k to each element of vs.

Examples:
> (define dict (multidict 'a 1 'b 2 'b 3))
> (multidict-replace-values dict 'a (in-range 1 5))

(multidict 'a 1 'a 3 'a 2 'a 4 'b 3 'b 2)

> (multidict-replace-values dict 'b empty-list)

(multidict 'a 1)

> (multidict-replace-values dict 'c "hello")

(multidict 'a 1 'c #\o 'c #\l 'c #\h 'c #\e 'b 3 'b 2)

4.10.2 Querying Multidicts

procedure

(multidict-size dict) → natural?

  dict : multidict?
Returns the number of key-value mappings in dict. Note that this does not return the number of keys in dict — all values mapped by a key contribute to the returned size.

Examples:
> (multidict-size (multidict 'a 1 'b 2 'c 3))

3

> (multidict-size (multidict 'a 1 'b 2 'b 3))

3

> (multidict-size (multidict 'a 1 'a 1 'a 1))

1

procedure

(multidict-ref dict k) → set?

  dict : multidict?
  k : any/c
Returns the set of values mapped by k in dict.

Examples:
> (define dict
    (multidict 'fruit 'apple
               'fruit 'orange
               'fruit 'banana
               'vegetable 'carrot
               'vegetable 'celery))
> (multidict-ref dict 'fruit)

(set 'apple 'banana 'orange)

> (multidict-ref dict 'vegetable)

(set 'celery 'carrot)

> (multidict-ref dict 'dessert)

(set)

procedure

(multidict-keys dict) → multiset?

  dict : multidict?
Returns a multiset of the keys in dict, with a copy of each key for each value mapped by that key.

Example:
> (multidict-keys
   (multidict 'fruit 'apple
              'fruit 'orange
              'fruit 'banana
              'vegetable 'carrot
              'vegetable 'celery))

(multiset 'vegetable 'vegetable 'fruit 'fruit 'fruit)

procedure

(multidict-values dict) → multiset?

  dict : multidict?
Returns a multiset of all values in dict.

Example:
> (multidict-values
   (multidict "Iron Man" 'marvel
              "Superman" 'dc
              "The Black Panther" 'marvel
              "Wonder Woman" 'dc
              "The Hulk" 'marvel
              "Captain Marvel" 'marvel))

(multiset 'dc 'dc 'marvel 'marvel 'marvel 'marvel)

procedure

(multidict-unique-keys dict) → set?

  dict : multidict?
Returns the set of keys in dict, ignoring duplicates.

Example:
> (multidict-unique-keys
   (multidict 'fruit 'apple
              'fruit 'orange
              'fruit 'banana
              'vegetable 'carrot
              'vegetable 'celery))

(set 'vegetable 'fruit)

procedure

(multidict-unique-values dict) → set?

  dict : multidict?
Returns the set of values in dict, ignoring duplicates.

Example:
> (multidict-unique-values
   (multidict "Iron Man" 'marvel
              "Superman" 'dc
              "The Black Panther" 'marvel
              "Wonder Woman" 'dc
              "The Hulk" 'marvel
              "Captain Marvel" 'marvel))

(set 'dc 'marvel)

procedure

(multidict-entries dict) → (set/c entry?)

  dict : multidict?
Returns the (immutable) set of entries in dict. Note that this is not a multiset, because for each key the collection of values mapped by that key contains no duplicates.

Example:
> (multidict-entries
   (multidict 'fruit 'apple
              'fruit 'orange
              'fruit 'banana
              'vegetable 'carrot
              'vegetable 'celery))

(set

 (entry 'vegetable 'celery)

 (entry 'vegetable 'carrot)

 (entry 'fruit 'orange)

 (entry 'fruit 'banana)

 (entry 'fruit 'apple))

procedure

(multidict-inverse dict) → multidict?

  dict : multidict?
Inverts dict, returning a multidict with all the same entries as dict except keys and values are swapped.

Example:
> (multidict-inverse
   (multidict 'a 1
              'a 2
              'a 3
              'b 2
              'b 4
              'c 4
              'c 1
              'd 3))

(multidict 1 'a 1 'c 3 'a 3 'd 2 'a 2 'b 4 'c 4 'b)

procedure

(multidict-contains-key? dict k) → boolean?

  dict : multidict?
  k : any/c
Returns #t if dict contains any mappings for the key k, returns #f otherwise.

Examples:
> (define dict (multidict 'even 2 'even 4 'odd 1 'odd 5 'odd 3))
> (multidict-contains-key? dict 'even)

#t

> (multidict-contains-key? dict 'prime)

#f

procedure

(multidict-contains-value? dict v) → boolean?

  dict : multidict?
  v : any/c
Returns #t if dict contains any mappings with the value v, returns #f otherwise.

Examples:
> (define dict (multidict 'even 2 'even 4 'odd 1 'odd 5 'odd 3))
> (multidict-contains-value? dict 5)

#t

> (multidict-contains-value? dict "hello world")

#f

procedure

(multidict-contains-entry? dict e) → boolean?

  dict : multidict?
  e : entry?
Returns #t if dict contains the mapping e, returns #f otherwise.

Examples:
> (define dict (multidict 'even 2 'even 4 'odd 1 'odd 5 'odd 3))
> (multidict-contains-entry? dict (entry 'even 4))

#t

> (multidict-contains-entry? dict (entry 'odd 4))

#f

4.10.3 Multidict Conversions

procedure

(multidict->hash dict)

 → (hash/c any/c nonempty-set? #:immutable #t)
  dict : multidict?
Converts dict into a hash table from keys to (nonempty) sets of values.

Example:
> (multidict->hash
   (multidict 'fruit 'apple
              'fruit 'orange
              'fruit 'banana
              'vegetable 'carrot
              'vegetable 'celery))

(hash 'fruit (set 'apple 'banana 'orange) 'vegetable (set 'celery 'carrot))

4.10.4 Multidict Iterations and Comprehensions

procedure

(in-multidict-entries dict) → (sequence/c entry?)

  dict : multidict?
Returns a sequence of the entries in dict.

Examples:
> (define food-classifications
    (multidict 'fruit 'apple
               'vegetable 'carrot
               'fruit 'orange
               'fruit 'banana
               'vegetable 'celery))
> (for ([e (in-multidict-entries food-classifications)])
    (printf "key: ~a  value: ~a\n"
            (entry-key e)
            (entry-value e)))

key: vegetable  value: celery

key: vegetable  value: carrot

key: fruit  value: apple

key: fruit  value: banana

key: fruit  value: orange

syntax

(for/multidict (for-clause ...) body-or-break ... body)

 
  body : entry?
Iterates like for, but collects each entry returned by body into a multidict.

syntax

(for*/multidict (for-clause ...) body-or-break ... body)

 
  body : entry?
Iterates like for*, but collects each entry returned by body into a multidict.

value

into-multidict : (reducer/c entry? multidict?)

A reducer that reduces a sequence of entries into a multidict.

  top  ← prev  up  next →