source: project/wiki/eggref/4/vlist @ 25900

[[tags:egg]]

== vlist

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

[[toc:]]

== 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


<procedure>vlist? x -> boolean</procedure>

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

<procedure>vlist-cons item vlist -> vlist</procedure>

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

<procedure>vlist-head vlist -> value</procedure>

Returns the head of {{vlist}}.

<procedure>vlist-tail vlist -> vlist</procedure>

Return the tail of {{vlist}}.

<procedure>vlist-null? vlist -> boolean</procedure>

Returns true if {{vlist}} is empty, false otherwise.

<procedure>list->vlist lst</procedure>

Returns a new vlist whose contents correspond to {{lst}}.

<procedure>vlist-fold proc init vlist</procedure>

Fold over {{vlist}}, calling {{proc}} for each element.

<procedure>vlist-fold-right proc init vlist</procedure>

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

<procedure>vlist-reverse vlist</procedure>

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

<procedure>vlist-map proc vlist</procedure>

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

<procedure>vlist->list vlist -> list</procedure>

Return a new list containing the elements of {{vlist}}.

<procedure>vlist-ref vlist index -> value</procedure>

Returns the element at index {{index}} in {{vlist}}.

<procedure>vlist-drop vlist count -> vlist</procedure>

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

<procedure>vlist-take vlist count -> vlist</procedure>

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

<procedure>vlist-filter pred vlist -> vlist</procedure>

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

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

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

<procedure>vlist-length vlist -> number</procedure>

Returns the length of {{vlist}}.

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

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


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

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


<procedure>vlist-append vlists1 .. vlistn -> vlist</procedure>
Appends the given vlists.

<procedure>vlist-for-each proc vlist -> unspecified</procedure>

Calls {{proc}} on each element of {{vlist}}.

=== Hash list procedures

Hash vlists are analogous to association lists.


<procedure>vhash? obj -> boolean</procedure>

Returns true if {{obj}} is a hash vlist, false otherwise.

<procedure>vhash-cons key value vhash [hash] -> vhash</procedure>
<procedure>vhash-consq key value vhash [hash] -> vhash</procedure>
<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.

<procedure>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}}.

<procedure>vhash-foldq* proc init key vhash -> value</procedure>

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

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

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

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

<procedure>vhash-assq key vhash -> (key . value)</procedure>

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

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

Returns the first key/value pair from {{vhash}} whose key is {{eqv?}}
to {{key}}.

<procedure>vhash-delete key vhash [equal?] [hash] -> vhash</procedure>
<procedure>vhash-delq key vhash [equal?] [hash] -> vhash</procedure>
<procedure>vhash-delv key vhash [equal?] [hash] -> vhash</procedure>

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


<procedure>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}}.


<procedure>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}}.


<procedure>alist->vhash alist [hash] -> vhash</procedure>

Returns the vhash corresponding to {{alist}}, an association list.



== Examples


== About this egg


=== Author

[[/users/ivan-raikov|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/>.