The (ice-9 vlist) module provides an implementation of the VList
data structure designed by Phil Bagwell in 2002. VLists are immutable lists,
which can contain any Scheme object. They improve on standard Scheme linked
lists in several areas:
The idea behind VLists is to store vlist elements in increasingly large
contiguous blocks (implemented as vectors here). These blocks are linked to one
another using a pointer to the next block and an offset within that block. The
size of these blocks form a geometric series with ratio
block-growth-factor (2 by default).
The VList structure also serves as the basis for the VList-based hash lists or “vhashes”, an immutable dictionary type (see VHashes).
However, the current implementation in (ice-9 vlist) has several
noteworthy shortcomings:
vlist-cons mutates part of its internal structure, which makes
it non-thread-safe. This could be fixed, but it would slow down
vlist-cons.
vlist-cons always allocates at least as much memory as cons.
Again, Phil Bagwell describes how to fix it, but that would require tuning the
garbage collector in a way that may not be generally beneficial.
vlist-cons is a Scheme procedure compiled to bytecode, and it does not
compete with the straightforward C implementation of cons, and with the
fact that the VM has a special cons instruction.
We hope to address these in the future.
The programming interface exported by (ice-9 vlist) is defined below.
Most of it is the same as SRFI-1 with an added vlist- prefix to function
names.
The empty VList. Note that it's possible to create an empty VList not
eq?tovlist-null; thus, callers should always usevlist-null?when testing whether a VList is empty.
Return a new vlist with item as its head and vlist as its tail.
A fluid that defines the growth factor of VList blocks, 2 by default.
The functions below provide the usual set of higher-level list operations.
Fold over vlist, calling proc for each element, as for SRFI-1
foldandfold-right(seefold).
Return the element at index index in vlist. This is typically a constant-time operation.
Return the length of vlist. This is typically logarithmic in the number of elements in vlist.
Return a new vlist whose content are those of vlist in reverse order.
Map proc over the elements of vlist and return a new vlist.
Call proc on each element of vlist. The result is unspecified.
Return a new vlist that does not contain the count first elements of vlist. This is typically a constant-time operation.
Return a new vlist that contains only the count first elements of vlist.
Return a new vlist containing all the elements from vlist that satisfy pred.
Return a new vlist corresponding to vlist without the elements equal? to x.
Return a new vlist, as for SRFI-1
unfoldandunfold-right(seeunfold).