Next: Hash Tables, Previous: Association Lists, Up: Compound Data Types [Contents][Index]

The `(ice-9 vlist)`

module provides an implementation of *VList-based
hash lists* (see VLists). VList-based hash lists, or *vhashes*, are an
immutable dictionary type similar to association lists that maps *keys* to
*values*. However, unlike association lists, accessing a value given its
key is typically a constant-time operation.

The VHash programming interface of `(ice-9 vlist)`

is mostly the same as
that of association lists found in SRFI-1, with procedure names prefixed by
`vhash-`

instead of `alist-`

(see SRFI-1 Association Lists).

In addition, vhashes can be manipulated using VList operations:

(vlist-head (vhash-consq 'a 1 vlist-null)) ⇒ (a . 1) (define vh1 (vhash-consq 'b 2 (vhash-consq 'a 1 vlist-null))) (define vh2 (vhash-consq 'c 3 (vlist-tail vh1))) (vhash-assq 'a vh2) ⇒ (a . 1) (vhash-assq 'b vh2) ⇒ #f (vhash-assq 'c vh2) ⇒ (c . 3) (vlist->list vh2) ⇒ ((c . 3) (a . 1))

However, keep in mind that procedures that construct new VLists
(`vlist-map`

, `vlist-filter`

, etc.) return raw VLists, not vhashes:

(define vh (alist->vhash '((a . 1) (b . 2) (c . 3)) hashq)) (vhash-assq 'a vh) ⇒ (a . 1) (define vl ;; This will create a raw vlist. (vlist-filter (lambda (key+value) (odd? (cdr key+value))) vh)) (vhash-assq 'a vl) ⇒ ERROR: Wrong type argument in position 2 (vlist->list vl) ⇒ ((a . 1) (c . 3))

- Scheme Procedure:
**vhash?***obj* Return true if

`obj`is a vhash.

- Scheme Procedure:
**vhash-cons***key value vhash [hash-proc]* - Scheme Procedure:
**vhash-consq***key value vhash* - Scheme Procedure:
**vhash-consv***key value vhash* Return a new hash list based on

`vhash`where`key`is associated with`value`, using`hash-proc`to compute the hash of`key`.`vhash`must be either`vlist-null`

or a vhash returned by a previous call to`vhash-cons`

.`hash-proc`defaults to`hash`

(see`hash`

procedure). With`vhash-consq`

, the`hashq`

hash function is used; with`vhash-consv`

the`hashv`

hash function is used.All

`vhash-cons`

calls made to construct a vhash should use the same`hash-proc`. Failing to do that, the result is undefined.

- Scheme Procedure:
**vhash-assoc***key vhash [equal? [hash-proc]]* - Scheme Procedure:
**vhash-assq***key vhash* - Scheme Procedure:
**vhash-assv***key vhash* Return the first key/value pair from

`vhash`whose key is equal to`key`according to the`equal?`equality predicate (which defaults to`equal?`

), and using`hash-proc`(which defaults to`hash`

) to compute the hash of`key`. The second form uses`eq?`

as the equality predicate and`hashq`

as the hash function; the last form uses`eqv?`

and`hashv`

.Note that it is important to consistently use the same hash function for

`hash-proc`as was passed to`vhash-cons`

. Failing to do that, the result is unpredictable.

- Scheme Procedure:
**vhash-delete***key vhash [equal? [hash-proc]]* - Scheme Procedure:
**vhash-delq***key vhash* - Scheme Procedure:
**vhash-delv***key vhash* Remove all associations from

`vhash`with`key`, comparing keys with`equal?`(which defaults to`equal?`

), and computing the hash of`key`using`hash-proc`(which defaults to`hash`

). The second form uses`eq?`

as the equality predicate and`hashq`

as the hash function; the last one uses`eqv?`

and`hashv`

.Again the choice of

`hash-proc`must be consistent with previous calls to`vhash-cons`

.

- Scheme Procedure:
**vhash-fold***proc init vhash* - Scheme Procedure:
**vhash-fold-right***proc init vhash* Fold over the key/value elements of

`vhash`in the given direction, with each call to`proc`having the form`(`

, where`proc`key value result)`result`is the result of the previous call to`proc`and`init`the value of`result`for the first call to`proc`.

- Scheme Procedure:
**vhash-fold****proc init key vhash [equal? [hash]]* - Scheme Procedure:
**vhash-foldq****proc init key vhash* - Scheme Procedure:
**vhash-foldv****proc init key vhash* Fold over all the values associated with

`key`in`vhash`, with each call to`proc`having the form`(proc value result)`

, where`result`is the result of the previous call to`proc`and`init`the value of`result`for the first call to`proc`.Keys in

`vhash`are hashed using`hash`are compared using`equal?`. The second form uses`eq?`

as the equality predicate and`hashq`

as the hash function; the third one uses`eqv?`

and`hashv`

.Example:

(define vh (alist->vhash '((a . 1) (a . 2) (z . 0) (a . 3)))) (vhash-fold* cons '() 'a vh) ⇒ (3 2 1) (vhash-fold* cons '() 'z vh) ⇒ (0)

- Scheme Procedure:
**alist->vhash***alist [hash-proc]* Return the vhash corresponding to

`alist`, an association list, using`hash-proc`to compute key hashes. When omitted,`hash-proc`defaults to`hash`

.

Next: Hash Tables, Previous: Association Lists, Up: Compound Data Types [Contents][Index]