6.6.14 VLists

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:

• Random access has typically constant-time complexity.
• Computing the length of a VList has time complexity logarithmic in the number of elements.
• VLists use less storage space than standard lists.
• VList elements are stored in contiguous regions, which improves memory locality and leads to more efficient use of hardware caches.

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:

• It is not thread-safe. Although operations on vlists are all referentially transparent (i.e., purely functional), adding elements to a vlist with 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.

Scheme Procedure: vlist? obj

Return true if obj is a VList.

Scheme Variable: vlist-null

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.

Scheme Procedure: vlist-null? vlist

Return true if vlist is empty.

Scheme Procedure: vlist-cons item vlist

Return a new vlist with item as its head and vlist as its tail.

Scheme Procedure: vlist-head vlist

Return the head of vlist.

Scheme Procedure: vlist-tail vlist

Return the tail of vlist.

Scheme Variable: block-growth-factor

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.

Scheme Procedure: vlist-fold proc init vlist

Scheme Procedure: vlist-fold-right proc init vlist

Fold over vlist, calling proc for each element, as for SRFI-1 fold and fold-right (see fold).

Scheme Procedure: vlist-ref vlist index

Return the element at index index in vlist. This is typically a constant-time operation.

Scheme Procedure: vlist-length vlist

Return the length of vlist. This is typically logarithmic in the number of elements in vlist.

Scheme Procedure: vlist-reverse vlist

Return a new vlist whose content are those of vlist in reverse order.

Scheme Procedure: vlist-map proc vlist

Map proc over the elements of vlist and return a new vlist.

Scheme Procedure: vlist-for-each proc vlist

Call proc on each element of vlist. The result is unspecified.

Scheme Procedure: vlist-drop vlist count

Return a new vlist that does not contain the count first elements of vlist. This is typically a constant-time operation.

Scheme Procedure: vlist-take vlist count

Return a new vlist that contains only the count first elements of vlist.

Scheme Procedure: vlist-filter pred vlist

Return a new vlist containing all the elements from vlist that satisfy pred.

Scheme Procedure: vlist-delete x vlist [equal?]

Return a new vlist corresponding to vlist without the elements equal? to x.

Scheme Procedure: vlist-unfold p f g seed [tail-gen]

Scheme Procedure: vlist-unfold-right p f g seed [tail]

Return a new vlist, as for SRFI-1 unfold and unfold-right (see unfold).

Scheme Procedure: vlist-append vlist …

Append the given vlists and return the resulting vlist.

Scheme Procedure: list->vlist lst

Return a new vlist whose contents correspond to lst.

Scheme Procedure: vlist->list vlist

Return a new list whose contents match those of vlist.