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

Last change on this file since 25899 was 25899, checked in by Ivan Raikov, 9 years ago

initial documentation of vlist

File size: 4.4 KB
Line 
1[[tags:egg]]
2
3== vlist
4
5Implementation of vlists, a functional list-like  data structure.
6
7[[toc:]]
8
9== Usage
10
11(require-extension vlist)
12
13== Documentation
14
15The {{vlist}} library provides an implementations of vlists, a
16functional list-like data structure described by Phil Bagwell in "Fast
17Functional Lists, Hash-Lists, Dequeues and Variable-Length Arrays",
18EPFL Technical Report, 2002.
19
20The idea is to store vlist elements in increasingly large contiguous
21blocks (implemented as vectors here).  These blocks are linked to one
22another using a pointer to the next block (called `block-base' here)
23and an offset within that block (`block-offset' here).  The size of
24these blocks form a geometric series with ratio `block-growth-factor'.
25
26In the best case (e.g., using a vlist returned by `list->vlist'),
27elements from the first half of an N-element vlist are accessed in
28O(1) (assuming `block-growth-factor' is 2), and `vlist-length' takes
29only O(ln(N)).  Furthermore, the data structure improves data locality
30since vlist elements are adjacent, which plays well with caches.
31
32=== Procedures
33
34
35<procedure>vlist? x -> boolean</procedure>
36
37Returns {{#t}} if {{x}} is a vlist, {{#f}} otherwise.
38
39<procedure>vlist-cons item vlist -> vlist</procedure>
40
41Creates a new vlist with {{item}} as its head and {{vlist}} as its tail.
42
43<procedure>vlist-head vlist -> value</procedure>
44
45Returns the head of {{vlist}}.
46
47<procedure>vlist-tail vlist -> vlist</procedure>
48
49Return the tail of {{vlist}}.
50
51<procedure>vlist-null? vlist -> boolean</procedure>
52
53Returns true if {{vlist}} is empty, false otherwise.
54
55<procedure>list->vlist lst</procedure>
56
57Returns a new vlist whose contents correspond to {{lst}}.
58
59<procedure>vlist-fold proc init vlist</procedure>
60
61Fold over {{vlist}}, calling {{proc}} for each element.
62
63<procedure>vlist-fold-right proc init vlist</procedure>
64
65Fold over {{vlist}}, calling {{proc}} for each element, starting from
66the last element.
67
68<procedure>vlist-reverse vlist</procedure>
69
70Returns a new {{vlist}} whose content are those of {{vlist}} in
71reverse order.
72
73<procedure>vlist-map proc vlist</procedure>
74
75Maps {{proc}} over the elements of {{vlist}} and return a new vlist.
76
77<procedure>vlist->list vlist -> list</procedure>
78
79Return a new list containing the elements of {{vlist}}.
80
81<procedure>vlist-ref vlist index -> value</procedure>
82
83Returns the element at index {{index}} in {{vlist}}.
84
85<procedure>vlist-drop vlist count -> vlist</procedure>
86
87Returns a new vlist that does not contain the {{count}} first elements of {{vlist}}.
88
89<procedure>vlist-take vlist count -> vlist</procedure>
90
91Returns a new vlist that contains only the {{count}} first elements of {{vlist}}.
92
93<procedure>vlist-filter pred vlist -> vlist</procedure>
94
95Returns a new vlist containing all the elements from {{vlist}} that satisfy {{pred}}.
96
97<procedure>vlist-delete x vlist [equal?] -> vlist</procedure>
98
99Returns a new vlist corresponding to {{vlist}} without the elements {{equal?}} to {{x}}.
100
101<procedure>vlist-length vlist -> number</procedure>
102
103Returns the length of {{vlist}}.
104
105<procedure>vlist-unfold p f g seed [tail-gen] -> vlist</procedure>
106
107vlist constructor.  Analogous to SRFI-1 `unfold'.
108
109
110<procedure>vlist-unfold-right p f g seed [tail] -> vlist</procedure>
111
112vlist constructor.  Analogous to SRFI-1 `unfold-right'.
113
114
115<procedure>vlist-append vlists1 .. vlistn -> vlist</procedure>
116Appends the given vlists.
117
118<procedure>vlist-for-each proc vlist -> unspecified</procedure>
119
120Calls {{proc}} on each element of {{vlist}}.
121
122
123== Examples
124
125
126== About this egg
127
128
129=== Author
130
131[[/users/ivan-raikov|Ivan Raikov]]
132
133=== Version history
134
135; 1.0 : Initial release
136
137=== License
138
139 The vlist library was written by Ludovic CourtÚs and adapted for
140 Chicken Scheme by Ivan Raikov.
141 
142  Copyright (C) 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
143  Chicken Scheme modifications Copyright 2012 Ivan Raikov.
144 
145 This library is free software; you can redistribute it and/or
146 modify it under the terms of the GNU Lesser General Public
147 License as published by the Free Software Foundation; either
148 version 3 of the License, or (at your option) any later version.
149
150 This library is distributed in the hope that it will be useful,
151 but WITHOUT ANY WARRANTY; without even the implied warranty of
152 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
153 Lesser General Public License for more details.
154 
155 A full copy of the Lesser GPL license can be found at
156 <http://www.gnu.org/licenses/>.
Note: See TracBrowser for help on using the repository browser.