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

Ivan Raikov

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