Version: 5.1.1.2
4 Collection Datatypes
4.1 Sets
This module provides tools for representing finite sets.
4.1.1 Set Constructors
(set | [ | #:mutable? mutable? | | | | | | | #:weak? weak? | | | | | | | #:compare compare] | | | | | | | x ...) | | → | | set? |
|
mutable? : boolean? = weak? |
weak? : boolean? = #f |
compare : (or/c 'eq 'eqv 'equal) = 'equal |
x : any/c |
Produces a hash table-based set using the hash table properties described by
any keyword arguments, and the given values as elements of the set.
Examples: |
> (set 1 2 3) | '#hash((1) (2) (3)) | > (set #:mutable? #t 1 2 3) | '#hash((1) (2) (3)) | > (set #:weak? #t 1 2 3) | '#hash((1) (2) (3)) | > (set #:compare 'eqv 1 2 3) | '#hasheqv((1) (2) (3)) |
|
Produces an empty hash table-based set using the hash table properties described
by any keyword arguments.
Produces a hash table-based set using the hash table properties described by
any keyword arguments, with the elements of the given list as the elements of
the set.
Examples: |
> (list->set '(1 2 3)) | '#hash((1) (2) (3)) | > (list->set #:mutable? #t '(1 2 3)) | '#hash((1) (2) (3)) | > (list->set #:weak? #t '(1 2 3)) | '#hash((1) (2) (3)) | > (list->set #:compare 'eqv '(1 2 3)) | '#hasheqv((1) (2) (3)) |
|
Produces a custom hash table-based set using the given equality predicate
equiv? and optional hash functions hash-primary and
hash-secondary. If no hash functions are given, they default to a
degenerate hash function, resulting in an effectively list-based set. The set
is populated with the given elem values.
4.1.2 Set Accessors
Reports whether s contains x.
Reports whether a set is empty.
Reports the number of elements in s.
Reports whether two sets contain the same elements.
Reports whether b contains all of the elements of a.
Reports whether b contains all of the elements of a, and at
least one element not in a.
Produces a list containing the elements of s.
Produces a sequence iterating over the elements of the set.
4.1.3 Set Updaters
Produces a new version of s containing x.
Produces a new version of s that does not contain x.
Mutates s to contain x.
Examples: |
| > s | '#hash((1) (2) (3)) | > (set-insert! s 4) | > s | '#hash((1) (2) (3) (4)) | > (set-insert! s 1) | > s | '#hash((1) (2) (3) (4)) |
|
Mutates x so as not to contain x.
Produces a new version of s0 containing all the elements in each
s.
Produces a new version of s0 containing only those elements found in
every s.
Produces a new version of s0 containing only those elements not found
in any s.
Produces a new version of s0 containing only those elements found in
s0 and each s an odd number of times.
4.1.4 Set Predicates
Examples: |
> (set? '(1 2)) | #f | > (set? '((1 . one) (2 . two))) | #t |
|
4.1.5 Structures as Sets
Property for structurs as
sets. Its value must be a vector of 7
elements, as follows:
a binary function implementing set-contains?,
a binary function implementing set-insert!, or #f if not
supported,
a binary function implementing set-insert, or #f if not
supported,
a binary function implementing set-remove!, or #f if not
supported,
a binary function implementing set-remove, or #f if
not supported,
a unary function implementing set-count,
and a unary function implementing in-set.
Examples: |
| (define (never-insert! set elem) (error 'set-insert! "always empty!")) | |
| | | | | | (define-struct always-empty [] | #:transparent | #:property prop:set | (vector never-contains? | never-insert! | never-insert | never-remove! | never-remove | always-zero | no-elements)) | |
| > (set? (make-always-empty)) | #t | > (set-contains? (make-always-empty) 1) | #f | > (set-insert! (make-always-empty) 2) | set-insert!: always empty! | > (set-insert (make-always-empty) 3) | set-insert: always empty! | > (set-remove (make-always-empty) 4) | (always-empty ) | > (set-remove! (make-always-empty) 5) | > (set-count (make-always-empty)) | 0 | |
|
4.2 Dictionaries
This module provides tools for manipulating dictionary values.
4.2.1 Dictionary Constructors
Constructs an empty hash table based on the behavior specified by
mutable?, weak?, and compare.
Converts a given dictionary d to a hash table based on the behavior
specified by mutable?, weak?, and compare.
Examples: |
> (make-dict '([1 . one] [2 . two])) | '#hash((1 . one) (2 . two)) | > (make-dict '([1 . one] [2 . two]) #:mutable? #t) | '#hash((1 . one) (2 . two)) | > (make-dict '([1 . one] [2 . two]) #:weak? #t) | '#hash((1 . one) (2 . two)) | > (make-dict '([1 . one] [2 . two]) #:compare 'eqv) | '#hasheqv((1 . one) (2 . two)) |
|
Constructs a dictionary based on custom comparison and optional hash functions.
Given no hash functions, the dictionary defaults to a degenerate hash function
and is thus essentially equivalent to a list-based dictionary.
4.2.2 Dictionary Lookup
Looks up key k in dictionary d. If d has no entry
for k, updates d to map k to the result of
(v) (if v is a procedure) or v (otherwise), and
returns the new mapping.
Examples: |
| > (dict-set! d 1 'one) | > (dict-set! d 2 'two) | > d | '#hash((1 . one) (2 . two)) | > (dict-ref! d 2 'dos) | 'two | > d | '#hash((1 . one) (2 . two)) | > (dict-ref! d 3 'tres) | 'tres | > d | '#hash((1 . one) (2 . two) (3 . tres)) | > (dict-ref! d 4 gensym) | 'g2511 | > d | '#hash((1 . one) (2 . two) (3 . tres) (4 . g2511)) |
|
Looks up key
k in dictionary
d. Raises a contract error if
d has no entry for
k. Equivalent to
(dict-ref d k),
except for the specific exception value raised.
Looks up key
k in dictionary
d. Returns
k if
d has no entry for
k. Equivalent to
(dict-ref d k (lambda () k)).
Looks up key
k in dictionary
d. Returns
v if
d has no entry for
k. Equivalent to
(dict-ref d k (lambda () v)).
Looks up key
k in dictionary
d. Returns the result of
applying
f (in tail position) if
d has no entry for
k. Equivalent to
(dict-ref d k f).
4.2.3 Dictionary Accessors
Reports whether d is empty (has no keys).
Reports whether d has an entry for k.
Produces the domain of a dictionary as a list of keys.
Example: |
> (dict-domain '([1 . one] [2 . two] [3 . three])) | '(1 2 3) |
|
Produces the range of a dictionary as a list of values.
Example: |
> (dict-range '([1 . one] [2 . two] [3 . three])) | '(one two three) |
|
4.2.4 Dictionary Combinations
Computes the union of d0 with each dictionary d by functional
update, adding each element of each d to d0 in turn. For each
key k and value v, if a mapping from k to some value
v0 already exists, it is replaced with a mapping from k to
(combine/key k v0 v).
Examples: |
> (dict-union '([1 . one]) '([2 . two]) '([3 . three])) | '((1 . one) (2 . two) (3 . three)) | > (dict-union '([1 one uno] [2 two dos]) | '([1 ein une] [2 zwei deux]) | #:combine/key (lambda (k v1 v2) (append v1 v2))) |
| '((1 one uno ein une) (2 two dos zwei deux)) |
|
Computes the union of d0 with each dictionary d by mutable
update, adding each element of each d to d0 in turn. For each
key k and value v, if a mapping from k to some value
v0 already exists, it is replaced with a mapping from k to
(combine/key k v0 v).
Examples: |
| > d | '#hash() | > (dict-union! d '([1 one uno] [2 two dos])) | > d | '#hash((1 . (one uno)) (2 . (two dos))) | | > d | '#hash((1 . (one uno ein une)) (2 . (two dos zwei deux))) |
|
4.2.5 Dictionary Structure Properties
Produces a value appropriate for
prop:dict for a derived dictionary
type recognized by
pred. Dictionaries constructed from this property
will extract a nested dictionary using
unwrap and will produce a
wrapped dictionary during functional update using
wrap.
Examples: |
| > (dict? (make-table '([1 . one] [2 . two]))) | #t | > (dict-ref (make-table '([1 . one] [2 . two])) 1) | 'one | > (dict-set (make-table '([1 . one] [2 . two])) 3 'three) | (table '((1 . one) (2 . two) (3 . three))) |
|
4.2.6 Contracted Dictionaries
This library re-provides dict/c from
(planet cce/scheme:7:4/contract).
4.3 Hash Tables
This module provides tools for manipulating hash tables.
4.3.1 Hash Table Construction
(hash immutable-hash-type [key-expr value-expr] ...) |
|
immutable-hash-type | | = | | | | | | | | #:eq | | | | | | #:eqv | | | | | | #:equal |
|
Produces an immutable hash table based on the given comparison, defaulting to
#:equal, and mapping the result of each key-expr to the result
of each value-expr.
Examples: |
> (hash ['one 1] ['two 2]) | '#hash((one . 1) (two . 2)) | > (hash #:eq ['one 1] ['two 2]) | '#hasheq((one . 1) (two . 2)) | > (hash #:eqv ['one 1] ['two 2]) | '#hasheqv((one . 1) (two . 2)) | > (hash #:equal ['one 1] ['two 2]) | '#hash((one . 1) (two . 2)) |
|
(hash! mutable-hash-spec [key-expr value-expr] ...) |
|
mutable-hash-spec | | = | | mutable-hash-type mutable-hash-weak | | | | | | mutable-hash-weak mutable-hash-type | | | | | | mutable-hash-type | | = | | | | | | | | #:eq | | | | | | #:eqv | | | | | | #:equal | | | | | | mutable-hash-weak | | = | | | | | | | | #:weak |
|
Produces a mutable hash table based on the given comparison and weakness
specification, defaulting to #:equal and not #:weak, and
mapping the result of each key-expr to the result of each
value-expr.
Examples: |
> (hash! ['one 1] ['two 2]) | '#hash((one . 1) (two . 2)) | > (hash! #:eq ['one 1] ['two 2]) | '#hasheq((one . 1) (two . 2)) | > (hash! #:eqv #:weak ['one 1] ['two 2]) | '#hasheqv((one . 1) (two . 2)) | > (hash! #:weak #:equal ['one 1] ['two 2]) | '#hash((one . 1) (two . 2)) |
|
4.3.2 Hash Table Lookup
Looks up key
k in hash table
h. Raises a contract error if
h has no entry for
k. Equivalent to
(hash-ref h k),
except for the specific exception value raised.
Looks up key
k in hash table
h. Returns
k if
h has no entry for
k. Equivalent to
(hash-ref h k (lambda () k)).
Looks up key
k in hash table
h. Returns
v if
h has no entry for
k. Equivalent to
(hash-ref h k (lambda () v)).
Looks up key
k in hash table
h. Returns the result of
applying
f (in tail position) if
h has no entry for
k. Equivalent to
(hash-ref h k f).
4.3.3 Hash Table Accessors
Reports whether
h maps keys according to
equal?.
Reports whether
h has an entry for
k. This function is
re-exported from
scheme/base. In versions of PLT Scheme before
hash-has-key? was implemented, this module provides its own definition.
Produces the domain of a hash table as a list of keys.
Produces the range of a hash table as a list of values.
4.3.4 Hash Table Combinations
Computes the union of h0 with each hash table h by functional
update, adding each element of each h to h0 in turn. For each
key k and value v, if a mapping from k to some value
v0 already exists, it is replaced with a mapping from k to
(combine/key k v0 v).
Computes the union of h0 with each hash table h by mutable
update, adding each element of each h to h0 in turn. For each
key k and value v, if a mapping from k to some value
v0 already exists, it is replaced with a mapping from k to
(combine/key k v0 v).
Examples: |
| > h | '#hash() | > (hash-union! h (make-immutable-hash '([1 one uno] [2 two dos]))) | > h | '#hash((1 . (one uno)) (2 . (two dos))) | | > h | '#hash((1 . (one uno ein une)) (2 . (two dos zwei deux))) |
|
4.4 Imperative Queues
This module provides a mutable queue representation.
Produces an empty queue.
Adds an element to the back of a queue.
Removes an element from the front of a nonempty queue, and returns that element.
Recognizes whether a queue is empty or not.
This predicate recognizes queues.
These contracts recognize queues; the latter requires the queue to contain at
least one value.