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 VList-Based Hash Lists or “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.
Return true if obj is a VList.
The empty VList. Note that it’s possible to create an empty VList not
eq?
to vlist-null
; thus, callers should always use
vlist-null?
when testing whether a VList is empty.
Return true if vlist is empty.
Return a new vlist with item as its head and vlist as its tail.
Return the head of vlist.
Return the tail of vlist.
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
fold
and fold-right
(see fold
).
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 unfold
and unfold-right
(see unfold
).
Append the given vlists and return the resulting vlist.
Return a new vlist whose contents correspond to lst.
Return a new list whose contents match those of vlist.