chickadee » vlist

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.

List procedures

vlist? x -> boolean procedure

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

vlist-cons item vlist -> vlist procedure

Creates a new vlist with item as its head and vlist as its tail.

vlist-head vlist -> value procedure

Returns the head of vlist.

vlist-tail vlist -> vlist procedure

Return the tail of vlist.

vlist-null? vlist -> boolean procedure

Returns true if vlist is empty, false otherwise.

list->vlist lst procedure

Returns a new vlist whose contents correspond to lst.

vlist-fold proc init vlist procedure

Fold over vlist, calling proc for each element.

vlist-fold-right proc init vlist procedure

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

vlist-reverse vlist procedure

Returns a new vlist whose content are those of vlist in reverse order.

vlist-map proc vlist procedure

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

vlist->list vlist -> list procedure

Return a new list containing the elements of vlist.

vlist-ref vlist index -> value procedure

Returns the element at index index in vlist.

vlist-drop vlist count -> vlist procedure

Returns a new vlist that does not contain the count first elements of vlist.

vlist-take vlist count -> vlist procedure

Returns a new vlist that contains only the count first elements of vlist.

vlist-filter pred vlist -> vlist procedure

Returns a new vlist containing all the elements from vlist that satisfy pred.

vlist-delete x vlist [equal?] -> vlist procedure

Returns a new vlist corresponding to vlist without the elements equal? to x.

vlist-length vlist -> number procedure

Returns the length of vlist.

vlist-unfold p f g seed [tail-gen] -> vlist procedure

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

vlist-unfold-right p f g seed [tail] -> vlist procedure

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

vlist-append vlists1 .. vlistn -> vlist procedure

Appends the given vlists.

vlist-for-each proc vlist -> unspecified procedure

Calls proc on each element of vlist.

Hash list procedures

Hash vlists are analogous to association lists.

vhash? obj -> boolean procedure

Returns 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 procedure

Return 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 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* proc init key vhash -> value procedure

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

vhash-foldv* proc init key vhash -> value procedure

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

vhash-assoc key vhash [equal?] [hash] -> (key . value) procedure

Returns 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) procedure

Returns the first key/value pair from vhash whose key is eq? to key.

vhash-assv key vhash -> (key . value) procedure

Returns 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 procedure

Removes all associations from vhash with key, comparing keys with equal?.

vhash-fold proc init vhash procedure

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-right proc init vhash procedure

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->vhash alist [hash] -> vhash procedure

Returns the vhash corresponding to alist, an association list.

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

Contents »