## vlist

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

## TOC »

## 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.

### List procedures

`vlist? x -> boolean`procedureReturns

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

`vlist-cons item vlist -> vlist`procedureCreates a new vlist with

`item`as its head and`vlist`as its tail.

`vlist-head vlist -> value`procedureReturns the head of

`vlist`.

`vlist-tail vlist -> vlist`procedureReturn the tail of

`vlist`.

`vlist-null? vlist -> boolean`procedureReturns true if

`vlist`is empty, false otherwise.

`list->vlist lst`procedureReturns a new vlist whose contents correspond to

`lst`.

`vlist-fold proc init vlist`procedureFold over

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

`vlist-fold-right proc init vlist`procedureFold over

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

`vlist-reverse vlist`procedureReturns a new

`vlist`whose content are those of`vlist`in reverse order.

`vlist-map proc vlist`procedureMaps

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

`vlist->list vlist -> list`procedureReturn a new list containing the elements of

`vlist`.

`vlist-ref vlist index -> value`procedureReturns the element at index

`index`in`vlist`.

`vlist-drop vlist count -> vlist`procedureReturns a new vlist that does not contain the

`count`first elements of`vlist`.

`vlist-take vlist count -> vlist`procedureReturns a new vlist that contains only the

`count`first elements of`vlist`.

`vlist-filter pred vlist -> vlist`procedureReturns a new vlist containing all the elements from

`vlist`that satisfy`pred`.

`vlist-delete x vlist [equal?] -> vlist`procedureReturns a new vlist corresponding to

`vlist`without the elements`equal?`to`x`.

`vlist-length vlist -> number`procedureReturns the length of

`vlist`.

`vlist-unfold p f g seed [tail-gen] -> vlist`procedurevlist constructor. Analogous to SRFI-1 `unfold'.

`vlist-unfold-right p f g seed [tail] -> vlist`procedurevlist constructor. Analogous to SRFI-1 `unfold-right'.

`vlist-append vlists1 .. vlistn -> vlist`procedureAppends the given vlists.

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

`proc`on each element of`vlist`.

### Hash list procedures

Hash vlists are analogous to association lists.

`vhash? obj -> boolean`procedureReturns true if

`obj`is a hash vlist, false otherwise.

`vhash-cons key value vhash [hash] -> vhash`procedure`vhash-consq key value vhash [hash] -> vhash`procedure`vhash-consv key value vhash [hash] -> vhash`procedureReturn a new hash list based on

`vhash`where`key`is associated with`value`. Use`hash`to compute`key`'s hash.

`vhash-fold* proc init key vhash -> value`procedureFolds over all the values associated with

`key`in`vhash`, with each call to`proc`having the form`(proc value result)`, where`result`is the result of the previous call to`proc`and`init`the value of`result`for the first call to`proc`.

`vhash-foldq* proc init key vhash -> value`procedureSame as

`vhash-fold*`, but using`eq?-hash`and`eq?`.

`vhash-foldv* proc init key vhash -> value`procedureSame as

`vhash-fold*`, but using`eqv?-hash`and`eqv?`.

`vhash-assoc key vhash [equal?] [hash] -> (key . value)`procedureReturns the first key/value pair from

`vhash`whose key is equal to`key`according to the`equal?`equality predicate.

`vhash-assq key vhash -> (key . value)`procedureReturns the first key/value pair from

`vhash`whose key is`eq?`to`key`.

`vhash-assv key vhash -> (key . value)`procedureReturns the first key/value pair from

`vhash`whose key is`eqv?`to`key`.

`vhash-delete key vhash [equal?] [hash] -> vhash`procedure`vhash-delq key vhash [equal?] [hash] -> vhash`procedure`vhash-delv key vhash [equal?] [hash] -> vhash`procedureRemoves all associations from

`vhash`with`key`, comparing keys with`equal?`.

`vhash-fold proc init vhash`procedureFolds over the key/pair elements of

`vhash`from left to right, with each call to`proc`having the form`(proc key value result)`, where`result`is the result of the previous call to`proc`and`init`the value of`result`for the first call to`proc`.

`vhash-fold-right proc init vhash`procedureFolds over the key/pair elements of

`vhash`from right to left, with each call to`proc`having the form`(proc key value result)`, where`result`is the result of the previous call to`proc`and`init`the value of`result`for the first call to`proc`.

`alist->vhash alist [hash] -> vhash`procedureReturns the vhash corresponding to

`alist`, an association list.

## 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/>.