You are looking at historical revision 25899 of this page. It may differ significantly from its current revision.

## vlist

Implementation of vlists, a functional list-like data structure.

## Usage

(require-extension vlist)

## Documentation

The `vlist` library provides an implementations of vlists, a functional list-like data structure described by Phil Bagwell in "Fast Functional Lists, Hash-Lists, Dequeues and Variable-Length Arrays", EPFL Technical Report, 2002.

The idea 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 (called `block-base' here) and an offset within that block (`block-offset' here). The size of these blocks form a geometric series with ratio `block-growth-factor'.

In the best case (e.g., using a vlist returned by `list->vlist'), elements from the first half of an N-element vlist are accessed in O(1) (assuming `block-growth-factor' is 2), and `vlist-length' takes only O(ln(N)). Furthermore, the data structure improves data locality since vlist elements are adjacent, which plays well with caches.

### Procedures

*[procedure]*

`vlist? x -> boolean`

Returns `#t` if `x` is a vlist, `#f` otherwise.

*[procedure]*

`vlist-cons item vlist -> vlist`

Creates a new vlist with `item` as its head and `vlist` as its tail.

*[procedure]*

`vlist-head vlist -> value`

Returns the head of `vlist`.

*[procedure]*

`vlist-tail vlist -> vlist`

Return the tail of `vlist`.

*[procedure]*

`vlist-null? vlist -> boolean`

Returns true if `vlist` is empty, false otherwise.

*[procedure]*

`list->vlist lst`

Returns a new vlist whose contents correspond to `lst`.

*[procedure]*

`vlist-fold proc init vlist`

Fold over `vlist`, calling `proc` for each element.

*[procedure]*

`vlist-fold-right proc init vlist`

Fold over `vlist`, calling `proc` for each element, starting from the last element.

*[procedure]*

`vlist-reverse vlist`

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

*[procedure]*

`vlist-map proc vlist`

Maps `proc` over the elements of `vlist` and return a new vlist.

*[procedure]*

`vlist->list vlist -> list`

Return a new list containing the elements of `vlist`.

*[procedure]*

`vlist-ref vlist index -> value`

Returns the element at index `index` in `vlist`.

*[procedure]*

`vlist-drop vlist count -> vlist`

Returns a new vlist that does not contain the `count` first elements of `vlist`.

*[procedure]*

`vlist-take vlist count -> vlist`

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

*[procedure]*

`vlist-filter pred vlist -> vlist`

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

*[procedure]*

`vlist-delete x vlist [equal?] -> vlist`

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

*[procedure]*

`vlist-length vlist -> number`

Returns the length of `vlist`.

*[procedure]*

`vlist-unfold p f g seed [tail-gen] -> vlist`

vlist constructor. Analogous to SRFI-1 `unfold'.

*[procedure]*

`vlist-unfold-right p f g seed [tail] -> vlist`

vlist constructor. Analogous to SRFI-1 `unfold-right'.

*[procedure]*

`vlist-append vlists1 .. vlistn -> vlist`

Appends the given vlists.

*[procedure]*

`vlist-for-each proc vlist -> unspecified`

Calls `proc` on each element of `vlist`.

## Examples

## About this egg

### Author

### Version history

- 1.0
- Initial release

### License

The vlist library was written by Ludovic Courtès and adapted for Chicken Scheme by Ivan Raikov. Copyright (C) 2009, 2010, 2011, 2012 Free Software Foundation, Inc. Chicken Scheme modifications Copyright 2012 Ivan Raikov. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. A full copy of the Lesser GPL license can be found at <http://www.gnu.org/licenses/>.