On this page:
4.1 Dictionaries
4.1.1 Dictionary Lookup
dict-ref!
dict-ref/ check
dict-ref/ identity
dict-ref/ default
dict-ref/ failure
4.1.2 Dictionary Accessors
dict-has-key?
dict-domain
dict-range
4.1.3 Dictionary Combinations
dict-union
dict-union!
4.1.4 Dictionary Contract
dict/ c
4.2 Hash Tables
4.2.1 Hash Table Lookup
hash-ref/ check
hash-ref/ identity
hash-ref/ default
hash-ref/ failure
4.2.2 Hash Table Accessors
hash-contains?
hash-has-key?
hash-domain
hash-range
4.2.3 Hash Table Combinations
hash-union
hash-union!
4.3 Imperative Queues
make-queue
enqueue!
dequeue!
queue-empty?
queue?
queue/ c
nonempty-queue/ c
Version: 4.2.1.8

4 Collection Datatypes

4.1 Dictionaries

 (require (planet cce/scheme:5:0/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)

  g1567

  > d

  #hash((1. one)              (2. two)                      (3. tres)                              (4. g1567))

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

  g1709

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:5:0/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)

  g1356

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:5:0/queue))

This module provides a mutable queue representation.

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

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