4 Collection Datatypes

Version: 4.2.4.2

← prev up next →

4 Collection Datatypes

4.1 Dictionaries

(require (planet cce/scheme:6:1/dict))

This module provides tools for manipulating dictionary values.

4.1.1 Dictionary Lookup

(dict-ref! d k v) → any/c

d : (and/c dict? dict-mutable?)

k : any/c

v : (or/c (-> any/c) any/c)

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:
  (define d (make-hash))

  > (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)
  g1266
  > d
  #hash((1. one)              (2. two)                      (3. tres)                              (4. g1266))

(dict-ref/check d k) → any/c

d : dict?

k : (lambda (k) (dict-has-key? d k))

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.

Example:
> (dict-ref/check '([1 . one] [2 . two] [3 . three]) 2)
two

(dict-ref/identity d k) → any/c

d : dict?

k : any/c

Looks up key k in dictionary d. Returns k if d has no entry for k. Equivalent to (dict-ref d k (lambda () k)).

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

Looks up key k in dictionary d. Returns v if d has no entry for k. Equivalent to (dict-ref d k (lambda () v)).

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

(dict-ref/failure d k f) → any/c

d : dict?

k : any/c

f : (-> any/c)

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

Examples:
  > (dict-ref/failure '([1 . one] [2 . two] [3 . three]) 2 gensym)
  two
  > (dict-ref/failure '([1 . one] [2 . two] [3 . three]) 4 gensym)
  g1376

4.1.2 Dictionary Accessors

(dict-has-key? d k) → boolean?

d : dict?

k : any/c

Reports whether d has an entry for k.

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?

Produces the domain of a dictionary as a list of keys.

Example:
> (dict-domain '([1 . one] [2 . two] [3 . three]))
(1 2 3)

(dict-range d) → list?

d : dict?

Produces the range of a dictionary as a list of values.

Example:
> (dict-range '([1 . one] [2 . two] [3 . three]))
(one two three)

4.1.3 Dictionary Combinations

(dict-union d0 d ... [#:combine combine])

→ (and/c dict? dict-can-functional-set?)

d0 : (and/c dict? dict-can-functional-set?)

d : dict?

	combine		:		(-> any/c any/c any/c any/c)
			=		(lambda _ (error 'dict-union ...))

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 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 (lambda (k v1 v2) (append v1 v2)))
  ((1 one uno ein une) (2 two dos zwei deux))

(dict-union! d0 d ... [#:combine combine]) → void?

d0 : (and/c dict? dict-mutable?)

d : dict?

	combine		:		(-> any/c any/c any/c any/c)
			=		(lambda _ (error 'dict-union! ...))

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 k v0 v).

Examples:
  (define d (make-hash))

  > d
  #hash()
  > (dict-union! d '([1    one uno]  [2    two dos]))
  > d
  #hash((1oneuno)              (2twodos))
  > (dict-union! d
                 '([1    ein une]  [2    zwei deux])
                 #:combine (lambda (k v1 v2) (append v1 v2)))
  > d
  #hash((1oneunoeinune)              (2twodoszweideux))

4.1.4 Dictionary Contract

(dict/c key/c value/c) → contract?

key/c : contract?

value/c : contract?

Consumes one contract for keys and another for values, and produces a higher-order contract that wraps dictionaries much the same way that arrow contracts wrap functions. Specifically, dictionary operations on the wrapped dictionary require all keys to satisfy key/c and values to satisfy value/c.

The wrapped dictionary will support the same set of dictionary operations as the base dictionary, and respond identically to dict-mutable?, dict-can-remove-keys?, and dict-can-functional-set?.

Warning: Bear in mind that these checks are perfomed on every dictionary operation, and dictionaries wrapped in dict/c multiple times will perform the checks as many times for each operation. Especially for immutable dictionaries (which may be passed through a constructor that involves dict/c on each update), contract-wrapped dictionaries may be much less efficient than the original dictionaries.

4.2 Hash Tables

(require (planet cce/scheme:6:1/hash))

This module provides tools for manipulating hash tables.

4.2.1 Hash Table Lookup

(hash-ref/check h k) → any/c

h : hash?

k : (lambda (k) (hash-has-key? h k))

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.

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

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

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

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

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

(hash-ref/failure h k f) → any/c

h : hash?

k : any/c

f : (-> any/c)

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

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

4.2.2 Hash Table Accessors

(hash-contains? h k) → boolean?

h : hash?

k : any/c

Deprecated: This function has been replaced by hash-has-key? from scheme/base (and re-exported from this module); see below.

(hash-has-key? h k) → boolean?

h : hash?

k : any/c

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.

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?

Produces the domain of a hash table as a list of keys.

Example:
> (hash-domain (make-immutable-hash '([1 . one] [2 . two] [3 . three])))
(1 2 3)

(hash-range h) → list?

h : hash?

Produces the range of a hash table as a list of values.

Example:
> (hash-range (make-immutable-hash '([1 . one] [2 . two] [3 . three])))
(one two three)

4.2.3 Hash Table Combinations

(hash-union h0 h ... [#:combine combine])

→ (and/c hash? hash-can-functional-set?)

h0 : (and/c hash? hash-can-functional-set?)

h : hash?

	combine		:		(-> any/c any/c any/c any/c)
			=		(lambda _ (error 'hash-union ...))

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 k v0 v).

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-union (make-immutable-hash '([1    one uno]  [2    two dos]))
                (make-immutable-hash '([1    ein une]  [2    zwei deux]))
                #:combine (lambda (k v1 v2) (append v1 v2)))
  #hash((1oneunoeinune)              (2twodoszweideux))

(hash-union! h0 h ... [#:combine combine]) → void?

h0 : (and/c hash? hash-mutable?)

h : hash?

	combine		:		(-> any/c any/c any/c any/c)
			=		(lambda _ (error 'hash-union! ...))

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 k v0 v).

Examples:
  (define h (make-hash))

  > h
  #hash()
  > (hash-union! h (make-immutable-hash '([1    one uno]  [2    two dos])))
  > h
  #hash((1oneuno)              (2twodos))
  > (hash-union! h
                 (make-immutable-hash '([1    ein une]  [2    zwei deux]))
                 #:combine (lambda (k v1 v2) (append v1 v2)))
  > h
  #hash((1oneunoeinune)              (2twodoszweideux))

4.3 Imperative Queues

(require (planet cce/scheme:6:1/queue))

This module provides a mutable queue representation.

(make-queue) → queue/c

Produces an empty queue.

(enqueue! q v) → void?

q : queue/c

v : any/c

Adds an element to the back of a queue.

(dequeue! q) → any/c

q : nonempty-queue/c

Removes an element from the front of a nonempty queue, and returns that element.

Examples:
  (define q (make-queue))

  > (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

Recognizes whether a queue is empty or not.

Examples:
  (define q (make-queue))

  > (queue-empty? q)
  #t
  > (enqueue! q 1)
  > (queue-empty? q)
  #f
  > (dequeue! q)
  1
  > (queue-empty? q)
  #t

(queue? v) → boolean?

v : any/c

This predicate recognizes queues.

Examples:
  > (queue? (make-queue))
  #t
  > (queue? 'not-a-queue)
  #f

queue/c : flat-contract?

nonempty-queue/c : flat-contract?

These contracts recognize queues; the latter requires the queue to contain at least one value.

← prev up next →

1	Functions
2	Multiple Values
3	Textual Data
4	Collection Datatypes
5	Macros
6	Classes and Objects
7	Contracts
8	Modules
9	Ports
10	Sandboxed Evaluation
11	Scribble Documentation
12	Graphics