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

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

vlist doc fixes

File size: 7.0 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=== List 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=== Hash list procedures
123
124Hash vlists are analogous to association lists.
125
126
127<procedure>vhash? obj -> boolean</procedure>
128
129Returns true if {{obj}} is a hash vlist, false otherwise.
130
131<procedure>vhash-cons key value vhash [hash] -> vhash</procedure>
132<procedure>vhash-consq key value vhash [hash] -> vhash</procedure>
133<procedure>vhash-consv key value vhash [hash] -> vhash</procedure>
134
135Return a new hash list based on {{vhash}} where {{key}} is associated with
136{{value}}.  Use {{hash}} to compute {{key}}'s hash.
137
138<procedure>vhash-fold* proc init key vhash -> value</procedure>
139
140Folds over all the values associated with {{key}} in {{vhash}}, with
141each call to {{proc}} having the form {{(proc value result)}}, where
142{{result}} is the result of the previous call to {{proc}} and {{init}}
143the value of {{result}} for the first call to {{proc}}.
144
145<procedure>vhash-foldq* proc init key vhash -> value</procedure>
146
147Same as {{vhash-fold*}}, but using {{eq?-hash}} and {{eq?}}.
148
149<procedure>vhash-foldv* proc init key vhash -> value</procedure>
150
151Same as {{vhash-fold*}}, but using {{eqv?-hash}} and {{eqv?}}.
152
153<procedure>vhash-assoc key vhash [equal?] [hash] -> (key . value)</procedure>
154
155Returns the first key/value pair from {{vhash}} whose key is equal to
156{{key}} according to the {{equal?}} equality predicate.
157
158<procedure>vhash-assq key vhash -> (key . value)</procedure>
159
160Returns the first key/value pair from {{vhash}} whose key is {{eq?}}
161to {{key}}.
162
163<procedure>vhash-assv key vhash -> (key . value)</procedure>
164
165Returns the first key/value pair from {{vhash}} whose key is {{eqv?}}
166to {{key}}.
167
168<procedure>vhash-delete key vhash [equal?] [hash] -> vhash</procedure>
169<procedure>vhash-delq key vhash [equal?] [hash] -> vhash</procedure>
170<procedure>vhash-delv key vhash [equal?] [hash] -> vhash</procedure>
171
172Removes all associations from {{vhash}} with {{key}}, comparing keys
173with {{equal?}}.
174
175
176<procedure>vhash-fold proc init vhash</procedure>
177
178Folds over the key/pair elements of {{vhash}} from left to right, with
179each call to {{proc}} having the form {{(proc key value result)}},
180where {{result}} is the result of the previous call to {{proc}} and
181{{init}} the value of {{result}} for the first call to {{proc}}.
182
183
184<procedure>vhash-fold-right proc init vhash</procedure>
185
186Folds over the key/pair elements of {{vhash}} from right to left, with
187each call to {{proc}} having the form {{(proc key value result)}},
188where {{result}} is the result of the previous call to {{proc}} and
189{{init}} the value of {{result}} for the first call to {{proc}}.
190
191
192<procedure>alist->vhash alist [hash] -> vhash</procedure>
193
194Returns the vhash corresponding to {{alist}}, an association list.
195
196
197
198== Examples
199
200
201== About this egg
202
203
204=== Author
205
206[[/users/ivan-raikov|Ivan Raikov]]
207
208=== Version history
209
210; 1.0 : Initial release
211
212=== License
213
214 The vlist library was written by Ludovic CourtÚs and adapted for
215 Chicken Scheme by Ivan Raikov.
216 
217  Copyright (C) 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
218  Chicken Scheme modifications Copyright 2012 Ivan Raikov.
219 
220 This library is free software; you can redistribute it and/or
221 modify it under the terms of the GNU Lesser General Public
222 License as published by the Free Software Foundation; either
223 version 3 of the License, or (at your option) any later version.
224
225 This library is distributed in the hope that it will be useful,
226 but WITHOUT ANY WARRANTY; without even the implied warranty of
227 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
228 Lesser General Public License for more details.
229 
230 A full copy of the Lesser GPL license can be found at
231 <http://www.gnu.org/licenses/>.
Note: See TracBrowser for help on using the repository browser.