(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
vlist-consmutates part of its internal structure, which makes it non-thread-safe. This could be fixed, but it would slow down
vlist-consalways 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-consis 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
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
Return true if obj is a VList.
The empty VList. Note that it’s possible to create an empty VList not
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
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
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.