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?procedure
Returns #t if x is a vlist, #f otherwise.
- vlist-consprocedure
Creates a new vlist with item as its head and vlist as its tail.
- vlist-headprocedure
Returns the head of vlist.
- vlist-tailprocedure
Return the tail of vlist.
- vlist-null?procedure
Returns true if vlist is empty, false otherwise.
- list->vlistprocedure
Returns a new vlist whose contents correspond to lst.
- vlist-foldprocedure
Fold over vlist, calling proc for each element.
- vlist-fold-rightprocedure
Fold over vlist, calling proc for each element, starting from the last element.
- vlist-reverseprocedure
Returns a new vlist whose content are those of vlist in reverse order.
- vlist-mapprocedure
Maps proc over the elements of vlist and return a new vlist.
- vlist->listprocedure
Return a new list containing the elements of vlist.
- vlist-refprocedure
Returns the element at index index in vlist.
- vlist-dropprocedure
Returns a new vlist that does not contain the count first elements of vlist.
- vlist-takeprocedure
Returns a new vlist that contains only the count first elements of vlist.
- vlist-filterprocedure
Returns a new vlist containing all the elements from vlist that satisfy pred.
- vlist-deleteprocedure
Returns a new vlist corresponding to vlist without the elements equal? to x.
- vlist-lengthprocedure
Returns the length of vlist.
- vlist-unfoldprocedure
vlist constructor. Analogous to SRFI-1 `unfold'.
- vlist-unfold-rightprocedure
vlist constructor. Analogous to SRFI-1 `unfold-right'.
- vlist-appendprocedure
Appends the given vlists.
- vlist-for-eachprocedure
Calls proc on each element of vlist.
Hash list procedures
Hash vlists are analogous to association lists.
- vhash?procedure
Returns true if obj is a hash vlist, false otherwise.
- vhash-consprocedure
- vhash-consqprocedure
- vhash-consvprocedure
Return a new hash list based on vhash where key is associated with value. Use hash to compute key's hash.
- vhash-fold*procedure
Folds 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*procedure
Same as vhash-fold*, but using eq?-hash and eq?.
- vhash-foldv*procedure
Same as vhash-fold*, but using eqv?-hash and eqv?.
- vhash-assocprocedure
Returns the first key/value pair from vhash whose key is equal to key according to the equal? equality predicate.
- vhash-assqprocedure
Returns the first key/value pair from vhash whose key is eq? to key.
- vhash-assvprocedure
Returns the first key/value pair from vhash whose key is eqv? to key.
- vhash-deleteprocedure
- vhash-delqprocedure
- vhash-delvprocedure
Removes all associations from vhash with key, comparing keys with equal?.
- vhash-foldprocedure
Folds 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-rightprocedure
Folds 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->vhashprocedure
Returns 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/>.