## vlist

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

## TOC »

## 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?`procedureReturns

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

`vlist-cons`procedureCreates a new vlist with

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

`vlist-head`procedureReturns the head of

`vlist`.

`vlist-tail`procedureReturn the tail of

`vlist`.

`vlist-null?`procedureReturns true if

`vlist`is empty, false otherwise.

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

`lst`.

`vlist-fold`procedureFold over

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

`vlist-fold-right`procedureFold over

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

`vlist-reverse`procedureReturns a new

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

`vlist-map`procedureMaps

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

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

`vlist`.

`vlist-ref`procedureReturns the element at index

`index`in`vlist`.

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

`count`first elements of`vlist`.

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

`count`first elements of`vlist`.

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

`vlist`that satisfy`pred`.

`vlist-delete`procedureReturns a new vlist corresponding to

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

`vlist-length`procedureReturns the length of

`vlist`.

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

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

`vlist-append`procedureAppends the given vlists.

`vlist-for-each`procedureCalls

`proc`on each element of`vlist`.

### Hash list procedures

Hash vlists are analogous to association lists.

`vhash?`procedureReturns true if

`obj`is a hash vlist, false otherwise.

`vhash-cons`procedure`vhash-consq`procedure`vhash-consv`procedureReturn a new hash list based on

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

`vhash-fold*`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*`procedureSame as

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

`vhash-foldv*`procedureSame as

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

`vhash-assoc`procedureReturns the first key/value pair from

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

`vhash-assq`procedureReturns the first key/value pair from

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

`vhash-assv`procedureReturns the first key/value pair from

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

`vhash-delete`procedure`vhash-delq`procedure`vhash-delv`procedureRemoves all associations from

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

`vhash-fold`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`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`procedureReturns the vhash corresponding to

`alist`, an association list.

## Examples

## About this egg

### Author

### Repository

This egg is hosted on the CHICKEN Subversion repository:

https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/vlist

If you want to check out the source code repository of this egg and you are not familiar with Subversion, see this page.

### Version history

- 1.1
- Ported to CHICKEN 5 (thanks to Yuriy Shirokov)
- 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/>.