You are looking at historical revision 25899 of this page. It may differ significantly from its current revision.
Implementation of vlists, a functional list-like data structure.
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.
About this egg
- Initial release
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/>.