4 Collection Datatypes
4.1 Sets
(require (planet cce/scheme:7:2/set)) |
This module provides tools for representing finite sets.
4.1.1 Set Constructors
| ||||||||||||||||||||||||||||
mutable? : boolean? = weak? | ||||||||||||||||||||||||||||
weak? : boolean? = #f | ||||||||||||||||||||||||||||
compare : (or/c 'eq 'eqv 'equal) = 'equal | ||||||||||||||||||||||||||||
x : any/c |
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)) |
| |||||||||||||||||||||
mutable? : boolean? = weak? | |||||||||||||||||||||
weak? : boolean? = #f | |||||||||||||||||||||
compare : (or/c 'eq 'eqv 'equal) = 'equal |
Examples: |
> (empty-set) |
'#hash() |
> (empty-set #:mutable? #t) |
'#hash() |
> (empty-set #:weak? #t) |
'#hash() |
> (empty-set #:compare 'eqv) |
'#hasheqv() |
| ||||||||||||||||||||||||||||
mutable? : boolean? = weak? | ||||||||||||||||||||||||||||
weak? : boolean? = #f | ||||||||||||||||||||||||||||
compare : (or/c 'eq 'eqv 'equal) = 'equal | ||||||||||||||||||||||||||||
lst : list? |
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)) |
| ||||||||||||||||||||||||||||||||||||||||||
compare : (-> any/c any/c any/c) | ||||||||||||||||||||||||||||||||||||||||||
hash : (-> any/c exact-integer?) = (lambda (x) 0) | ||||||||||||||||||||||||||||||||||||||||||
hash2 : (-> any/c exact-integer?) = (lambda (x) 0) | ||||||||||||||||||||||||||||||||||||||||||
mutable? : boolean? = weak? | ||||||||||||||||||||||||||||||||||||||||||
weak? : boolean? = #f | ||||||||||||||||||||||||||||||||||||||||||
elem : any/c |
Examples: | |||||
| |||||
> (set->list singularity) | |||||
'(one) | |||||
> (set-insert! singularity 'four) | |||||
> (set->list singularity) | |||||
'(one) | |||||
> (set-remove! singularity 'zero) | |||||
> (set->list singularity) | |||||
'() |
4.1.2 Set Accessors
(set-contains? s x) → boolean? |
s : set? |
x : any/c |
Examples: |
> (set-contains? (set 1 2 3) 1) |
#t |
> (set-contains? (set 1 2 3) 4) |
#f |
(set-empty? s) → boolean? |
s : set? |
Examples: |
> (set-empty? '()) |
#t |
> (set-empty? '((1 . one))) |
#f |
(set-count s) → exact-nonnegative-integer? |
s : set? |
Examples: |
> (set-count (set)) |
0 |
> (set-count (set 1 2 3)) |
3 |
Examples: |
> (set=? (set 1) (set 1 2 3)) |
#f |
> (set=? (set 1 2 3) (set 1)) |
#f |
> (set=? (set 1 2 3) (set 1 2 3)) |
#t |
Examples: |
> (subset? (set 1) (set 1 2 3)) |
#t |
> (subset? (set 1 2 3) (set 1)) |
#f |
> (subset? (set 1 2 3) (set 1 2 3)) |
#t |
(proper-subset? a b) → boolean? |
a : set? |
b : set? |
Examples: |
> (proper-subset? (set 1) (set 1 2 3)) |
#t |
> (proper-subset? (set 1 2 3) (set 1)) |
#f |
> (proper-subset? (set 1 2 3) (set 1 2 3)) |
#f |
Example: |
> (set->list (set 1 2 3)) |
'(1 2 3) |
Example: |
> (for/list ([x (in-set (set 1 2 3))]) x) |
'(1 2 3) |
4.1.3 Set Updaters
(set-insert s x) → set? |
s : set? |
x : any/c |
Examples: |
> (set-insert (set 1 2 3) 4) |
'#hash((1) (2) (3) (4)) |
> (set-insert (set 1 2 3) 1) |
'#hash((1) (2) (3)) |
(set-remove s x) → set? |
s : set? |
x : any/c |
Examples: |
> (set-remove (set 1 2 3) 1) |
'#hash((2) (3)) |
> (set-remove (set 1 2 3) 4) |
'#hash((1) (2) (3)) |
(set-insert! s x) → void? |
s : set? |
x : any/c |
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)) |
(set-remove! s x) → void? |
s : set? |
x : any/c |
Examples: | ||
| ||
> s | ||
'#hash((1) (2) (3)) | ||
> (set-remove! s 1) | ||
> s | ||
'#hash((2) (3)) | ||
> (set-remove! s 4) | ||
> s | ||
'#hash((2) (3)) |
Example: |
> (set-union (set 1 2) (set 1 3) (set 2 3)) |
'#hash((1) (2) (3)) |
(set-intersection s0 s ...) → set? |
s0 : (and/c set? set-can-remove?) |
s : set? |
Example: |
> (set-intersection (set 1 2 3) (set 1 2) (set 2 3)) |
'#hash((2)) |
(set-difference s0 s ...) → set? |
s0 : (and/c set? set-can-remove?) |
s : set? |
Example: |
> (set-difference (set 1 2 3) (set 1) (set 3)) |
'#hash((2)) |
(set-exclusive-or s0 s ...) → set? |
s0 : (and/c set? set-can-insert? set-can-remove?) |
s : set? |
Example: |
> (set-exclusive-or (set 1) (set 1 2) (set 1 2 3)) |
'#hash((1) (3)) |
4.1.4 Set Predicates
Examples: |
> (set? '(1 2)) |
#f |
> (set? '((1 . one) (2 . two))) |
#t |
| ||
| ||
| ||
|
Examples: | ||
| ||
> (set-can-insert? functional-set) | ||
#t | ||
> (set-can-remove? functional-set) | ||
#t | ||
> (set-can-insert!? functional-set) | ||
#f | ||
> (set-can-remove!? functional-set) | ||
#f | ||
| ||
> (set-can-insert? imperative-set) | ||
#f | ||
> (set-can-remove? imperative-set) | ||
#f | ||
> (set-can-insert!? imperative-set) | ||
#t | ||
> (set-can-remove!? imperative-set) | ||
#t |
4.1.5 Structures as Sets
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: | |||||||||||
| |||||||||||
| |||||||||||
| |||||||||||
| |||||||||||
| |||||||||||
| |||||||||||
| |||||||||||
| |||||||||||
> (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
(require (planet cce/scheme:7:2/dict)) |
This module provides tools for manipulating dictionary values.
4.2.1 Dictionary Constructors
| |||||||||||||||||||||
mutable? : boolean? = weak? | |||||||||||||||||||||
weak? : boolean? = #f | |||||||||||||||||||||
compare : (or/c 'eq 'eqv 'equal) = equal |
Examples: |
> (empty-dict) |
'#hash() |
> (empty-dict #:mutable? #t) |
'#hash() |
> (empty-dict #:weak? #t) |
'#hash() |
> (empty-dict #:compare 'eqv) |
'#hasheqv() |
| ||||||||||||||||||||||||||||
d : dict? | ||||||||||||||||||||||||||||
mutable? : boolean? = weak? | ||||||||||||||||||||||||||||
weak? : boolean? = #f | ||||||||||||||||||||||||||||
compare : (or/c 'eq 'eqv 'equal) = equal |
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)) |
| |||||||||||||||||||||||||||||||||||
equiv? : (-> any/c any/c any/c) | |||||||||||||||||||||||||||||||||||
hash-primary : (-> any/c exact-integer?) = (lambda (x) 0) | |||||||||||||||||||||||||||||||||||
hash-secondary : (-> any/c exact-integer?) = (lambda (x) 0) | |||||||||||||||||||||||||||||||||||
mutable? : boolean? = weak? | |||||||||||||||||||||||||||||||||||
weak? : boolean? = #f |
Examples: | ||
| ||
> (dict-set! table 1 'one) | ||
> (dict-set! table 2 'two) | ||
| ||
'((2 . two) (1 . one)) |
4.2.2 Dictionary Lookup
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) | ||
'g2414 | ||
> d | ||
'#hash((1 . one) (2 . two) (3 . tres) (4 . g2414)) |
(dict-ref/check d k) → any/c |
d : dict? |
k : (lambda (k) (dict-has-key? d k)) |
Example: |
> (dict-ref/check '([1 . one] [2 . two] [3 . three]) 2) |
'two |
(dict-ref/identity d k) → any/c |
d : dict? |
k : any/c |
Examples: |
> (dict-ref/identity '([1 . one] [2 . two] [3 . three]) 2) |
'two |
> (dict-ref/identity '([1 . one] [2 . two] [3 . three]) 4) |
4 |
(dict-ref/default d k v) → any/c |
d : dict? |
k : any/c |
v : any/c |
Examples: |
> (dict-ref/default '([1 . one] [2 . two] [3 . three]) 2 'other) |
'two |
> (dict-ref/default '([1 . one] [2 . two] [3 . three]) 4 'other) |
'other |
Examples: |
> (dict-ref/failure '([1 . one] [2 . two] [3 . three]) 2 gensym) |
'two |
> (dict-ref/failure '([1 . one] [2 . two] [3 . three]) 4 gensym) |
'g2557 |
4.2.3 Dictionary Accessors
(dict-empty? d) → boolean? |
d : dict? |
Examples: |
> (dict-empty? '()) |
#t |
> (dict-empty? '([1 . one] [2 . two])) |
#f |
(dict-has-key? d k) → boolean? |
d : dict? |
k : any/c |
Examples: |
> (dict-has-key? '([1 . one] [2 . two] [3 . three]) 2) |
#t |
> (dict-has-key? '([1 . one] [2 . two] [3 . three]) 4) |
#f |
(dict-domain d) → list? |
d : dict? |
Example: |
> (dict-domain '([1 . one] [2 . two] [3 . three])) |
'(1 2 3) |
(dict-range d) → list? |
d : dict? |
Example: |
> (dict-range '([1 . one] [2 . two] [3 . three])) |
'(one two three) |
4.2.4 Dictionary Combinations
| ||||||||||||||||
→ (and/c dict? dict-can-functional-set?) | ||||||||||||||||
d0 : (and/c dict? dict-can-functional-set?) | ||||||||||||||||
d : dict? | ||||||||||||||||
| ||||||||||||||||
|
Examples: | |||
> (dict-union '([1 . one]) '([2 . two]) '([3 . three])) | |||
'((1 . one) (2 . two) (3 . three)) | |||
| |||
'((1 one uno ein une) (2 two dos zwei deux)) |
| ||||||||||||||||||||||||||||
d0 : (and/c dict? dict-mutable?) | ||||||||||||||||||||||||||||
d : dict? | ||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
|
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
| ||||||||||||||||||||||||||||||||||||||||||
unwrap : (-> (and/c dict? pred) dict?) | ||||||||||||||||||||||||||||||||||||||||||
wrap : (-> dict? (and/c dict? pred)) = (lambda (x) x) | ||||||||||||||||||||||||||||||||||||||||||
pred : (-> any/c boolean?) = (lambda (x) #t) | ||||||||||||||||||||||||||||||||||||||||||
mutable? : boolean? = weak? | ||||||||||||||||||||||||||||||||||||||||||
mutable? : boolean? = #f | ||||||||||||||||||||||||||||||||||||||||||
functional? : boolean? = #t |
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:2/contract).
4.3 Hash Tables
(require (planet cce/scheme:7:2/hash)) |
This module provides tools for manipulating hash tables.
4.3.1 Hash Table Construction
(hash immutable-hash-type [key-expr 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] ...) | ||||||||||||||||||||||||||||||||||||||||||||||||||||
|
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
(hash-ref/check h k) → any/c |
h : hash? |
k : (lambda (k) (hash-has-key? h k)) |
Example: |
> (hash-ref/check (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 2) |
'two |
(hash-ref/identity h k) → any/c |
h : hash? |
k : any/c |
Examples: |
> (hash-ref/identity (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 2) |
'two |
> (hash-ref/identity (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 4) |
4 |
(hash-ref/default h k v) → any/c |
h : hash? |
k : any/c |
v : any/c |
Examples: |
> (hash-ref/default (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 2 'other) |
'two |
> (hash-ref/default (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 4 'other) |
'other |
Examples: |
> (hash-ref/failure (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 2 gensym) |
'two |
> (hash-ref/failure (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 4 gensym) |
'g2052 |
4.3.3 Hash Table Accessors
(hash-equal? h) → boolean? |
h : hash? |
Examples: |
> (hash-equal? #hash()) |
#t |
> (hash-equal? #hasheq()) |
#f |
> (hash-equal? #hasheqv()) |
#f |
(hash-has-key? h k) → boolean? |
h : hash? |
k : any/c |
Examples: |
> (hash-has-key? (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 2) |
#t |
> (hash-has-key? (make-immutable-hash '([1 . one] [2 . two] [3 . three])) 4) |
#f |
(hash-domain h) → list? |
h : hash? |
Example: |
> (hash-domain (make-immutable-hash '([1 . one] [2 . two] [3 . three]))) |
'(1 2 3) |
(hash-range h) → list? |
h : hash? |
Example: |
> (hash-range (make-immutable-hash '([1 . one] [2 . two] [3 . three]))) |
'(one two three) |
4.3.4 Hash Table Combinations
| ||||||||||||||||
→ (and/c hash? hash-can-functional-set?) | ||||||||||||||||
h0 : (and/c hash? hash-can-functional-set?) | ||||||||||||||||
h : hash? | ||||||||||||||||
| ||||||||||||||||
|
Examples: | |||
> (hash-union (make-immutable-hash '([1 . one])) (make-immutable-hash '([2 . two])) (make-immutable-hash '([3 . three]))) | |||
'#hash((1 . one) (2 . two) (3 . three)) | |||
| |||
'#hash((1 . (one uno ein une)) (2 . (two dos zwei deux))) |
| ||||||||||||||||||||||||||||
h0 : (and/c hash? hash-mutable?) | ||||||||||||||||||||||||||||
h : hash? | ||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
|
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
(require (planet cce/scheme:7:2/queue)) |
This module provides a mutable queue representation.
(make-queue) → queue/c |
(dequeue! q) → any/c |
q : nonempty-queue/c |
Examples: | ||
| ||
> (enqueue! q 1) | ||
> (dequeue! q) | ||
1 | ||
> (enqueue! q 2) | ||
> (enqueue! q 3) | ||
> (dequeue! q) | ||
2 | ||
> (dequeue! q) | ||
3 |
(queue-empty? q) → boolean? |
q : queue/c |
Examples: | ||
| ||
> (queue-empty? q) | ||
#t | ||
> (enqueue! q 1) | ||
> (queue-empty? q) | ||
#f | ||
> (dequeue! q) | ||
1 | ||
> (queue-empty? q) | ||
#t |
Examples: |
> (queue? (make-queue)) |
#t |
> (queue? 'not-a-queue) |
#f |