Commit | Line | Data |
---|---|---|
2da09c3f MV |
1 | @c -*-texinfo-*- |
2 | @c This is part of the GNU Guile Reference Manual. | |
3 | @c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004 | |
4 | @c Free Software Foundation, Inc. | |
5 | @c See the file guile.texi for copying conditions. | |
6 | ||
4c731ece NJ |
7 | @page |
8 | @node Compound Data Types | |
9 | @chapter Compound Data Types | |
10 | ||
11 | This chapter describes Guile's compound data types. By @dfn{compound} | |
12 | we mean that the primary purpose of these data types is to act as | |
13 | containers for other kinds of data (including other compound objects). | |
14 | For instance, a (non-uniform) vector with length 5 is a container that | |
15 | can hold five arbitrary Scheme objects. | |
16 | ||
17 | The various kinds of container object differ from each other in how | |
18 | their memory is allocated, how they are indexed, and how particular | |
19 | values can be looked up within them. | |
20 | ||
21 | @menu | |
22 | * Pairs:: Scheme's basic building block. | |
23 | * Lists:: Special list functions supported by Guile. | |
24 | * Vectors:: One-dimensional arrays of Scheme objects. | |
25 | * Records:: | |
26 | * Structures:: | |
27 | * Arrays:: Arrays of values. | |
28 | * Association Lists and Hash Tables:: Dictionary data types. | |
29 | @end menu | |
30 | ||
31 | ||
32 | @node Pairs | |
33 | @section Pairs | |
34 | @tpindex Pairs | |
35 | ||
4c731ece NJ |
36 | Pairs are used to combine two Scheme objects into one compound object. |
37 | Hence the name: A pair stores a pair of objects. | |
38 | ||
39 | The data type @dfn{pair} is extremely important in Scheme, just like in | |
40 | any other Lisp dialect. The reason is that pairs are not only used to | |
41 | make two values available as one object, but that pairs are used for | |
42 | constructing lists of values. Because lists are so important in Scheme, | |
43 | they are described in a section of their own (@pxref{Lists}). | |
44 | ||
45 | Pairs can literally get entered in source code or at the REPL, in the | |
46 | so-called @dfn{dotted list} syntax. This syntax consists of an opening | |
47 | parentheses, the first element of the pair, a dot, the second element | |
48 | and a closing parentheses. The following example shows how a pair | |
49 | consisting of the two numbers 1 and 2, and a pair containing the symbols | |
50 | @code{foo} and @code{bar} can be entered. It is very important to write | |
51 | the whitespace before and after the dot, because otherwise the Scheme | |
85a9b4ed | 52 | parser would not be able to figure out where to split the tokens. |
4c731ece NJ |
53 | |
54 | @lisp | |
55 | (1 . 2) | |
56 | (foo . bar) | |
57 | @end lisp | |
58 | ||
59 | But beware, if you want to try out these examples, you have to | |
60 | @dfn{quote} the expressions. More information about quotation is | |
61 | available in the section (REFFIXME). The correct way to try these | |
62 | examples is as follows. | |
63 | ||
64 | @lisp | |
65 | '(1 . 2) | |
66 | @result{} | |
67 | (1 . 2) | |
68 | '(foo . bar) | |
69 | @result{} | |
70 | (foo . bar) | |
71 | @end lisp | |
72 | ||
73 | A new pair is made by calling the procedure @code{cons} with two | |
74 | arguments. Then the argument values are stored into a newly allocated | |
75 | pair, and the pair is returned. The name @code{cons} stands for | |
76 | "construct". Use the procedure @code{pair?} to test whether a | |
77 | given Scheme object is a pair or not. | |
78 | ||
79 | @rnindex cons | |
80 | @deffn {Scheme Procedure} cons x y | |
81 | @deffnx {C Function} scm_cons (x, y) | |
82 | Return a newly allocated pair whose car is @var{x} and whose | |
83 | cdr is @var{y}. The pair is guaranteed to be different (in the | |
84 | sense of @code{eq?}) from every previously existing object. | |
85 | @end deffn | |
86 | ||
87 | @rnindex pair? | |
88 | @deffn {Scheme Procedure} pair? x | |
89 | @deffnx {C Function} scm_pair_p (x) | |
90 | Return @code{#t} if @var{x} is a pair; otherwise return | |
91 | @code{#f}. | |
92 | @end deffn | |
93 | ||
94 | The two parts of a pair are traditionally called @dfn{car} and | |
95 | @dfn{cdr}. They can be retrieved with procedures of the same name | |
96 | (@code{car} and @code{cdr}), and can be modified with the procedures | |
97 | @code{set-car!} and @code{set-cdr!}. Since a very common operation in | |
98 | Scheme programs is to access the car of a pair, or the car of the cdr of | |
99 | a pair, etc., the procedures called @code{caar}, @code{cadr} and so on | |
100 | are also predefined. | |
101 | ||
102 | @rnindex car | |
103 | @rnindex cdr | |
104 | @deffn {Scheme Procedure} car pair | |
105 | @deffnx {Scheme Procedure} cdr pair | |
106 | Return the car or the cdr of @var{pair}, respectively. | |
107 | @end deffn | |
108 | ||
109 | @deffn {Scheme Procedure} caar pair | |
110 | @deffnx {Scheme Procedure} cadr pair @dots{} | |
111 | @deffnx {Scheme Procedure} cdddar pair | |
112 | @deffnx {Scheme Procedure} cddddr pair | |
113 | These procedures are compositions of @code{car} and @code{cdr}, where | |
114 | for example @code{caddr} could be defined by | |
115 | ||
116 | @lisp | |
117 | (define caddr (lambda (x) (car (cdr (cdr x))))) | |
118 | @end lisp | |
119 | @end deffn | |
120 | ||
121 | @rnindex set-car! | |
122 | @deffn {Scheme Procedure} set-car! pair value | |
123 | @deffnx {C Function} scm_set_car_x (pair, value) | |
124 | Stores @var{value} in the car field of @var{pair}. The value returned | |
125 | by @code{set-car!} is unspecified. | |
126 | @end deffn | |
127 | ||
128 | @rnindex set-cdr! | |
129 | @deffn {Scheme Procedure} set-cdr! pair value | |
130 | @deffnx {C Function} scm_set_cdr_x (pair, value) | |
131 | Stores @var{value} in the cdr field of @var{pair}. The value returned | |
132 | by @code{set-cdr!} is unspecified. | |
133 | @end deffn | |
134 | ||
135 | ||
136 | @node Lists | |
137 | @section Lists | |
138 | @tpindex Lists | |
139 | ||
4c731ece NJ |
140 | A very important data type in Scheme---as well as in all other Lisp |
141 | dialects---is the data type @dfn{list}.@footnote{Strictly speaking, | |
142 | Scheme does not have a real datatype @dfn{list}. Lists are made up of | |
143 | @dfn{chained pairs}, and only exist by definition---a list is a chain | |
144 | of pairs which looks like a list.} | |
145 | ||
146 | This is the short definition of what a list is: | |
147 | ||
148 | @itemize @bullet | |
149 | @item | |
150 | Either the empty list @code{()}, | |
151 | ||
152 | @item | |
153 | or a pair which has a list in its cdr. | |
154 | @end itemize | |
155 | ||
156 | @c FIXME::martin: Describe the pair chaining in more detail. | |
157 | ||
158 | @c FIXME::martin: What is a proper, what an improper list? | |
159 | @c What is a circular list? | |
160 | ||
161 | @c FIXME::martin: Maybe steal some graphics from the Elisp reference | |
162 | @c manual? | |
163 | ||
164 | @menu | |
165 | * List Syntax:: Writing literal lists. | |
166 | * List Predicates:: Testing lists. | |
167 | * List Constructors:: Creating new lists. | |
168 | * List Selection:: Selecting from lists, getting their length. | |
169 | * Append/Reverse:: Appending and reversing lists. | |
170 | * List Modification:: Modifying existing lists. | |
171 | * List Searching:: Searching for list elements | |
172 | * List Mapping:: Applying procedures to lists. | |
173 | @end menu | |
174 | ||
175 | @node List Syntax | |
176 | @subsection List Read Syntax | |
177 | ||
4c731ece NJ |
178 | The syntax for lists is an opening parentheses, then all the elements of |
179 | the list (separated by whitespace) and finally a closing | |
180 | parentheses.@footnote{Note that there is no separation character between | |
181 | the list elements, like a comma or a semicolon.}. | |
182 | ||
183 | @lisp | |
184 | (1 2 3) ; @r{a list of the numbers 1, 2 and 3} | |
185 | ("foo" bar 3.1415) ; @r{a string, a symbol and a real number} | |
186 | () ; @r{the empty list} | |
187 | @end lisp | |
188 | ||
189 | The last example needs a bit more explanation. A list with no elements, | |
190 | called the @dfn{empty list}, is special in some ways. It is used for | |
191 | terminating lists by storing it into the cdr of the last pair that makes | |
192 | up a list. An example will clear that up: | |
193 | ||
194 | @lisp | |
195 | (car '(1)) | |
196 | @result{} | |
197 | 1 | |
198 | (cdr '(1)) | |
199 | @result{} | |
200 | () | |
201 | @end lisp | |
202 | ||
203 | This example also shows that lists have to be quoted (REFFIXME) when | |
204 | written, because they would otherwise be mistakingly taken as procedure | |
205 | applications (@pxref{Simple Invocation}). | |
206 | ||
207 | ||
208 | @node List Predicates | |
209 | @subsection List Predicates | |
210 | ||
4c731ece NJ |
211 | Often it is useful to test whether a given Scheme object is a list or |
212 | not. List-processing procedures could use this information to test | |
213 | whether their input is valid, or they could do different things | |
214 | depending on the datatype of their arguments. | |
215 | ||
216 | @rnindex list? | |
217 | @deffn {Scheme Procedure} list? x | |
218 | @deffnx {C Function} scm_list_p (x) | |
219 | Return @code{#t} iff @var{x} is a proper list, else @code{#f}. | |
220 | @end deffn | |
221 | ||
222 | The predicate @code{null?} is often used in list-processing code to | |
223 | tell whether a given list has run out of elements. That is, a loop | |
224 | somehow deals with the elements of a list until the list satisfies | |
225 | @code{null?}. Then, the algorithm terminates. | |
226 | ||
227 | @rnindex null? | |
228 | @deffn {Scheme Procedure} null? x | |
229 | @deffnx {C Function} scm_null_p (x) | |
230 | Return @code{#t} iff @var{x} is the empty list, else @code{#f}. | |
231 | @end deffn | |
232 | ||
233 | @node List Constructors | |
234 | @subsection List Constructors | |
235 | ||
236 | This section describes the procedures for constructing new lists. | |
237 | @code{list} simply returns a list where the elements are the arguments, | |
238 | @code{cons*} is similar, but the last argument is stored in the cdr of | |
239 | the last pair of the list. | |
240 | ||
51787257 KR |
241 | @c C Function scm_list(rest) used to be documented here, but it's a |
242 | @c no-op since it does nothing but return the list the caller must | |
243 | @c have already created. | |
244 | @c | |
245 | @deffn {Scheme Procedure} list elem1 @dots{} elemN | |
246 | @deffnx {C Function} scm_list_1 (elem1) | |
247 | @deffnx {C Function} scm_list_2 (elem1, elem2) | |
248 | @deffnx {C Function} scm_list_3 (elem1, elem2, elem3) | |
249 | @deffnx {C Function} scm_list_4 (elem1, elem2, elem3, elem4) | |
250 | @deffnx {C Function} scm_list_5 (elem1, elem2, elem3, elem4, elem5) | |
251 | @deffnx {C Function} scm_list_n (elem1, @dots{}, elemN, @nicode{SCM_UNDEFINED}) | |
4c731ece | 252 | @rnindex list |
51787257 KR |
253 | Return a new list containing elements @var{elem1} to @var{elemN}. |
254 | ||
255 | @code{scm_list_n} takes a variable number of arguments, terminated by | |
256 | the special @code{SCM_UNDEFINED}. That final @code{SCM_UNDEFINED} is | |
257 | not included in the list. None of @var{elem1} to @var{elemN} can | |
258 | themselves be @code{SCM_UNDEFINED}, or @code{scm_list_n} will | |
259 | terminate at that point. | |
4c731ece NJ |
260 | @end deffn |
261 | ||
603707f4 KR |
262 | @c C Function scm_cons_star(arg1,rest) used to be documented here, |
263 | @c but it's not really a useful interface, since it expects the | |
264 | @c caller to have already consed up all but the first argument | |
265 | @c already. | |
266 | @c | |
4c731ece | 267 | @deffn {Scheme Procedure} cons* arg1 arg2 @dots{} |
4c731ece NJ |
268 | Like @code{list}, but the last arg provides the tail of the |
269 | constructed list, returning @code{(cons @var{arg1} (cons | |
270 | @var{arg2} (cons @dots{} @var{argn})))}. Requires at least one | |
271 | argument. If given one argument, that argument is returned as | |
272 | result. This function is called @code{list*} in some other | |
273 | Schemes and in Common LISP. | |
274 | @end deffn | |
275 | ||
276 | @deffn {Scheme Procedure} list-copy lst | |
277 | @deffnx {C Function} scm_list_copy (lst) | |
278 | Return a (newly-created) copy of @var{lst}. | |
279 | @end deffn | |
280 | ||
281 | @deffn {Scheme Procedure} make-list n [init] | |
282 | Create a list containing of @var{n} elements, where each element is | |
283 | initialized to @var{init}. @var{init} defaults to the empty list | |
284 | @code{()} if not given. | |
285 | @end deffn | |
286 | ||
287 | Note that @code{list-copy} only makes a copy of the pairs which make up | |
288 | the spine of the lists. The list elements are not copied, which means | |
85a9b4ed | 289 | that modifying the elements of the new list also modifies the elements |
4c731ece NJ |
290 | of the old list. On the other hand, applying procedures like |
291 | @code{set-cdr!} or @code{delv!} to the new list will not alter the old | |
292 | list. If you also need to copy the list elements (making a deep copy), | |
293 | use the procedure @code{copy-tree} (@pxref{Copying}). | |
294 | ||
295 | @node List Selection | |
296 | @subsection List Selection | |
297 | ||
4c731ece NJ |
298 | These procedures are used to get some information about a list, or to |
299 | retrieve one or more elements of a list. | |
300 | ||
301 | @rnindex length | |
302 | @deffn {Scheme Procedure} length lst | |
303 | @deffnx {C Function} scm_length (lst) | |
304 | Return the number of elements in list @var{lst}. | |
305 | @end deffn | |
306 | ||
307 | @deffn {Scheme Procedure} last-pair lst | |
308 | @deffnx {C Function} scm_last_pair (lst) | |
309 | Return a pointer to the last pair in @var{lst}, signalling an error if | |
310 | @var{lst} is circular. | |
311 | @end deffn | |
312 | ||
313 | @rnindex list-ref | |
314 | @deffn {Scheme Procedure} list-ref list k | |
315 | @deffnx {C Function} scm_list_ref (list, k) | |
316 | Return the @var{k}th element from @var{list}. | |
317 | @end deffn | |
318 | ||
319 | @rnindex list-tail | |
320 | @deffn {Scheme Procedure} list-tail lst k | |
321 | @deffnx {Scheme Procedure} list-cdr-ref lst k | |
322 | @deffnx {C Function} scm_list_tail (lst, k) | |
323 | Return the "tail" of @var{lst} beginning with its @var{k}th element. | |
324 | The first element of the list is considered to be element 0. | |
325 | ||
326 | @code{list-tail} and @code{list-cdr-ref} are identical. It may help to | |
327 | think of @code{list-cdr-ref} as accessing the @var{k}th cdr of the list, | |
328 | or returning the results of cdring @var{k} times down @var{lst}. | |
329 | @end deffn | |
330 | ||
331 | @deffn {Scheme Procedure} list-head lst k | |
332 | @deffnx {C Function} scm_list_head (lst, k) | |
333 | Copy the first @var{k} elements from @var{lst} into a new list, and | |
334 | return it. | |
335 | @end deffn | |
336 | ||
337 | @node Append/Reverse | |
338 | @subsection Append and Reverse | |
339 | ||
4c731ece NJ |
340 | @code{append} and @code{append!} are used to concatenate two or more |
341 | lists in order to form a new list. @code{reverse} and @code{reverse!} | |
342 | return lists with the same elements as their arguments, but in reverse | |
343 | order. The procedure variants with an @code{!} directly modify the | |
344 | pairs which form the list, whereas the other procedures create new | |
345 | pairs. This is why you should be careful when using the side-effecting | |
346 | variants. | |
347 | ||
348 | @rnindex append | |
697039a9 KR |
349 | @deffn {Scheme Procedure} append lst1 @dots{} lstN |
350 | @deffnx {Scheme Procedure} append! lst1 @dots{} lstN | |
351 | @deffnx {C Function} scm_append (lstlst) | |
352 | @deffnx {C Function} scm_append_x (lstlst) | |
353 | Return a list comprising all the elements of lists @var{lst1} to | |
354 | @var{lstN}. | |
355 | ||
4c731ece NJ |
356 | @lisp |
357 | (append '(x) '(y)) @result{} (x y) | |
358 | (append '(a) '(b c d)) @result{} (a b c d) | |
359 | (append '(a (b)) '((c))) @result{} (a (b) (c)) | |
360 | @end lisp | |
697039a9 KR |
361 | |
362 | The last argument @var{lstN} may actually be any object; an improper | |
363 | list results if the last argument is not a proper list. | |
364 | ||
4c731ece NJ |
365 | @lisp |
366 | (append '(a b) '(c . d)) @result{} (a b c . d) | |
367 | (append '() 'a) @result{} a | |
368 | @end lisp | |
4c731ece | 369 | |
697039a9 KR |
370 | @code{append} doesn't modify the given lists, but the return may share |
371 | structure with the final @var{lstN}. @code{append!} modifies the | |
372 | given lists to form its return. | |
373 | ||
374 | For @code{scm_append} and @code{scm_append_x}, @var{lstlst} is a list | |
375 | of the list operands @var{lst1} @dots{} @var{lstN}. That @var{lstlst} | |
376 | itself is not modified or used in the return. | |
4c731ece NJ |
377 | @end deffn |
378 | ||
379 | @rnindex reverse | |
380 | @deffn {Scheme Procedure} reverse lst | |
c537e01b | 381 | @deffnx {Scheme Procedure} reverse! lst [newtail] |
4c731ece | 382 | @deffnx {C Function} scm_reverse (lst) |
c537e01b KR |
383 | @deffnx {C Function} scm_reverse_x (lst, newtail) |
384 | Return a list comprising the elements of @var{lst}, in reverse order. | |
385 | ||
386 | @code{reverse} constructs a new list, @code{reverse!} modifies | |
387 | @var{lst} in constructing its return. | |
4c731ece | 388 | |
c537e01b KR |
389 | For @code{reverse!}, the optional @var{newtail} is appended to to the |
390 | result. @var{newtail} isn't reversed, it simply becomes the list | |
391 | tail. For @code{scm_reverse_x}, the @var{newtail} parameter is | |
392 | mandatory, but can be @code{SCM_EOL} if no further tail is required. | |
4c731ece NJ |
393 | @end deffn |
394 | ||
395 | @node List Modification | |
396 | @subsection List Modification | |
397 | ||
398 | The following procedures modify an existing list, either by changing | |
399 | elements of the list, or by changing the list structure itself. | |
400 | ||
401 | @deffn {Scheme Procedure} list-set! list k val | |
402 | @deffnx {C Function} scm_list_set_x (list, k, val) | |
403 | Set the @var{k}th element of @var{list} to @var{val}. | |
404 | @end deffn | |
405 | ||
406 | @deffn {Scheme Procedure} list-cdr-set! list k val | |
407 | @deffnx {C Function} scm_list_cdr_set_x (list, k, val) | |
408 | Set the @var{k}th cdr of @var{list} to @var{val}. | |
409 | @end deffn | |
410 | ||
411 | @deffn {Scheme Procedure} delq item lst | |
412 | @deffnx {C Function} scm_delq (item, lst) | |
413 | Return a newly-created copy of @var{lst} with elements | |
414 | @code{eq?} to @var{item} removed. This procedure mirrors | |
415 | @code{memq}: @code{delq} compares elements of @var{lst} against | |
416 | @var{item} with @code{eq?}. | |
417 | @end deffn | |
418 | ||
419 | @deffn {Scheme Procedure} delv item lst | |
420 | @deffnx {C Function} scm_delv (item, lst) | |
421 | Return a newly-created copy of @var{lst} with elements | |
422 | @code{eqv?} to @var{item} removed. This procedure mirrors | |
423 | @code{memv}: @code{delv} compares elements of @var{lst} against | |
424 | @var{item} with @code{eqv?}. | |
425 | @end deffn | |
426 | ||
427 | @deffn {Scheme Procedure} delete item lst | |
428 | @deffnx {C Function} scm_delete (item, lst) | |
429 | Return a newly-created copy of @var{lst} with elements | |
430 | @code{equal?} to @var{item} removed. This procedure mirrors | |
431 | @code{member}: @code{delete} compares elements of @var{lst} | |
432 | against @var{item} with @code{equal?}. | |
433 | @end deffn | |
434 | ||
435 | @deffn {Scheme Procedure} delq! item lst | |
436 | @deffnx {Scheme Procedure} delv! item lst | |
437 | @deffnx {Scheme Procedure} delete! item lst | |
438 | @deffnx {C Function} scm_delq_x (item, lst) | |
439 | @deffnx {C Function} scm_delv_x (item, lst) | |
440 | @deffnx {C Function} scm_delete_x (item, lst) | |
441 | These procedures are destructive versions of @code{delq}, @code{delv} | |
442 | and @code{delete}: they modify the pointers in the existing @var{lst} | |
443 | rather than creating a new list. Caveat evaluator: Like other | |
444 | destructive list functions, these functions cannot modify the binding of | |
445 | @var{lst}, and so cannot be used to delete the first element of | |
446 | @var{lst} destructively. | |
447 | @end deffn | |
448 | ||
449 | @deffn {Scheme Procedure} delq1! item lst | |
450 | @deffnx {C Function} scm_delq1_x (item, lst) | |
451 | Like @code{delq!}, but only deletes the first occurrence of | |
452 | @var{item} from @var{lst}. Tests for equality using | |
453 | @code{eq?}. See also @code{delv1!} and @code{delete1!}. | |
454 | @end deffn | |
455 | ||
456 | @deffn {Scheme Procedure} delv1! item lst | |
457 | @deffnx {C Function} scm_delv1_x (item, lst) | |
458 | Like @code{delv!}, but only deletes the first occurrence of | |
459 | @var{item} from @var{lst}. Tests for equality using | |
460 | @code{eqv?}. See also @code{delq1!} and @code{delete1!}. | |
461 | @end deffn | |
462 | ||
463 | @deffn {Scheme Procedure} delete1! item lst | |
464 | @deffnx {C Function} scm_delete1_x (item, lst) | |
465 | Like @code{delete!}, but only deletes the first occurrence of | |
466 | @var{item} from @var{lst}. Tests for equality using | |
467 | @code{equal?}. See also @code{delq1!} and @code{delv1!}. | |
468 | @end deffn | |
469 | ||
60e25dc4 KR |
470 | @deffn {Scheme Procedure} filter pred lst |
471 | @deffnx {Scheme Procedure} filter! pred lst | |
472 | Return a list containing all elements from @var{lst} which satisfy the | |
473 | predicate @var{pred}. The elements in the result list have the same | |
474 | order as in @var{lst}. The order in which @var{pred} is applied to | |
475 | the list elements is not specified. | |
476 | ||
477 | @code{filter!} is allowed, but not required to modify the structure of | |
478 | @end deffn | |
479 | ||
4c731ece NJ |
480 | @node List Searching |
481 | @subsection List Searching | |
482 | ||
4c731ece NJ |
483 | The following procedures search lists for particular elements. They use |
484 | different comparison predicates for comparing list elements with the | |
485 | object to be searched. When they fail, they return @code{#f}, otherwise | |
486 | they return the sublist whose car is equal to the search object, where | |
487 | equality depends on the equality predicate used. | |
488 | ||
489 | @rnindex memq | |
490 | @deffn {Scheme Procedure} memq x lst | |
491 | @deffnx {C Function} scm_memq (x, lst) | |
492 | Return the first sublist of @var{lst} whose car is @code{eq?} | |
493 | to @var{x} where the sublists of @var{lst} are the non-empty | |
494 | lists returned by @code{(list-tail @var{lst} @var{k})} for | |
495 | @var{k} less than the length of @var{lst}. If @var{x} does not | |
496 | occur in @var{lst}, then @code{#f} (not the empty list) is | |
497 | returned. | |
498 | @end deffn | |
499 | ||
500 | @rnindex memv | |
501 | @deffn {Scheme Procedure} memv x lst | |
502 | @deffnx {C Function} scm_memv (x, lst) | |
503 | Return the first sublist of @var{lst} whose car is @code{eqv?} | |
504 | to @var{x} where the sublists of @var{lst} are the non-empty | |
505 | lists returned by @code{(list-tail @var{lst} @var{k})} for | |
506 | @var{k} less than the length of @var{lst}. If @var{x} does not | |
507 | occur in @var{lst}, then @code{#f} (not the empty list) is | |
508 | returned. | |
509 | @end deffn | |
510 | ||
511 | @rnindex member | |
512 | @deffn {Scheme Procedure} member x lst | |
513 | @deffnx {C Function} scm_member (x, lst) | |
514 | Return the first sublist of @var{lst} whose car is | |
515 | @code{equal?} to @var{x} where the sublists of @var{lst} are | |
516 | the non-empty lists returned by @code{(list-tail @var{lst} | |
517 | @var{k})} for @var{k} less than the length of @var{lst}. If | |
518 | @var{x} does not occur in @var{lst}, then @code{#f} (not the | |
519 | empty list) is returned. | |
520 | @end deffn | |
521 | ||
4c731ece NJ |
522 | |
523 | @node List Mapping | |
524 | @subsection List Mapping | |
525 | ||
4c731ece NJ |
526 | List processing is very convenient in Scheme because the process of |
527 | iterating over the elements of a list can be highly abstracted. The | |
528 | procedures in this section are the most basic iterating procedures for | |
529 | lists. They take a procedure and one or more lists as arguments, and | |
530 | apply the procedure to each element of the list. They differ in their | |
531 | return value. | |
532 | ||
533 | @rnindex map | |
534 | @c begin (texi-doc-string "guile" "map") | |
535 | @deffn {Scheme Procedure} map proc arg1 arg2 @dots{} | |
536 | @deffnx {Scheme Procedure} map-in-order proc arg1 arg2 @dots{} | |
537 | @deffnx {C Function} scm_map (proc, arg1, args) | |
538 | Apply @var{proc} to each element of the list @var{arg1} (if only two | |
539 | arguments are given), or to the corresponding elements of the argument | |
540 | lists (if more than two arguments are given). The result(s) of the | |
541 | procedure applications are saved and returned in a list. For | |
542 | @code{map}, the order of procedure applications is not specified, | |
543 | @code{map-in-order} applies the procedure from left to right to the list | |
544 | elements. | |
545 | @end deffn | |
546 | ||
547 | @rnindex for-each | |
548 | @c begin (texi-doc-string "guile" "for-each") | |
549 | @deffn {Scheme Procedure} for-each proc arg1 arg2 @dots{} | |
550 | Like @code{map}, but the procedure is always applied from left to right, | |
551 | and the result(s) of the procedure applications are thrown away. The | |
552 | return value is not specified. | |
553 | @end deffn | |
554 | ||
555 | ||
556 | @node Vectors | |
557 | @section Vectors | |
558 | @tpindex Vectors | |
559 | ||
4c731ece NJ |
560 | Vectors are sequences of Scheme objects. Unlike lists, the length of a |
561 | vector, once the vector is created, cannot be changed. The advantage of | |
562 | vectors over lists is that the time required to access one element of a vector | |
563 | given its @dfn{position} (synonymous with @dfn{index}), a zero-origin number, | |
564 | is constant, whereas lists have an access time linear to the position of the | |
565 | accessed element in the list. | |
566 | ||
567 | Vectors can contain any kind of Scheme object; it is even possible to have | |
568 | different types of objects in the same vector. For vectors containing | |
569 | vectors, you may wish to use arrays, instead. Note, too, that some array | |
570 | procedures operate happily on vectors (@pxref{Arrays}). | |
571 | ||
0624ce33 NJ |
572 | @menu |
573 | * Vector Syntax:: Read syntax for vectors. | |
574 | * Vector Creation:: Dynamic vector creation and validation. | |
575 | * Vector Accessors:: Accessing and modifying vector contents. | |
576 | @end menu | |
577 | ||
578 | ||
579 | @node Vector Syntax | |
580 | @subsection Read Syntax for Vectors | |
4c731ece NJ |
581 | |
582 | Vectors can literally be entered in source code, just like strings, | |
583 | characters or some of the other data types. The read syntax for vectors | |
584 | is as follows: A sharp sign (@code{#}), followed by an opening | |
585 | parentheses, all elements of the vector in their respective read syntax, | |
586 | and finally a closing parentheses. The following are examples of the | |
587 | read syntax for vectors; where the first vector only contains numbers | |
588 | and the second three different object types: a string, a symbol and a | |
589 | number in hexadecimal notation. | |
590 | ||
591 | @lisp | |
592 | #(1 2 3) | |
593 | #("Hello" foo #xdeadbeef) | |
594 | @end lisp | |
595 | ||
42ad901d DH |
596 | Like lists, vectors have to be quoted (REFFIXME): |
597 | ||
598 | @lisp | |
599 | '#(a b c) @result{} #(a b c) | |
600 | @end lisp | |
4c731ece | 601 | |
0624ce33 NJ |
602 | @node Vector Creation |
603 | @subsection Dynamic Vector Creation and Validation | |
4c731ece | 604 | |
0624ce33 NJ |
605 | Instead of creating a vector implicitly by using the read syntax just |
606 | described, you can create a vector dynamically by calling one of the | |
607 | @code{vector} and @code{list->vector} primitives with the list of Scheme | |
608 | values that you want to place into a vector. The size of the vector | |
609 | thus created is determined implicitly by the number of arguments given. | |
4c731ece NJ |
610 | |
611 | @rnindex vector | |
612 | @rnindex list->vector | |
613 | @deffn {Scheme Procedure} vector . l | |
614 | @deffnx {Scheme Procedure} list->vector l | |
615 | @deffnx {C Function} scm_vector (l) | |
616 | Return a newly allocated vector composed of the | |
617 | given arguments. Analogous to @code{list}. | |
618 | ||
619 | @lisp | |
620 | (vector 'a 'b 'c) @result{} #(a b c) | |
621 | @end lisp | |
622 | @end deffn | |
623 | ||
0624ce33 NJ |
624 | (As an aside, an interesting implementation detail is that the Guile |
625 | reader reads the @code{#(@dots{})} syntax by reading everything but the | |
626 | initial @code{#} as a @emph{list}, and then passing the list that | |
627 | results to @code{list->vector}. Notice how neatly this fits with the | |
628 | similarity between the read (and print) syntaxes for lists and vectors.) | |
629 | ||
630 | The inverse operation is @code{vector->list}: | |
631 | ||
4c731ece NJ |
632 | @rnindex vector->list |
633 | @deffn {Scheme Procedure} vector->list v | |
634 | @deffnx {C Function} scm_vector_to_list (v) | |
635 | Return a newly allocated list composed of the elements of @var{v}. | |
636 | ||
637 | @lisp | |
638 | (vector->list '#(dah dah didah)) @result{} (dah dah didah) | |
639 | (list->vector '(dididit dah)) @result{} #(dididit dah) | |
640 | @end lisp | |
641 | @end deffn | |
642 | ||
0624ce33 NJ |
643 | To allocate a vector with an explicitly specified size, use |
644 | @code{make-vector}. With this primitive you can also specify an initial | |
645 | value for the vector elements (the same value for all elements, that | |
646 | is): | |
647 | ||
648 | @rnindex make-vector | |
649 | @deffn {Scheme Procedure} make-vector k [fill] | |
650 | @deffnx {C Function} scm_make_vector (k, fill) | |
651 | Return a newly allocated vector of @var{k} elements. If a | |
652 | second argument is given, then each position is initialized to | |
653 | @var{fill}. Otherwise the initial contents of each position is | |
654 | unspecified. | |
655 | @end deffn | |
656 | ||
657 | To check whether an arbitrary Scheme value @emph{is} a vector, use the | |
658 | @code{vector?} primitive: | |
659 | ||
660 | @rnindex vector? | |
661 | @deffn {Scheme Procedure} vector? obj | |
662 | @deffnx {C Function} scm_vector_p (obj) | |
663 | Return @code{#t} if @var{obj} is a vector, otherwise return | |
664 | @code{#f}. | |
665 | @end deffn | |
666 | ||
667 | ||
668 | @node Vector Accessors | |
669 | @subsection Accessing and Modifying Vector Contents | |
4c731ece | 670 | |
0624ce33 NJ |
671 | @code{vector-length} and @code{vector-ref} return information about a |
672 | given vector, respectively its size and the elements that are contained | |
673 | in the vector. | |
4c731ece | 674 | |
0624ce33 NJ |
675 | @rnindex vector-length |
676 | @deffn {Scheme Procedure} vector-length vector | |
677 | @deffnx {C Function} scm_vector_length vector | |
678 | Return the number of elements in @var{vector} as an exact integer. | |
679 | @end deffn | |
680 | ||
681 | @rnindex vector-ref | |
682 | @deffn {Scheme Procedure} vector-ref vector k | |
683 | @deffnx {C Function} scm_vector_ref vector k | |
684 | Return the contents of position @var{k} of @var{vector}. | |
685 | @var{k} must be a valid index of @var{vector}. | |
686 | @lisp | |
687 | (vector-ref '#(1 1 2 3 5 8 13 21) 5) @result{} 8 | |
688 | (vector-ref '#(1 1 2 3 5 8 13 21) | |
689 | (let ((i (round (* 2 (acos -1))))) | |
690 | (if (inexact? i) | |
691 | (inexact->exact i) | |
692 | i))) @result{} 13 | |
693 | @end lisp | |
694 | @end deffn | |
695 | ||
696 | A vector created by one of the dynamic vector constructor procedures | |
697 | (@pxref{Vector Creation}) can be modified using the following | |
698 | procedures. | |
699 | ||
700 | @emph{NOTE:} According to R5RS, it is an error to use any of these | |
701 | procedures on a literally read vector, because such vectors should be | |
702 | considered as constants. Currently, however, Guile does not detect this | |
4c731ece NJ |
703 | error. |
704 | ||
705 | @rnindex vector-set! | |
706 | @deffn {Scheme Procedure} vector-set! vector k obj | |
0624ce33 | 707 | @deffnx {C Function} scm_vector_set_x vector k obj |
4c731ece NJ |
708 | Store @var{obj} in position @var{k} of @var{vector}. |
709 | @var{k} must be a valid index of @var{vector}. | |
710 | The value returned by @samp{vector-set!} is unspecified. | |
711 | @lisp | |
712 | (let ((vec (vector 0 '(2 2 2 2) "Anna"))) | |
713 | (vector-set! vec 1 '("Sue" "Sue")) | |
714 | vec) @result{} #(0 ("Sue" "Sue") "Anna") | |
715 | @end lisp | |
716 | @end deffn | |
717 | ||
718 | @rnindex vector-fill! | |
719 | @deffn {Scheme Procedure} vector-fill! v fill | |
720 | @deffnx {C Function} scm_vector_fill_x (v, fill) | |
721 | Store @var{fill} in every position of @var{vector}. The value | |
722 | returned by @code{vector-fill!} is unspecified. | |
723 | @end deffn | |
724 | ||
725 | @deffn {Scheme Procedure} vector-move-left! vec1 start1 end1 vec2 start2 | |
726 | @deffnx {C Function} scm_vector_move_left_x (vec1, start1, end1, vec2, start2) | |
727 | Copy elements from @var{vec1}, positions @var{start1} to @var{end1}, | |
728 | to @var{vec2} starting at position @var{start2}. @var{start1} and | |
729 | @var{start2} are inclusive indices; @var{end1} is exclusive. | |
730 | ||
731 | @code{vector-move-left!} copies elements in leftmost order. | |
732 | Therefore, in the case where @var{vec1} and @var{vec2} refer to the | |
733 | same vector, @code{vector-move-left!} is usually appropriate when | |
734 | @var{start1} is greater than @var{start2}. | |
735 | @end deffn | |
736 | ||
737 | @deffn {Scheme Procedure} vector-move-right! vec1 start1 end1 vec2 start2 | |
738 | @deffnx {C Function} scm_vector_move_right_x (vec1, start1, end1, vec2, start2) | |
739 | Copy elements from @var{vec1}, positions @var{start1} to @var{end1}, | |
740 | to @var{vec2} starting at position @var{start2}. @var{start1} and | |
741 | @var{start2} are inclusive indices; @var{end1} is exclusive. | |
742 | ||
743 | @code{vector-move-right!} copies elements in rightmost order. | |
744 | Therefore, in the case where @var{vec1} and @var{vec2} refer to the | |
745 | same vector, @code{vector-move-right!} is usually appropriate when | |
746 | @var{start1} is less than @var{start2}. | |
747 | @end deffn | |
748 | ||
4c731ece NJ |
749 | |
750 | @node Records | |
751 | @section Records | |
752 | ||
753 | A @dfn{record type} is a first class object representing a user-defined | |
754 | data type. A @dfn{record} is an instance of a record type. | |
755 | ||
756 | @deffn {Scheme Procedure} record? obj | |
757 | Return @code{#t} if @var{obj} is a record of any type and @code{#f} | |
758 | otherwise. | |
759 | ||
760 | Note that @code{record?} may be true of any Scheme value; there is no | |
761 | promise that records are disjoint with other Scheme types. | |
762 | @end deffn | |
763 | ||
764 | @deffn {Scheme Procedure} make-record-type type-name field-names | |
765 | Return a @dfn{record-type descriptor}, a value representing a new data | |
766 | type disjoint from all others. The @var{type-name} argument must be a | |
767 | string, but is only used for debugging purposes (such as the printed | |
768 | representation of a record of the new type). The @var{field-names} | |
769 | argument is a list of symbols naming the @dfn{fields} of a record of the | |
770 | new type. It is an error if the list contains any duplicates. It is | |
771 | unspecified how record-type descriptors are represented. | |
772 | @end deffn | |
773 | ||
774 | @deffn {Scheme Procedure} record-constructor rtd [field-names] | |
775 | Return a procedure for constructing new members of the type represented | |
776 | by @var{rtd}. The returned procedure accepts exactly as many arguments | |
777 | as there are symbols in the given list, @var{field-names}; these are | |
778 | used, in order, as the initial values of those fields in a new record, | |
779 | which is returned by the constructor procedure. The values of any | |
780 | fields not named in that list are unspecified. The @var{field-names} | |
781 | argument defaults to the list of field names in the call to | |
782 | @code{make-record-type} that created the type represented by @var{rtd}; | |
783 | if the @var{field-names} argument is provided, it is an error if it | |
784 | contains any duplicates or any symbols not in the default list. | |
785 | @end deffn | |
786 | ||
787 | @deffn {Scheme Procedure} record-predicate rtd | |
788 | Return a procedure for testing membership in the type represented by | |
789 | @var{rtd}. The returned procedure accepts exactly one argument and | |
790 | returns a true value if the argument is a member of the indicated record | |
791 | type; it returns a false value otherwise. | |
792 | @end deffn | |
793 | ||
794 | @deffn {Scheme Procedure} record-accessor rtd field-name | |
795 | Return a procedure for reading the value of a particular field of a | |
796 | member of the type represented by @var{rtd}. The returned procedure | |
797 | accepts exactly one argument which must be a record of the appropriate | |
798 | type; it returns the current value of the field named by the symbol | |
799 | @var{field-name} in that record. The symbol @var{field-name} must be a | |
800 | member of the list of field-names in the call to @code{make-record-type} | |
801 | that created the type represented by @var{rtd}. | |
802 | @end deffn | |
803 | ||
804 | @deffn {Scheme Procedure} record-modifier rtd field-name | |
805 | Return a procedure for writing the value of a particular field of a | |
806 | member of the type represented by @var{rtd}. The returned procedure | |
807 | accepts exactly two arguments: first, a record of the appropriate type, | |
808 | and second, an arbitrary Scheme value; it modifies the field named by | |
809 | the symbol @var{field-name} in that record to contain the given value. | |
810 | The returned value of the modifier procedure is unspecified. The symbol | |
811 | @var{field-name} must be a member of the list of field-names in the call | |
812 | to @code{make-record-type} that created the type represented by | |
813 | @var{rtd}. | |
814 | @end deffn | |
815 | ||
816 | @deffn {Scheme Procedure} record-type-descriptor record | |
817 | Return a record-type descriptor representing the type of the given | |
818 | record. That is, for example, if the returned descriptor were passed to | |
819 | @code{record-predicate}, the resulting predicate would return a true | |
820 | value when passed the given record. Note that it is not necessarily the | |
821 | case that the returned descriptor is the one that was passed to | |
822 | @code{record-constructor} in the call that created the constructor | |
823 | procedure that created the given record. | |
824 | @end deffn | |
825 | ||
826 | @deffn {Scheme Procedure} record-type-name rtd | |
827 | Return the type-name associated with the type represented by rtd. The | |
828 | returned value is @code{eqv?} to the @var{type-name} argument given in | |
829 | the call to @code{make-record-type} that created the type represented by | |
830 | @var{rtd}. | |
831 | @end deffn | |
832 | ||
833 | @deffn {Scheme Procedure} record-type-fields rtd | |
834 | Return a list of the symbols naming the fields in members of the type | |
835 | represented by @var{rtd}. The returned value is @code{equal?} to the | |
836 | field-names argument given in the call to @code{make-record-type} that | |
837 | created the type represented by @var{rtd}. | |
838 | @end deffn | |
839 | ||
840 | ||
841 | @node Structures | |
842 | @section Structures | |
843 | @tpindex Structures | |
844 | ||
845 | [FIXME: this is pasted in from Tom Lord's original guile.texi and should | |
846 | be reviewed] | |
847 | ||
848 | A @dfn{structure type} is a first class user-defined data type. A | |
849 | @dfn{structure} is an instance of a structure type. A structure type is | |
850 | itself a structure. | |
851 | ||
852 | Structures are less abstract and more general than traditional records. | |
853 | In fact, in Guile Scheme, records are implemented using structures. | |
854 | ||
855 | @menu | |
856 | * Structure Concepts:: The structure of Structures | |
857 | * Structure Layout:: Defining the layout of structure types | |
858 | * Structure Basics:: make-, -ref and -set! procedures for structs | |
859 | * Vtables:: Accessing type-specific data | |
860 | @end menu | |
861 | ||
862 | @node Structure Concepts | |
863 | @subsection Structure Concepts | |
864 | ||
865 | A structure object consists of a handle, structure data, and a vtable. | |
866 | The handle is a Scheme value which points to both the vtable and the | |
867 | structure's data. Structure data is a dynamically allocated region of | |
868 | memory, private to the structure, divided up into typed fields. A | |
869 | vtable is another structure used to hold type-specific data. Multiple | |
870 | structures can share a common vtable. | |
871 | ||
872 | Three concepts are key to understanding structures. | |
873 | ||
874 | @itemize @bullet{} | |
875 | @item @dfn{layout specifications} | |
876 | ||
877 | Layout specifications determine how memory allocated to structures is | |
878 | divided up into fields. Programmers must write a layout specification | |
879 | whenever a new type of structure is defined. | |
880 | ||
881 | @item @dfn{structural accessors} | |
882 | ||
883 | Structure access is by field number. There is only one set of | |
884 | accessors common to all structure objects. | |
885 | ||
886 | @item @dfn{vtables} | |
887 | ||
888 | Vtables, themselves structures, are first class representations of | |
889 | disjoint sub-types of structures in general. In most cases, when a | |
85a9b4ed | 890 | new structure is created, programmers must specify a vtable for the |
4c731ece NJ |
891 | new structure. Each vtable has a field describing the layout of its |
892 | instances. Vtables can have additional, user-defined fields as well. | |
893 | @end itemize | |
894 | ||
895 | ||
896 | ||
897 | @node Structure Layout | |
898 | @subsection Structure Layout | |
899 | ||
900 | When a structure is created, a region of memory is allocated to hold its | |
901 | state. The @dfn{layout} of the structure's type determines how that | |
902 | memory is divided into fields. | |
903 | ||
904 | Each field has a specified type. There are only three types allowed, each | |
905 | corresponding to a one letter code. The allowed types are: | |
906 | ||
907 | @itemize @bullet{} | |
908 | @item 'u' -- unprotected | |
909 | ||
910 | The field holds binary data that is not GC protected. | |
911 | ||
912 | @item 'p' -- protected | |
913 | ||
914 | The field holds a Scheme value and is GC protected. | |
915 | ||
916 | @item 's' -- self | |
917 | ||
918 | The field holds a Scheme value and is GC protected. When a structure is | |
919 | created with this type of field, the field is initialized to refer to | |
920 | the structure's own handle. This kind of field is mainly useful when | |
921 | mixing Scheme and C code in which the C code may need to compute a | |
801892e7 | 922 | structure's handle given only the address of its malloc'd data. |
4c731ece NJ |
923 | @end itemize |
924 | ||
925 | ||
926 | Each field also has an associated access protection. There are only | |
927 | three kinds of protection, each corresponding to a one letter code. | |
928 | The allowed protections are: | |
929 | ||
930 | @itemize @bullet{} | |
931 | @item 'w' -- writable | |
932 | ||
933 | The field can be read and written. | |
934 | ||
935 | @item 'r' -- readable | |
936 | ||
937 | The field can be read, but not written. | |
938 | ||
939 | @item 'o' -- opaque | |
940 | ||
941 | The field can be neither read nor written. This kind | |
942 | of protection is for fields useful only to built-in routines. | |
943 | @end itemize | |
944 | ||
945 | A layout specification is described by stringing together pairs | |
946 | of letters: one to specify a field type and one to specify a field | |
947 | protection. For example, a traditional cons pair type object could | |
948 | be described as: | |
949 | ||
950 | @example | |
951 | ; cons pairs have two writable fields of Scheme data | |
952 | "pwpw" | |
953 | @end example | |
954 | ||
955 | A pair object in which the first field is held constant could be: | |
956 | ||
957 | @example | |
958 | "prpw" | |
959 | @end example | |
960 | ||
961 | Binary fields, (fields of type "u"), hold one @dfn{word} each. The | |
962 | size of a word is a machine dependent value defined to be equal to the | |
963 | value of the C expression: @code{sizeof (long)}. | |
964 | ||
965 | The last field of a structure layout may specify a tail array. | |
966 | A tail array is indicated by capitalizing the field's protection | |
967 | code ('W', 'R' or 'O'). A tail-array field is replaced by | |
968 | a read-only binary data field containing an array size. The array | |
969 | size is determined at the time the structure is created. It is followed | |
970 | by a corresponding number of fields of the type specified for the | |
971 | tail array. For example, a conventional Scheme vector can be | |
972 | described as: | |
973 | ||
974 | @example | |
975 | ; A vector is an arbitrary number of writable fields holding Scheme | |
976 | ; values: | |
977 | "pW" | |
978 | @end example | |
979 | ||
980 | In the above example, field 0 contains the size of the vector and | |
981 | fields beginning at 1 contain the vector elements. | |
982 | ||
85a9b4ed | 983 | A kind of tagged vector (a constant tag followed by conventional |
4c731ece NJ |
984 | vector elements) might be: |
985 | ||
986 | @example | |
987 | "prpW" | |
988 | @end example | |
989 | ||
990 | ||
991 | Structure layouts are represented by specially interned symbols whose | |
992 | name is a string of type and protection codes. To create a new | |
993 | structure layout, use this procedure: | |
994 | ||
995 | @deffn {Scheme Procedure} make-struct-layout fields | |
996 | @deffnx {C Function} scm_make_struct_layout (fields) | |
997 | Return a new structure layout object. | |
998 | ||
999 | @var{fields} must be a string made up of pairs of characters | |
1000 | strung together. The first character of each pair describes a field | |
1001 | type, the second a field protection. Allowed types are 'p' for | |
1002 | GC-protected Scheme data, 'u' for unprotected binary data, and 's' for | |
1003 | a field that points to the structure itself. Allowed protections | |
1004 | are 'w' for mutable fields, 'r' for read-only fields, and 'o' for opaque | |
1005 | fields. The last field protection specification may be capitalized to | |
1006 | indicate that the field is a tail-array. | |
1007 | @end deffn | |
1008 | ||
1009 | ||
1010 | ||
1011 | @node Structure Basics | |
1012 | @subsection Structure Basics | |
1013 | ||
1014 | This section describes the basic procedures for creating and accessing | |
1015 | structures. | |
1016 | ||
1017 | @deffn {Scheme Procedure} make-struct vtable tail_array_size . init | |
1018 | @deffnx {C Function} scm_make_struct (vtable, tail_array_size, init) | |
1019 | Create a new structure. | |
1020 | ||
1021 | @var{type} must be a vtable structure (@pxref{Vtables}). | |
1022 | ||
1023 | @var{tail-elts} must be a non-negative integer. If the layout | |
1024 | specification indicated by @var{type} includes a tail-array, | |
1025 | this is the number of elements allocated to that array. | |
1026 | ||
1027 | The @var{init1}, @dots{} are optional arguments describing how | |
1028 | successive fields of the structure should be initialized. Only fields | |
1029 | with protection 'r' or 'w' can be initialized, except for fields of | |
1030 | type 's', which are automatically initialized to point to the new | |
1031 | structure itself; fields with protection 'o' can not be initialized by | |
1032 | Scheme programs. | |
1033 | ||
1034 | If fewer optional arguments than initializable fields are supplied, | |
1035 | fields of type 'p' get default value #f while fields of type 'u' are | |
1036 | initialized to 0. | |
1037 | ||
1038 | Structs are currently the basic representation for record-like data | |
1039 | structures in Guile. The plan is to eventually replace them with a | |
1040 | new representation which will at the same time be easier to use and | |
1041 | more powerful. | |
1042 | ||
1043 | For more information, see the documentation for @code{make-vtable-vtable}. | |
1044 | @end deffn | |
1045 | ||
1046 | @deffn {Scheme Procedure} struct? x | |
1047 | @deffnx {C Function} scm_struct_p (x) | |
1048 | Return @code{#t} iff @var{x} is a structure object, else | |
1049 | @code{#f}. | |
1050 | @end deffn | |
1051 | ||
1052 | ||
1053 | @deffn {Scheme Procedure} struct-ref handle pos | |
1054 | @deffnx {Scheme Procedure} struct-set! struct n value | |
1055 | @deffnx {C Function} scm_struct_ref (handle, pos) | |
1056 | @deffnx {C Function} scm_struct_set_x (struct, n, value) | |
1057 | Access (or modify) the @var{n}th field of @var{struct}. | |
1058 | ||
1059 | If the field is of type 'p', then it can be set to an arbitrary value. | |
1060 | ||
1061 | If the field is of type 'u', then it can only be set to a non-negative | |
1062 | integer value small enough to fit in one machine word. | |
1063 | @end deffn | |
1064 | ||
1065 | ||
1066 | ||
1067 | @node Vtables | |
1068 | @subsection Vtables | |
1069 | ||
1070 | Vtables are structures that are used to represent structure types. Each | |
1071 | vtable contains a layout specification in field | |
1072 | @code{vtable-index-layout} -- instances of the type are laid out | |
1073 | according to that specification. Vtables contain additional fields | |
1074 | which are used only internally to libguile. The variable | |
1075 | @code{vtable-offset-user} is bound to a field number. Vtable fields | |
1076 | at that position or greater are user definable. | |
1077 | ||
1078 | @deffn {Scheme Procedure} struct-vtable handle | |
1079 | @deffnx {C Function} scm_struct_vtable (handle) | |
1080 | Return the vtable structure that describes the type of @var{struct}. | |
1081 | @end deffn | |
1082 | ||
1083 | @deffn {Scheme Procedure} struct-vtable? x | |
1084 | @deffnx {C Function} scm_struct_vtable_p (x) | |
1085 | Return @code{#t} iff @var{x} is a vtable structure. | |
1086 | @end deffn | |
1087 | ||
1088 | If you have a vtable structure, @code{V}, you can create an instance of | |
1089 | the type it describes by using @code{(make-struct V ...)}. But where | |
1090 | does @code{V} itself come from? One possibility is that @code{V} is an | |
1091 | instance of a user-defined vtable type, @code{V'}, so that @code{V} is | |
1092 | created by using @code{(make-struct V' ...)}. Another possibility is | |
1093 | that @code{V} is an instance of the type it itself describes. Vtable | |
1094 | structures of the second sort are created by this procedure: | |
1095 | ||
1096 | @deffn {Scheme Procedure} make-vtable-vtable user_fields tail_array_size . init | |
1097 | @deffnx {C Function} scm_make_vtable_vtable (user_fields, tail_array_size, init) | |
1098 | Return a new, self-describing vtable structure. | |
1099 | ||
1100 | @var{user-fields} is a string describing user defined fields of the | |
1101 | vtable beginning at index @code{vtable-offset-user} | |
1102 | (see @code{make-struct-layout}). | |
1103 | ||
1104 | @var{tail-size} specifies the size of the tail-array (if any) of | |
1105 | this vtable. | |
1106 | ||
1107 | @var{init1}, @dots{} are the optional initializers for the fields of | |
1108 | the vtable. | |
1109 | ||
1110 | Vtables have one initializable system field---the struct printer. | |
1111 | This field comes before the user fields in the initializers passed | |
1112 | to @code{make-vtable-vtable} and @code{make-struct}, and thus works as | |
1113 | a third optional argument to @code{make-vtable-vtable} and a fourth to | |
1114 | @code{make-struct} when creating vtables: | |
1115 | ||
1116 | If the value is a procedure, it will be called instead of the standard | |
1117 | printer whenever a struct described by this vtable is printed. | |
1118 | The procedure will be called with arguments STRUCT and PORT. | |
1119 | ||
1120 | The structure of a struct is described by a vtable, so the vtable is | |
1121 | in essence the type of the struct. The vtable is itself a struct with | |
1122 | a vtable. This could go on forever if it weren't for the | |
1123 | vtable-vtables which are self-describing vtables, and thus terminate | |
1124 | the chain. | |
1125 | ||
1126 | There are several potential ways of using structs, but the standard | |
1127 | one is to use three kinds of structs, together building up a type | |
1128 | sub-system: one vtable-vtable working as the root and one or several | |
1129 | "types", each with a set of "instances". (The vtable-vtable should be | |
1130 | compared to the class <class> which is the class of itself.) | |
1131 | ||
1132 | @lisp | |
1133 | (define ball-root (make-vtable-vtable "pr" 0)) | |
1134 | ||
1135 | (define (make-ball-type ball-color) | |
1136 | (make-struct ball-root 0 | |
1137 | (make-struct-layout "pw") | |
1138 | (lambda (ball port) | |
1139 | (format port "#<a ~A ball owned by ~A>" | |
1140 | (color ball) | |
1141 | (owner ball))) | |
1142 | ball-color)) | |
1143 | (define (color ball) (struct-ref (struct-vtable ball) vtable-offset-user)) | |
1144 | (define (owner ball) (struct-ref ball 0)) | |
1145 | ||
1146 | (define red (make-ball-type 'red)) | |
1147 | (define green (make-ball-type 'green)) | |
1148 | ||
1149 | (define (make-ball type owner) (make-struct type 0 owner)) | |
1150 | ||
1151 | (define ball (make-ball green 'Nisse)) | |
1152 | ball @result{} #<a green ball owned by Nisse> | |
1153 | @end lisp | |
1154 | @end deffn | |
1155 | ||
1156 | @deffn {Scheme Procedure} struct-vtable-name vtable | |
1157 | @deffnx {C Function} scm_struct_vtable_name (vtable) | |
1158 | Return the name of the vtable @var{vtable}. | |
1159 | @end deffn | |
1160 | ||
1161 | @deffn {Scheme Procedure} set-struct-vtable-name! vtable name | |
1162 | @deffnx {C Function} scm_set_struct_vtable_name_x (vtable, name) | |
1163 | Set the name of the vtable @var{vtable} to @var{name}. | |
1164 | @end deffn | |
1165 | ||
1166 | @deffn {Scheme Procedure} struct-vtable-tag handle | |
1167 | @deffnx {C Function} scm_struct_vtable_tag (handle) | |
1168 | Return the vtable tag of the structure @var{handle}. | |
1169 | @end deffn | |
1170 | ||
1171 | ||
1172 | @node Arrays | |
1173 | @section Arrays | |
1174 | @tpindex Arrays | |
1175 | ||
1176 | @menu | |
1177 | * Conventional Arrays:: Arrays with arbitrary data. | |
1178 | * Array Mapping:: Applying a procedure to the contents of an array. | |
1179 | * Uniform Arrays:: Arrays with data of a single type. | |
1180 | * Bit Vectors:: Vectors of bits. | |
1181 | @end menu | |
1182 | ||
1183 | @node Conventional Arrays | |
1184 | @subsection Conventional Arrays | |
1185 | ||
1186 | @dfn{Conventional arrays} are a collection of cells organized into an | |
1187 | arbitrary number of dimensions. Each cell can hold any kind of Scheme | |
1188 | value and can be accessed in constant time by supplying an index for | |
1189 | each dimension. This contrasts with uniform arrays, which use memory | |
1190 | more efficiently but can hold data of only a single type, and lists | |
1191 | where inserting and deleting cells is more efficient, but more time | |
1192 | is usually required to access a particular cell. | |
1193 | ||
1194 | A conventional array is displayed as @code{#} followed by the @dfn{rank} | |
1195 | (number of dimensions) followed by the cells, organized into dimensions | |
1196 | using parentheses. The nesting depth of the parentheses is equal to | |
1197 | the rank. | |
1198 | ||
1199 | When an array is created, the number of dimensions and range of each | |
1200 | dimension must be specified, e.g., to create a 2x3 array with a | |
1201 | zero-based index: | |
1202 | ||
1203 | @example | |
1204 | (make-array 'ho 2 3) @result{} | |
1205 | #2((ho ho ho) (ho ho ho)) | |
1206 | @end example | |
1207 | ||
1208 | The range of each dimension can also be given explicitly, e.g., another | |
1209 | way to create the same array: | |
1210 | ||
1211 | @example | |
1212 | (make-array 'ho '(0 1) '(0 2)) @result{} | |
1213 | #2((ho ho ho) (ho ho ho)) | |
1214 | @end example | |
1215 | ||
1216 | A conventional array with one dimension based at zero is identical to | |
1217 | a vector: | |
1218 | ||
1219 | @example | |
1220 | (make-array 'ho 3) @result{} | |
1221 | #(ho ho ho) | |
1222 | @end example | |
1223 | ||
1224 | The following procedures can be used with conventional arrays (or vectors). | |
1225 | ||
1226 | @deffn {Scheme Procedure} array? v [prot] | |
1227 | @deffnx {C Function} scm_array_p (v, prot) | |
1228 | Return @code{#t} if the @var{obj} is an array, and @code{#f} if | |
1229 | not. The @var{prototype} argument is used with uniform arrays | |
1230 | and is described elsewhere. | |
1231 | @end deffn | |
1232 | ||
1233 | @deffn {Scheme Procedure} make-array initial-value bound1 bound2 @dots{} | |
1234 | Create and return an array that has as many dimensions as there are | |
1235 | @var{bound}s and fill it with @var{initial-value}. Each @var{bound} | |
1236 | may be a positive non-zero integer @var{N}, in which case the index for | |
1237 | that dimension can range from 0 through @var{N-1}; or an explicit index | |
1238 | range specifier in the form @code{(LOWER UPPER)}, where both @var{lower} | |
1239 | and @var{upper} are integers, possibly less than zero, and possibly the | |
1240 | same number (however, @var{lower} cannot be greater than @var{upper}). | |
1241 | @end deffn | |
1242 | ||
1243 | @c array-ref's type is `compiled-closure'. There's some weird stuff | |
1244 | @c going on in array.c, too. Let's call it a primitive. -twp | |
1245 | ||
1246 | @deffn {Scheme Procedure} uniform-vector-ref v args | |
1247 | @deffnx {Scheme Procedure} array-ref v . args | |
1248 | @deffnx {C Function} scm_uniform_vector_ref (v, args) | |
1249 | Return the element at the @code{(index1, index2)} element in | |
1250 | @var{array}. | |
1251 | @end deffn | |
1252 | ||
1253 | @deffn {Scheme Procedure} array-in-bounds? v . args | |
1254 | @deffnx {C Function} scm_array_in_bounds_p (v, args) | |
1255 | Return @code{#t} if its arguments would be acceptable to | |
1256 | @code{array-ref}. | |
1257 | @end deffn | |
1258 | ||
1259 | @c fixme: why do these sigs differ? -ttn 2001/07/19 01:14:12 | |
1260 | @deffn {Scheme Procedure} array-set! v obj . args | |
1261 | @deffnx {Scheme Procedure} uniform-array-set1! v obj args | |
1262 | @deffnx {C Function} scm_array_set_x (v, obj, args) | |
1263 | Set the element at the @code{(index1, index2)} element in @var{array} to | |
1264 | @var{new-value}. The value returned by array-set! is unspecified. | |
1265 | @end deffn | |
1266 | ||
1267 | @deffn {Scheme Procedure} make-shared-array oldra mapfunc . dims | |
1268 | @deffnx {C Function} scm_make_shared_array (oldra, mapfunc, dims) | |
1269 | @code{make-shared-array} can be used to create shared subarrays of other | |
1270 | arrays. The @var{mapper} is a function that translates coordinates in | |
1271 | the new array into coordinates in the old array. A @var{mapper} must be | |
1272 | linear, and its range must stay within the bounds of the old array, but | |
1273 | it can be otherwise arbitrary. A simple example: | |
1274 | @lisp | |
1275 | (define fred (make-array #f 8 8)) | |
1276 | (define freds-diagonal | |
1277 | (make-shared-array fred (lambda (i) (list i i)) 8)) | |
1278 | (array-set! freds-diagonal 'foo 3) | |
1279 | (array-ref fred 3 3) @result{} foo | |
1280 | (define freds-center | |
1281 | (make-shared-array fred (lambda (i j) (list (+ 3 i) (+ 3 j))) 2 2)) | |
1282 | (array-ref freds-center 0 0) @result{} foo | |
1283 | @end lisp | |
1284 | @end deffn | |
1285 | ||
1286 | @deffn {Scheme Procedure} shared-array-increments ra | |
1287 | @deffnx {C Function} scm_shared_array_increments (ra) | |
1288 | For each dimension, return the distance between elements in the root vector. | |
1289 | @end deffn | |
1290 | ||
1291 | @deffn {Scheme Procedure} shared-array-offset ra | |
1292 | @deffnx {C Function} scm_shared_array_offset (ra) | |
1293 | Return the root vector index of the first element in the array. | |
1294 | @end deffn | |
1295 | ||
1296 | @deffn {Scheme Procedure} shared-array-root ra | |
1297 | @deffnx {C Function} scm_shared_array_root (ra) | |
1298 | Return the root vector of a shared array. | |
1299 | @end deffn | |
1300 | ||
1301 | @deffn {Scheme Procedure} transpose-array ra . args | |
1302 | @deffnx {C Function} scm_transpose_array (ra, args) | |
1303 | Return an array sharing contents with @var{array}, but with | |
1304 | dimensions arranged in a different order. There must be one | |
1305 | @var{dim} argument for each dimension of @var{array}. | |
1306 | @var{dim0}, @var{dim1}, @dots{} should be integers between 0 | |
1307 | and the rank of the array to be returned. Each integer in that | |
1308 | range must appear at least once in the argument list. | |
1309 | ||
1310 | The values of @var{dim0}, @var{dim1}, @dots{} correspond to | |
1311 | dimensions in the array to be returned, their positions in the | |
1312 | argument list to dimensions of @var{array}. Several @var{dim}s | |
1313 | may have the same value, in which case the returned array will | |
1314 | have smaller rank than @var{array}. | |
1315 | ||
1316 | @lisp | |
1317 | (transpose-array '#2((a b) (c d)) 1 0) @result{} #2((a c) (b d)) | |
1318 | (transpose-array '#2((a b) (c d)) 0 0) @result{} #1(a d) | |
1319 | (transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) @result{} | |
1320 | #2((a 4) (b 5) (c 6)) | |
1321 | @end lisp | |
1322 | @end deffn | |
1323 | ||
1324 | @deffn {Scheme Procedure} enclose-array ra . axes | |
1325 | @deffnx {C Function} scm_enclose_array (ra, axes) | |
1326 | @var{dim0}, @var{dim1} @dots{} should be nonnegative integers less than | |
1327 | the rank of @var{array}. @var{enclose-array} returns an array | |
1328 | resembling an array of shared arrays. The dimensions of each shared | |
1329 | array are the same as the @var{dim}th dimensions of the original array, | |
1330 | the dimensions of the outer array are the same as those of the original | |
1331 | array that did not match a @var{dim}. | |
1332 | ||
1333 | An enclosed array is not a general Scheme array. Its elements may not | |
1334 | be set using @code{array-set!}. Two references to the same element of | |
1335 | an enclosed array will be @code{equal?} but will not in general be | |
1336 | @code{eq?}. The value returned by @var{array-prototype} when given an | |
1337 | enclosed array is unspecified. | |
1338 | ||
1339 | examples: | |
1340 | @lisp | |
1341 | (enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1) @result{} | |
1342 | #<enclosed-array (#1(a d) #1(b e) #1(c f)) (#1(1 4) #1(2 5) #1(3 6))> | |
1343 | ||
1344 | (enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 0) @result{} | |
1345 | #<enclosed-array #2((a 1) (d 4)) #2((b 2) (e 5)) #2((c 3) (f 6))> | |
1346 | @end lisp | |
1347 | @end deffn | |
1348 | ||
1349 | @deffn {Scheme Procedure} array-shape array | |
1350 | Return a list of inclusive bounds of integers. | |
1351 | @example | |
1352 | (array-shape (make-array 'foo '(-1 3) 5)) @result{} ((-1 3) (0 4)) | |
1353 | @end example | |
1354 | @end deffn | |
1355 | ||
1356 | @deffn {Scheme Procedure} array-dimensions ra | |
1357 | @deffnx {C Function} scm_array_dimensions (ra) | |
1358 | @code{Array-dimensions} is similar to @code{array-shape} but replaces | |
1359 | elements with a @code{0} minimum with one greater than the maximum. So: | |
1360 | @lisp | |
1361 | (array-dimensions (make-array 'foo '(-1 3) 5)) @result{} ((-1 3) 5) | |
1362 | @end lisp | |
1363 | @end deffn | |
1364 | ||
1365 | @deffn {Scheme Procedure} array-rank ra | |
1366 | @deffnx {C Function} scm_array_rank (ra) | |
1367 | Return the number of dimensions of @var{obj}. If @var{obj} is | |
1368 | not an array, @code{0} is returned. | |
1369 | @end deffn | |
1370 | ||
1371 | @deffn {Scheme Procedure} array->list v | |
21b83aab | 1372 | @deffnx {C Function} scm_array_to_list (v) |
4c731ece NJ |
1373 | Return a list consisting of all the elements, in order, of |
1374 | @var{array}. | |
1375 | @end deffn | |
1376 | ||
1377 | @deffn {Scheme Procedure} array-copy! src dst | |
1378 | @deffnx {Scheme Procedure} array-copy-in-order! src dst | |
1379 | @deffnx {C Function} scm_array_copy_x (src, dst) | |
1380 | Copy every element from vector or array @var{source} to the | |
1381 | corresponding element of @var{destination}. @var{destination} must have | |
1382 | the same rank as @var{source}, and be at least as large in each | |
1383 | dimension. The order is unspecified. | |
1384 | @end deffn | |
1385 | ||
1386 | @deffn {Scheme Procedure} array-fill! ra fill | |
1387 | @deffnx {C Function} scm_array_fill_x (ra, fill) | |
1388 | Store @var{fill} in every element of @var{array}. The value returned | |
1389 | is unspecified. | |
1390 | @end deffn | |
1391 | ||
1392 | @c begin (texi-doc-string "guile" "array-equal?") | |
1393 | @deffn {Scheme Procedure} array-equal? ra0 ra1 | |
1394 | Return @code{#t} iff all arguments are arrays with the same shape, the | |
1395 | same type, and have corresponding elements which are either | |
1396 | @code{equal?} or @code{array-equal?}. This function differs from | |
1397 | @code{equal?} in that a one dimensional shared array may be | |
1398 | @var{array-equal?} but not @var{equal?} to a vector or uniform vector. | |
1399 | @end deffn | |
1400 | ||
1401 | @deffn {Scheme Procedure} array-contents array [strict] | |
1402 | @deffnx {C Function} scm_array_contents (array, strict) | |
1403 | If @var{array} may be @dfn{unrolled} into a one dimensional shared array | |
1404 | without changing their order (last subscript changing fastest), then | |
1405 | @code{array-contents} returns that shared array, otherwise it returns | |
1406 | @code{#f}. All arrays made by @var{make-array} and | |
1407 | @var{make-uniform-array} may be unrolled, some arrays made by | |
1408 | @var{make-shared-array} may not be. | |
1409 | ||
1410 | If the optional argument @var{strict} is provided, a shared array will | |
1411 | be returned only if its elements are stored internally contiguous in | |
1412 | memory. | |
1413 | @end deffn | |
1414 | ||
1415 | @node Array Mapping | |
1416 | @subsection Array Mapping | |
1417 | ||
d23496c0 KR |
1418 | @c FIXME: array-map! accepts no source arrays at all, and in that |
1419 | @c case makes calls "(proc)". Is that meant to be a documented | |
1420 | @c feature? | |
1421 | @c | |
1422 | @c FIXME: array-for-each doesn't say what happens if the sources have | |
1423 | @c different index ranges. The code currently iterates over the | |
1424 | @c indices of the first and expects the others to cover those. That | |
1425 | @c at least vaguely matches array-map!, but is is meant to be a | |
1426 | @c documented feature? | |
1427 | ||
1428 | @deffn {Scheme Procedure} array-map! dst proc src1 @dots{} srcN | |
1429 | @deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN | |
1430 | @deffnx {C Function} scm_array_map_x (dst, proc, srclist) | |
1431 | Set each element of the @var{dst} array to values obtained from calls | |
1432 | to @var{proc}. The value returned is unspecified. | |
1433 | ||
1434 | Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})}, | |
1435 | where each @var{elem} is from the corresponding @var{src} array, at | |
1436 | the @var{dst} index. @code{array-map-in-order!} makes the calls in | |
1437 | row-major order, @code{array-map!} makes them in an unspecified order. | |
1438 | ||
1439 | The @var{src} arrays must have the same number of dimensions as | |
1440 | @var{dst}, and must have a range for each dimension which covers the | |
1441 | range in @var{dst}. This ensures all @var{dst} indices are valid in | |
1442 | each @var{src}. | |
1443 | @end deffn | |
1444 | ||
1445 | @deffn {Scheme Procedure} array-for-each proc src1 @dots{} srcN | |
1446 | @deffnx {C Function} scm_array_for_each (proc, src1, srclist) | |
1447 | Apply @var{proc} to each tuple of elements of @var{src1} @dots{} | |
1448 | @var{srcN}, in row-major order. The value returned is unspecified. | |
1449 | @end deffn | |
1450 | ||
1451 | @deffn {Scheme Procedure} array-index-map! dst proc | |
1452 | @deffnx {C Function} scm_array_index_map_x (dst, proc) | |
1453 | Set each element of the @var{dst} array to values returned by calls to | |
1454 | @var{proc}. The value returned is unspecified. | |
1455 | ||
1456 | Each call is @code{(@var{proc} @var{i1} @dots{} @var{iN})}, where | |
1457 | @var{i1}@dots{}@var{iN} is the destination index, one parameter for | |
1458 | each dimension. The order in which the calls are made is unspecified. | |
1459 | ||
1460 | For example, to create a @m{4\times4, 4x4} matrix representing a | |
1461 | cyclic group, | |
1462 | ||
1463 | @tex | |
1464 | \advance\leftskip by 2\lispnarrowing { | |
1465 | $\left(\matrix{% | |
1466 | 0 & 1 & 2 & 3 \cr | |
1467 | 1 & 2 & 3 & 0 \cr | |
1468 | 2 & 3 & 0 & 1 \cr | |
1469 | 3 & 0 & 1 & 2 \cr | |
1470 | }\right)$} \par | |
1471 | @end tex | |
1472 | @ifnottex | |
1473 | @example | |
1474 | / 0 1 2 3 \ | |
1475 | | 1 2 3 0 | | |
1476 | | 2 3 0 1 | | |
1477 | \ 3 0 1 2 / | |
1478 | @end example | |
1479 | @end ifnottex | |
1480 | ||
1481 | @example | |
1482 | (define a (make-array #f 4 4)) | |
1483 | (array-index-map! a (lambda (i j) | |
1484 | (modulo (+ i j) 4))) | |
1485 | @end example | |
4c731ece NJ |
1486 | @end deffn |
1487 | ||
1488 | @node Uniform Arrays | |
1489 | @subsection Uniform Arrays | |
1490 | @tpindex Uniform Arrays | |
1491 | ||
1492 | @noindent | |
1493 | @dfn{Uniform arrays} have elements all of the | |
1494 | same type and occupy less storage than conventional | |
1495 | arrays. Uniform arrays with a single zero-based dimension | |
1496 | are also known as @dfn{uniform vectors}. The procedures in | |
1497 | this section can also be used on conventional arrays, vectors, | |
1498 | bit-vectors and strings. | |
1499 | ||
1500 | @noindent | |
1501 | When creating a uniform array, the type of data to be stored | |
1502 | is indicated with a @var{prototype} argument. The following table | |
1503 | lists the types available and example prototypes: | |
1504 | ||
1505 | @example | |
1506 | prototype type printing character | |
1507 | ||
1508 | #t boolean (bit-vector) b | |
1509 | #\a char (string) a | |
1510 | #\nul byte (integer) y | |
1511 | 's short (integer) h | |
1512 | 1 unsigned long (integer) u | |
1513 | -1 signed long (integer) e | |
1514 | 'l signed long long (integer) l | |
1515 | 1.0 float (single precision) s | |
1516 | 1/3 double (double precision float) i | |
1517 | 0+i complex (double precision) c | |
1518 | () conventional vector | |
1519 | @end example | |
1520 | ||
1521 | @noindent | |
1522 | Unshared uniform arrays of characters with a single zero-based dimension | |
1523 | are identical to strings: | |
1524 | ||
1525 | @example | |
1526 | (make-uniform-array #\a 3) @result{} | |
1527 | "aaa" | |
1528 | @end example | |
1529 | ||
1530 | @noindent | |
1531 | Unshared uniform arrays of booleans with a single zero-based dimension | |
1532 | are identical to @ref{Bit Vectors, bit-vectors}. | |
1533 | ||
1534 | @example | |
1535 | (make-uniform-array #t 3) @result{} | |
1536 | #*111 | |
1537 | @end example | |
1538 | ||
1539 | @noindent | |
1540 | Other uniform vectors are written in a form similar to that of vectors, | |
1541 | except that a single character from the above table is put between | |
1542 | @code{#} and @code{(}. For example, a uniform vector of signed | |
1543 | long integers is displayed in the form @code{'#e(3 5 9)}. | |
1544 | ||
1545 | @deffn {Scheme Procedure} array? v [prot] | |
1546 | Return @code{#t} if the @var{obj} is an array, and @code{#f} if not. | |
1547 | ||
1548 | The @var{prototype} argument is used with uniform arrays and is described | |
1549 | elsewhere. | |
1550 | @end deffn | |
1551 | ||
1552 | @deffn {Scheme Procedure} make-uniform-array prototype bound1 bound2 @dots{} | |
1553 | Create and return a uniform array of type corresponding to | |
1554 | @var{prototype} that has as many dimensions as there are @var{bound}s | |
1555 | and fill it with @var{prototype}. | |
1556 | @end deffn | |
1557 | ||
1558 | @deffn {Scheme Procedure} array-prototype ra | |
1559 | @deffnx {C Function} scm_array_prototype (ra) | |
1560 | Return an object that would produce an array of the same type | |
1561 | as @var{array}, if used as the @var{prototype} for | |
1562 | @code{make-uniform-array}. | |
1563 | @end deffn | |
1564 | ||
1565 | @deffn {Scheme Procedure} list->uniform-array ndim prot lst | |
1566 | @deffnx {Scheme Procedure} list->uniform-vector prot lst | |
1567 | @deffnx {C Function} scm_list_to_uniform_array (ndim, prot, lst) | |
1568 | Return a uniform array of the type indicated by prototype | |
1569 | @var{prot} with elements the same as those of @var{lst}. | |
1570 | Elements must be of the appropriate type, no coercions are | |
1571 | done. | |
1572 | @end deffn | |
1573 | ||
1574 | @deffn {Scheme Procedure} uniform-vector-fill! uve fill | |
1575 | Store @var{fill} in every element of @var{uve}. The value returned is | |
1576 | unspecified. | |
1577 | @end deffn | |
1578 | ||
1579 | @deffn {Scheme Procedure} uniform-vector-length v | |
1580 | @deffnx {C Function} scm_uniform_vector_length (v) | |
1581 | Return the number of elements in @var{uve}. | |
1582 | @end deffn | |
1583 | ||
1584 | @deffn {Scheme Procedure} dimensions->uniform-array dims prot [fill] | |
1585 | @deffnx {Scheme Procedure} make-uniform-vector length prototype [fill] | |
1586 | @deffnx {C Function} scm_dimensions_to_uniform_array (dims, prot, fill) | |
1587 | Create and return a uniform array or vector of type | |
1588 | corresponding to @var{prototype} with dimensions @var{dims} or | |
1589 | length @var{length}. If @var{fill} is supplied, it's used to | |
1590 | fill the array, otherwise @var{prototype} is used. | |
1591 | @end deffn | |
1592 | ||
1593 | @c Another compiled-closure. -twp | |
1594 | ||
1595 | @deffn {Scheme Procedure} uniform-array-read! ra [port_or_fd [start [end]]] | |
1596 | @deffnx {Scheme Procedure} uniform-vector-read! uve [port-or-fdes] [start] [end] | |
1597 | @deffnx {C Function} scm_uniform_array_read_x (ra, port_or_fd, start, end) | |
1598 | Attempt to read all elements of @var{ura}, in lexicographic order, as | |
1599 | binary objects from @var{port-or-fdes}. | |
1600 | If an end of file is encountered, | |
1601 | the objects up to that point are put into @var{ura} | |
1602 | (starting at the beginning) and the remainder of the array is | |
1603 | unchanged. | |
1604 | ||
1605 | The optional arguments @var{start} and @var{end} allow | |
1606 | a specified region of a vector (or linearized array) to be read, | |
1607 | leaving the remainder of the vector unchanged. | |
1608 | ||
1609 | @code{uniform-array-read!} returns the number of objects read. | |
1610 | @var{port-or-fdes} may be omitted, in which case it defaults to the value | |
1611 | returned by @code{(current-input-port)}. | |
1612 | @end deffn | |
1613 | ||
1614 | @deffn {Scheme Procedure} uniform-array-write v [port_or_fd [start [end]]] | |
1615 | @deffnx {Scheme Procedure} uniform-vector-write uve [port-or-fdes] [start] [end] | |
1616 | @deffnx {C Function} scm_uniform_array_write (v, port_or_fd, start, end) | |
1617 | Writes all elements of @var{ura} as binary objects to | |
1618 | @var{port-or-fdes}. | |
1619 | ||
1620 | The optional arguments @var{start} | |
1621 | and @var{end} allow | |
1622 | a specified region of a vector (or linearized array) to be written. | |
1623 | ||
1624 | The number of objects actually written is returned. | |
1625 | @var{port-or-fdes} may be | |
1626 | omitted, in which case it defaults to the value returned by | |
1627 | @code{(current-output-port)}. | |
1628 | @end deffn | |
1629 | ||
1630 | @node Bit Vectors | |
1631 | @subsection Bit Vectors | |
1632 | ||
1633 | @noindent | |
1634 | Bit vectors are a specific type of uniform array: an array of booleans | |
1635 | with a single zero-based index. | |
1636 | ||
1637 | @noindent | |
1638 | They are displayed as a sequence of @code{0}s and | |
1639 | @code{1}s prefixed by @code{#*}, e.g., | |
1640 | ||
1641 | @example | |
1642 | (make-uniform-vector 8 #t #f) @result{} | |
1643 | #*00000000 | |
4c731ece NJ |
1644 | @end example |
1645 | ||
84bde77f KR |
1646 | @deffn {Scheme Procedure} bit-count bool bitvector |
1647 | @deffnx {C Function} scm_bit_count (bool, bitvector) | |
1648 | Return a count of how many entries in @var{bitvector} are equal to | |
1649 | @var{bool}. For example, | |
1650 | ||
1651 | @example | |
1652 | (bit-count #f #*000111000) @result{} 6 | |
1653 | @end example | |
4c731ece NJ |
1654 | @end deffn |
1655 | ||
84bde77f KR |
1656 | @deffn {Scheme Procedure} bit-position bool bitvector start |
1657 | @deffnx {C Function} scm_bit_position (bool, bitvector, start) | |
1658 | Return the index of the first occurrance of @var{bool} in | |
1659 | @var{bitvector}, starting from @var{start}. If there is no @var{bool} | |
1660 | entry between @var{start} and the end of @var{bitvector}, then return | |
1661 | @code{#f}. For example, | |
1662 | ||
1663 | @example | |
1664 | (bit-position #t #*000101 0) @result{} 3 | |
1665 | (bit-position #f #*0001111 3) @result{} #f | |
1666 | @end example | |
4c731ece NJ |
1667 | @end deffn |
1668 | ||
84bde77f KR |
1669 | @deffn {Scheme Procedure} bit-invert! bitvector |
1670 | @deffnx {C Function} scm_bit_invert_x (bitvector) | |
1671 | Modify @var{bitvector} by replacing each element with its negation. | |
4c731ece NJ |
1672 | @end deffn |
1673 | ||
84bde77f KR |
1674 | @deffn {Scheme Procedure} bit-set*! bitvector uvec bool |
1675 | @deffnx {C Function} scm_bit_set_star_x (bitvector, uvec, bool) | |
1676 | Set entries of @var{bitvector} to @var{bool}, with @var{uvec} | |
1677 | selecting the entries to change. | |
1678 | ||
1679 | If @var{uvec} is a bit vector, then those entries where it has | |
1680 | @code{#t} are the ones in @var{bitvector} which are set to @var{bool}. | |
1681 | When @var{bool} is @code{#t} it's like @var{uvec} is OR'ed into | |
1682 | @var{bitvector}. Or when @var{bool} is @code{#f} it can be seen as an | |
1683 | ANDNOT. | |
1684 | ||
1685 | @example | |
1686 | (define bv #*01000010) | |
1687 | (bit-set*! bv #*10010001 #t) | |
1688 | bv | |
1689 | @result{} #*11010011 | |
1690 | @end example | |
4c731ece | 1691 | |
84bde77f KR |
1692 | If @var{uvec} is a uniform vector of unsigned long integers, then |
1693 | they're indexes into @var{bitvector} which are set to @var{bool}. | |
1694 | ||
1695 | @example | |
1696 | (define bv #*01000010) | |
1697 | (bit-set*! bv #u(5 2 7) #t) | |
1698 | bv | |
1699 | @result{} #*01100111 | |
1700 | @end example | |
4c731ece NJ |
1701 | @end deffn |
1702 | ||
84bde77f KR |
1703 | @deffn {Scheme Procedure} bit-count* bitvector uvec bool |
1704 | @deffnx {C Function} scm_bit_count_star (bitvector, uvec, bool) | |
1705 | Return a count of how many entries in @var{bitvector} are equal to | |
1706 | @var{bool}, with @var{uvec} selecting the entries to consider. | |
1707 | ||
1708 | @var{uvec} is interpreted in the same way as for @code{bit-set*!} | |
1709 | above. Namely, if @var{uvec} is a bit vector then entries which have | |
1710 | @code{#t} there are considered in @var{bitvector}. Or if @var{uvec} | |
1711 | is a uniform vector of unsigned long integers then it's the indexes in | |
1712 | @var{bitvector} to consider. | |
1713 | ||
1714 | For example, | |
1715 | ||
1716 | @example | |
1717 | (bit-count* #*01110111 #*11001101 #t) @result{} 3 | |
1718 | (bit-count* #*01110111 #u(7 0 4) #f) @result{} 2 | |
1719 | @end example | |
4c731ece NJ |
1720 | @end deffn |
1721 | ||
1722 | ||
1723 | @node Association Lists and Hash Tables | |
1724 | @section Association Lists and Hash Tables | |
1725 | ||
1726 | This chapter discusses dictionary objects: data structures that are | |
1727 | useful for organizing and indexing large bodies of information. | |
1728 | ||
1729 | @menu | |
1730 | * Dictionary Types:: About dictionary types; what they're good for. | |
1731 | * Association Lists:: List-based dictionaries. | |
1732 | * Hash Tables:: Table-based dictionaries. | |
1733 | @end menu | |
1734 | ||
1735 | @node Dictionary Types | |
1736 | @subsection Dictionary Types | |
1737 | ||
1738 | A @dfn{dictionary} object is a data structure used to index | |
1739 | information in a user-defined way. In standard Scheme, the main | |
1740 | aggregate data types are lists and vectors. Lists are not really | |
1741 | indexed at all, and vectors are indexed only by number | |
1742 | (e.g. @code{(vector-ref foo 5)}). Often you will find it useful | |
1743 | to index your data on some other type; for example, in a library | |
1744 | catalog you might want to look up a book by the name of its | |
1745 | author. Dictionaries are used to help you organize information in | |
1746 | such a way. | |
1747 | ||
1748 | An @dfn{association list} (or @dfn{alist} for short) is a list of | |
1749 | key-value pairs. Each pair represents a single quantity or | |
1750 | object; the @code{car} of the pair is a key which is used to | |
1751 | identify the object, and the @code{cdr} is the object's value. | |
1752 | ||
1753 | A @dfn{hash table} also permits you to index objects with | |
1754 | arbitrary keys, but in a way that makes looking up any one object | |
1755 | extremely fast. A well-designed hash system makes hash table | |
1756 | lookups almost as fast as conventional array or vector references. | |
1757 | ||
1758 | Alists are popular among Lisp programmers because they use only | |
1759 | the language's primitive operations (lists, @dfn{car}, @dfn{cdr} | |
1760 | and the equality primitives). No changes to the language core are | |
1761 | necessary. Therefore, with Scheme's built-in list manipulation | |
1762 | facilities, it is very convenient to handle data stored in an | |
1763 | association list. Also, alists are highly portable and can be | |
1764 | easily implemented on even the most minimal Lisp systems. | |
1765 | ||
1766 | However, alists are inefficient, especially for storing large | |
1767 | quantities of data. Because we want Guile to be useful for large | |
1768 | software systems as well as small ones, Guile provides a rich set | |
1769 | of tools for using either association lists or hash tables. | |
1770 | ||
1771 | @node Association Lists | |
1772 | @subsection Association Lists | |
1773 | @tpindex Association Lists | |
1774 | @tpindex Alist | |
1775 | ||
1776 | @cindex Association List | |
1777 | @cindex Alist | |
1778 | @cindex Database | |
1779 | ||
1780 | An association list is a conventional data structure that is often used | |
1781 | to implement simple key-value databases. It consists of a list of | |
1782 | entries in which each entry is a pair. The @dfn{key} of each entry is | |
1783 | the @code{car} of the pair and the @dfn{value} of each entry is the | |
1784 | @code{cdr}. | |
1785 | ||
1786 | @example | |
1787 | ASSOCIATION LIST ::= '( (KEY1 . VALUE1) | |
1788 | (KEY2 . VALUE2) | |
1789 | (KEY3 . VALUE3) | |
1790 | @dots{} | |
1791 | ) | |
1792 | @end example | |
1793 | ||
1794 | @noindent | |
1795 | Association lists are also known, for short, as @dfn{alists}. | |
1796 | ||
1797 | The structure of an association list is just one example of the infinite | |
1798 | number of possible structures that can be built using pairs and lists. | |
1799 | As such, the keys and values in an association list can be manipulated | |
1800 | using the general list structure procedures @code{cons}, @code{car}, | |
1801 | @code{cdr}, @code{set-car!}, @code{set-cdr!} and so on. However, | |
1802 | because association lists are so useful, Guile also provides specific | |
1803 | procedures for manipulating them. | |
1804 | ||
1805 | @menu | |
801892e7 NJ |
1806 | * Alist Key Equality:: |
1807 | * Adding or Setting Alist Entries:: | |
1808 | * Retrieving Alist Entries:: | |
1809 | * Removing Alist Entries:: | |
1810 | * Sloppy Alist Functions:: | |
1811 | * Alist Example:: | |
4c731ece NJ |
1812 | @end menu |
1813 | ||
1814 | @node Alist Key Equality | |
1815 | @subsubsection Alist Key Equality | |
1816 | ||
1817 | All of Guile's dedicated association list procedures, apart from | |
801892e7 | 1818 | @code{acons}, come in three flavours, depending on the level of equality |
4c731ece NJ |
1819 | that is required to decide whether an existing key in the association |
1820 | list is the same as the key that the procedure call uses to identify the | |
1821 | required entry. | |
1822 | ||
1823 | @itemize @bullet | |
1824 | @item | |
1825 | Procedures with @dfn{assq} in their name use @code{eq?} to determine key | |
1826 | equality. | |
1827 | ||
1828 | @item | |
1829 | Procedures with @dfn{assv} in their name use @code{eqv?} to determine | |
1830 | key equality. | |
1831 | ||
1832 | @item | |
1833 | Procedures with @dfn{assoc} in their name use @code{equal?} to | |
1834 | determine key equality. | |
1835 | @end itemize | |
1836 | ||
1837 | @code{acons} is an exception because it is used to build association | |
1838 | lists which do not require their entries' keys to be unique. | |
1839 | ||
1840 | @node Adding or Setting Alist Entries | |
1841 | @subsubsection Adding or Setting Alist Entries | |
1842 | ||
1843 | @code{acons} adds a new entry to an association list and returns the | |
1844 | combined association list. The combined alist is formed by consing the | |
1845 | new entry onto the head of the alist specified in the @code{acons} | |
1846 | procedure call. So the specified alist is not modified, but its | |
1847 | contents become shared with the tail of the combined alist that | |
1848 | @code{acons} returns. | |
1849 | ||
1850 | In the most common usage of @code{acons}, a variable holding the | |
1851 | original association list is updated with the combined alist: | |
1852 | ||
1853 | @example | |
1854 | (set! address-list (acons name address address-list)) | |
1855 | @end example | |
1856 | ||
1857 | In such cases, it doesn't matter that the old and new values of | |
1858 | @code{address-list} share some of their contents, since the old value is | |
1859 | usually no longer independently accessible. | |
1860 | ||
1861 | Note that @code{acons} adds the specified new entry regardless of | |
1862 | whether the alist may already contain entries with keys that are, in | |
1863 | some sense, the same as that of the new entry. Thus @code{acons} is | |
1864 | ideal for building alists where there is no concept of key uniqueness. | |
1865 | ||
1866 | @example | |
1867 | (set! task-list (acons 3 "pay gas bill" '())) | |
1868 | task-list | |
1869 | @result{} | |
1870 | ((3 . "pay gas bill")) | |
1871 | ||
1872 | (set! task-list (acons 3 "tidy bedroom" task-list)) | |
1873 | task-list | |
1874 | @result{} | |
1875 | ((3 . "tidy bedroom") (3 . "pay gas bill")) | |
1876 | @end example | |
1877 | ||
1878 | @code{assq-set!}, @code{assv-set!} and @code{assoc-set!} are used to add | |
1879 | or replace an entry in an association list where there @emph{is} a | |
1880 | concept of key uniqueness. If the specified association list already | |
1881 | contains an entry whose key is the same as that specified in the | |
1882 | procedure call, the existing entry is replaced by the new one. | |
1883 | Otherwise, the new entry is consed onto the head of the old association | |
1884 | list to create the combined alist. In all cases, these procedures | |
1885 | return the combined alist. | |
1886 | ||
1887 | @code{assq-set!} and friends @emph{may} destructively modify the | |
1888 | structure of the old association list in such a way that an existing | |
1889 | variable is correctly updated without having to @code{set!} it to the | |
1890 | value returned: | |
1891 | ||
1892 | @example | |
1893 | address-list | |
1894 | @result{} | |
1895 | (("mary" . "34 Elm Road") ("james" . "16 Bow Street")) | |
1896 | ||
1897 | (assoc-set! address-list "james" "1a London Road") | |
1898 | @result{} | |
1899 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
1900 | ||
1901 | address-list | |
1902 | @result{} | |
1903 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
1904 | @end example | |
1905 | ||
1906 | Or they may not: | |
1907 | ||
1908 | @example | |
1909 | (assoc-set! address-list "bob" "11 Newington Avenue") | |
1910 | @result{} | |
1911 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
1912 | ("james" . "1a London Road")) | |
1913 | ||
1914 | address-list | |
1915 | @result{} | |
1916 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
1917 | @end example | |
1918 | ||
1919 | The only safe way to update an association list variable when adding or | |
1920 | replacing an entry like this is to @code{set!} the variable to the | |
1921 | returned value: | |
1922 | ||
1923 | @example | |
1924 | (set! address-list | |
1925 | (assoc-set! address-list "bob" "11 Newington Avenue")) | |
1926 | address-list | |
1927 | @result{} | |
1928 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
1929 | ("james" . "1a London Road")) | |
1930 | @end example | |
1931 | ||
1932 | Because of this slight inconvenience, you may find it more convenient to | |
1933 | use hash tables to store dictionary data. If your application will not | |
1934 | be modifying the contents of an alist very often, this may not make much | |
1935 | difference to you. | |
1936 | ||
1937 | If you need to keep the old value of an association list in a form | |
1938 | independent from the list that results from modification by | |
1939 | @code{acons}, @code{assq-set!}, @code{assv-set!} or @code{assoc-set!}, | |
1940 | use @code{list-copy} to copy the old association list before modifying | |
1941 | it. | |
1942 | ||
1943 | @deffn {Scheme Procedure} acons key value alist | |
1944 | @deffnx {C Function} scm_acons (key, value, alist) | |
1945 | Add a new key-value pair to @var{alist}. A new pair is | |
1946 | created whose car is @var{key} and whose cdr is @var{value}, and the | |
1947 | pair is consed onto @var{alist}, and the new list is returned. This | |
1948 | function is @emph{not} destructive; @var{alist} is not modified. | |
1949 | @end deffn | |
1950 | ||
1951 | @deffn {Scheme Procedure} assq-set! alist key val | |
1952 | @deffnx {Scheme Procedure} assv-set! alist key value | |
1953 | @deffnx {Scheme Procedure} assoc-set! alist key value | |
1954 | @deffnx {C Function} scm_assq_set_x (alist, key, val) | |
1955 | @deffnx {C Function} scm_assv_set_x (alist, key, val) | |
1956 | @deffnx {C Function} scm_assoc_set_x (alist, key, val) | |
801892e7 | 1957 | Reassociate @var{key} in @var{alist} with @var{value}: find any existing |
4c731ece NJ |
1958 | @var{alist} entry for @var{key} and associate it with the new |
1959 | @var{value}. If @var{alist} does not contain an entry for @var{key}, | |
1960 | add a new one. Return the (possibly new) alist. | |
1961 | ||
1962 | These functions do not attempt to verify the structure of @var{alist}, | |
1963 | and so may cause unusual results if passed an object that is not an | |
1964 | association list. | |
1965 | @end deffn | |
1966 | ||
1967 | @node Retrieving Alist Entries | |
1968 | @subsubsection Retrieving Alist Entries | |
1969 | @rnindex assq | |
1970 | @rnindex assv | |
1971 | @rnindex assoc | |
1972 | ||
1973 | @code{assq}, @code{assv} and @code{assoc} take an alist and a key as | |
1974 | arguments and return the entry for that key if an entry exists, or | |
1975 | @code{#f} if there is no entry for that key. Note that, in the cases | |
1976 | where an entry exists, these procedures return the complete entry, that | |
1977 | is @code{(KEY . VALUE)}, not just the value. | |
1978 | ||
1979 | @deffn {Scheme Procedure} assq key alist | |
1980 | @deffnx {Scheme Procedure} assv key alist | |
1981 | @deffnx {Scheme Procedure} assoc key alist | |
1982 | @deffnx {C Function} scm_assq (key, alist) | |
1983 | @deffnx {C Function} scm_assv (key, alist) | |
1984 | @deffnx {C Function} scm_assoc (key, alist) | |
1985 | Fetch the entry in @var{alist} that is associated with @var{key}. To | |
1986 | decide whether the argument @var{key} matches a particular entry in | |
1987 | @var{alist}, @code{assq} compares keys with @code{eq?}, @code{assv} | |
1988 | uses @code{eqv?} and @code{assoc} uses @code{equal?}. If @var{key} | |
1989 | cannot be found in @var{alist} (according to whichever equality | |
1990 | predicate is in use), then return @code{#f}. These functions | |
1991 | return the entire alist entry found (i.e. both the key and the value). | |
1992 | @end deffn | |
1993 | ||
1994 | @code{assq-ref}, @code{assv-ref} and @code{assoc-ref}, on the other | |
1995 | hand, take an alist and a key and return @emph{just the value} for that | |
1996 | key, if an entry exists. If there is no entry for the specified key, | |
1997 | these procedures return @code{#f}. | |
1998 | ||
1999 | This creates an ambiguity: if the return value is @code{#f}, it means | |
2000 | either that there is no entry with the specified key, or that there | |
2001 | @emph{is} an entry for the specified key, with value @code{#f}. | |
2002 | Consequently, @code{assq-ref} and friends should only be used where it | |
2003 | is known that an entry exists, or where the ambiguity doesn't matter | |
2004 | for some other reason. | |
2005 | ||
2006 | @deffn {Scheme Procedure} assq-ref alist key | |
2007 | @deffnx {Scheme Procedure} assv-ref alist key | |
2008 | @deffnx {Scheme Procedure} assoc-ref alist key | |
2009 | @deffnx {C Function} scm_assq_ref (alist, key) | |
2010 | @deffnx {C Function} scm_assv_ref (alist, key) | |
2011 | @deffnx {C Function} scm_assoc_ref (alist, key) | |
2012 | Like @code{assq}, @code{assv} and @code{assoc}, except that only the | |
2013 | value associated with @var{key} in @var{alist} is returned. These | |
2014 | functions are equivalent to | |
2015 | ||
2016 | @lisp | |
2017 | (let ((ent (@var{associator} @var{key} @var{alist}))) | |
2018 | (and ent (cdr ent))) | |
2019 | @end lisp | |
2020 | ||
2021 | where @var{associator} is one of @code{assq}, @code{assv} or @code{assoc}. | |
2022 | @end deffn | |
2023 | ||
2024 | @node Removing Alist Entries | |
2025 | @subsubsection Removing Alist Entries | |
2026 | ||
2027 | To remove the element from an association list whose key matches a | |
2028 | specified key, use @code{assq-remove!}, @code{assv-remove!} or | |
2029 | @code{assoc-remove!} (depending, as usual, on the level of equality | |
2030 | required between the key that you specify and the keys in the | |
2031 | association list). | |
2032 | ||
2033 | As with @code{assq-set!} and friends, the specified alist may or may not | |
2034 | be modified destructively, and the only safe way to update a variable | |
2035 | containing the alist is to @code{set!} it to the value that | |
2036 | @code{assq-remove!} and friends return. | |
2037 | ||
2038 | @example | |
2039 | address-list | |
2040 | @result{} | |
2041 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
2042 | ("james" . "1a London Road")) | |
2043 | ||
2044 | (set! address-list (assoc-remove! address-list "mary")) | |
2045 | address-list | |
2046 | @result{} | |
2047 | (("bob" . "11 Newington Avenue") ("james" . "1a London Road")) | |
2048 | @end example | |
2049 | ||
2050 | Note that, when @code{assq/v/oc-remove!} is used to modify an | |
2051 | association list that has been constructed only using the corresponding | |
2052 | @code{assq/v/oc-set!}, there can be at most one matching entry in the | |
2053 | alist, so the question of multiple entries being removed in one go does | |
2054 | not arise. If @code{assq/v/oc-remove!} is applied to an association | |
2055 | list that has been constructed using @code{acons}, or an | |
2056 | @code{assq/v/oc-set!} with a different level of equality, or any mixture | |
2057 | of these, it removes only the first matching entry from the alist, even | |
2058 | if the alist might contain further matching entries. For example: | |
2059 | ||
2060 | @example | |
2061 | (define address-list '()) | |
2062 | (set! address-list (assq-set! address-list "mary" "11 Elm Street")) | |
2063 | (set! address-list (assq-set! address-list "mary" "57 Pine Drive")) | |
2064 | address-list | |
2065 | @result{} | |
2066 | (("mary" . "57 Pine Drive") ("mary" . "11 Elm Street")) | |
2067 | ||
2068 | (set! address-list (assoc-remove! address-list "mary")) | |
2069 | address-list | |
2070 | @result{} | |
2071 | (("mary" . "11 Elm Street")) | |
2072 | @end example | |
2073 | ||
2074 | In this example, the two instances of the string "mary" are not the same | |
2075 | when compared using @code{eq?}, so the two @code{assq-set!} calls add | |
2076 | two distinct entries to @code{address-list}. When compared using | |
2077 | @code{equal?}, both "mary"s in @code{address-list} are the same as the | |
2078 | "mary" in the @code{assoc-remove!} call, but @code{assoc-remove!} stops | |
2079 | after removing the first matching entry that it finds, and so one of the | |
2080 | "mary" entries is left in place. | |
2081 | ||
2082 | @deffn {Scheme Procedure} assq-remove! alist key | |
2083 | @deffnx {Scheme Procedure} assv-remove! alist key | |
2084 | @deffnx {Scheme Procedure} assoc-remove! alist key | |
2085 | @deffnx {C Function} scm_assq_remove_x (alist, key) | |
2086 | @deffnx {C Function} scm_assv_remove_x (alist, key) | |
2087 | @deffnx {C Function} scm_assoc_remove_x (alist, key) | |
2088 | Delete the first entry in @var{alist} associated with @var{key}, and return | |
2089 | the resulting alist. | |
2090 | @end deffn | |
2091 | ||
2092 | @node Sloppy Alist Functions | |
2093 | @subsubsection Sloppy Alist Functions | |
2094 | ||
2095 | @code{sloppy-assq}, @code{sloppy-assv} and @code{sloppy-assoc} behave | |
2096 | like the corresponding non-@code{sloppy-} procedures, except that they | |
2097 | return @code{#f} when the specified association list is not well-formed, | |
2098 | where the non-@code{sloppy-} versions would signal an error. | |
2099 | ||
2100 | Specifically, there are two conditions for which the non-@code{sloppy-} | |
2101 | procedures signal an error, which the @code{sloppy-} procedures handle | |
2102 | instead by returning @code{#f}. Firstly, if the specified alist as a | |
2103 | whole is not a proper list: | |
2104 | ||
2105 | @example | |
2106 | (assoc "mary" '((1 . 2) ("key" . "door") . "open sesame")) | |
2107 | @result{} | |
2108 | ERROR: In procedure assoc in expression (assoc "mary" (quote #)): | |
2109 | ERROR: Wrong type argument in position 2 (expecting NULLP): "open sesame" | |
2110 | ABORT: (wrong-type-arg) | |
2111 | ||
2112 | (sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame")) | |
2113 | @result{} | |
2114 | #f | |
2115 | @end example | |
2116 | ||
2117 | @noindent | |
2118 | Secondly, if one of the entries in the specified alist is not a pair: | |
2119 | ||
2120 | @example | |
2121 | (assoc 2 '((1 . 1) 2 (3 . 9))) | |
2122 | @result{} | |
2123 | ERROR: In procedure assoc in expression (assoc 2 (quote #)): | |
2124 | ERROR: Wrong type argument in position 2 (expecting CONSP): 2 | |
2125 | ABORT: (wrong-type-arg) | |
2126 | ||
2127 | (sloppy-assoc 2 '((1 . 1) 2 (3 . 9))) | |
2128 | @result{} | |
2129 | #f | |
2130 | @end example | |
2131 | ||
2132 | Unless you are explicitly working with badly formed association lists, | |
2133 | it is much safer to use the non-@code{sloppy-} procedures, because they | |
2134 | help to highlight coding and data errors that the @code{sloppy-} | |
2135 | versions would silently cover up. | |
2136 | ||
2137 | @deffn {Scheme Procedure} sloppy-assq key alist | |
2138 | @deffnx {C Function} scm_sloppy_assq (key, alist) | |
2139 | Behaves like @code{assq} but does not do any error checking. | |
2140 | Recommended only for use in Guile internals. | |
2141 | @end deffn | |
2142 | ||
2143 | @deffn {Scheme Procedure} sloppy-assv key alist | |
2144 | @deffnx {C Function} scm_sloppy_assv (key, alist) | |
2145 | Behaves like @code{assv} but does not do any error checking. | |
2146 | Recommended only for use in Guile internals. | |
2147 | @end deffn | |
2148 | ||
2149 | @deffn {Scheme Procedure} sloppy-assoc key alist | |
2150 | @deffnx {C Function} scm_sloppy_assoc (key, alist) | |
2151 | Behaves like @code{assoc} but does not do any error checking. | |
2152 | Recommended only for use in Guile internals. | |
2153 | @end deffn | |
2154 | ||
2155 | @node Alist Example | |
2156 | @subsubsection Alist Example | |
2157 | ||
2158 | Here is a longer example of how alists may be used in practice. | |
2159 | ||
2160 | @lisp | |
2161 | (define capitals '(("New York" . "Albany") | |
2162 | ("Oregon" . "Salem") | |
2163 | ("Florida" . "Miami"))) | |
2164 | ||
2165 | ;; What's the capital of Oregon? | |
2166 | (assoc "Oregon" capitals) @result{} ("Oregon" . "Salem") | |
2167 | (assoc-ref capitals "Oregon") @result{} "Salem" | |
2168 | ||
2169 | ;; We left out South Dakota. | |
2170 | (set! capitals | |
5ad5a7b6 | 2171 | (assoc-set! capitals "South Dakota" "Pierre")) |
4c731ece | 2172 | capitals |
5ad5a7b6 | 2173 | @result{} (("South Dakota" . "Pierre") |
4c731ece NJ |
2174 | ("New York" . "Albany") |
2175 | ("Oregon" . "Salem") | |
2176 | ("Florida" . "Miami")) | |
2177 | ||
2178 | ;; And we got Florida wrong. | |
2179 | (set! capitals | |
2180 | (assoc-set! capitals "Florida" "Tallahassee")) | |
2181 | capitals | |
5ad5a7b6 | 2182 | @result{} (("South Dakota" . "Pierre") |
4c731ece NJ |
2183 | ("New York" . "Albany") |
2184 | ("Oregon" . "Salem") | |
2185 | ("Florida" . "Tallahassee")) | |
2186 | ||
2187 | ;; After Oregon secedes, we can remove it. | |
2188 | (set! capitals | |
2189 | (assoc-remove! capitals "Oregon")) | |
2190 | capitals | |
5ad5a7b6 | 2191 | @result{} (("South Dakota" . "Pierre") |
4c731ece NJ |
2192 | ("New York" . "Albany") |
2193 | ("Florida" . "Tallahassee")) | |
2194 | @end lisp | |
2195 | ||
2196 | @node Hash Tables | |
2197 | @subsection Hash Tables | |
2198 | @tpindex Hash Tables | |
2199 | ||
2200 | @c FIXME::martin: Review me! | |
2201 | ||
2202 | Hash tables are dictionaries which offer similar functionality as | |
2203 | association lists: They provide a mapping from keys to values. The | |
2204 | difference is that association lists need time linear in the size of | |
2205 | elements when searching for entries, whereas hash tables can normally | |
2206 | search in constant time. The drawback is that hash tables require a | |
2207 | little bit more memory, and that you can not use the normal list | |
2208 | procedures (@pxref{Lists}) for working with them. | |
2209 | ||
2210 | @menu | |
2211 | * Hash Table Examples:: Demonstration of hash table usage. | |
2212 | * Hash Table Reference:: Hash table procedure descriptions. | |
2213 | @end menu | |
2214 | ||
2215 | ||
2216 | @node Hash Table Examples | |
2217 | @subsubsection Hash Table Examples | |
2218 | ||
2219 | @c FIXME::martin: Review me! | |
2220 | ||
2221 | For demonstration purposes, this section gives a few usage examples of | |
2222 | some hash table procedures, together with some explanation what they do. | |
2223 | ||
2224 | First we start by creating a new hash table with 31 slots, and | |
2225 | populate it with two key/value pairs. | |
2226 | ||
2227 | @lisp | |
2228 | (define h (make-hash-table 31)) | |
2229 | ||
2230 | (hashq-create-handle! h 'foo "bar") | |
2231 | @result{} | |
2232 | (foo . "bar") | |
2233 | ||
2234 | (hashq-create-handle! h 'braz "zonk") | |
2235 | @result{} | |
2236 | (braz . "zonk") | |
2237 | ||
2238 | (hashq-create-handle! h 'frob #f) | |
2239 | @result{} | |
2240 | (frob . #f) | |
2241 | @end lisp | |
2242 | ||
2243 | You can get the value for a given key with the procedure | |
2244 | @code{hashq-ref}, but the problem with this procedure is that you | |
2245 | cannot reliably determine whether a key does exists in the table. The | |
2246 | reason is that the procedure returns @code{#f} if the key is not in | |
2247 | the table, but it will return the same value if the key is in the | |
2248 | table and just happens to have the value @code{#f}, as you can see in | |
2249 | the following examples. | |
2250 | ||
2251 | @lisp | |
2252 | (hashq-ref h 'foo) | |
2253 | @result{} | |
2254 | "bar" | |
2255 | ||
2256 | (hashq-ref h 'frob) | |
2257 | @result{} | |
2258 | #f | |
2259 | ||
2260 | (hashq-ref h 'not-there) | |
2261 | @result{} | |
2262 | #f | |
2263 | @end lisp | |
2264 | ||
2265 | Better is to use the procedure @code{hashq-get-handle}, which makes a | |
2266 | distinction between the two cases. Just like @code{assq}, this | |
2267 | procedure returns a key/value-pair on success, and @code{#f} if the | |
2268 | key is not found. | |
2269 | ||
2270 | @lisp | |
2271 | (hashq-get-handle h 'foo) | |
2272 | @result{} | |
2273 | (foo . "bar") | |
2274 | ||
2275 | (hashq-get-handle h 'not-there) | |
2276 | @result{} | |
2277 | #f | |
2278 | @end lisp | |
2279 | ||
2280 | There is no procedure for calculating the number of key/value-pairs in | |
2281 | a hash table, but @code{hash-fold} can be used for doing exactly that. | |
2282 | ||
2283 | @lisp | |
2284 | (hash-fold (lambda (key value seed) (+ 1 seed)) 0 h) | |
2285 | @result{} | |
2286 | 3 | |
2287 | @end lisp | |
2288 | ||
2289 | @node Hash Table Reference | |
2290 | @subsubsection Hash Table Reference | |
2291 | ||
ac5fa6d1 KR |
2292 | @c FIXME: Describe in broad terms what happens for resizing, and what |
2293 | @c the initial size means for this. | |
2294 | ||
2295 | Like the association list functions, the hash table functions come in | |
2296 | several varieties, according to the equality test used for the keys. | |
2297 | Plain @code{hash-} functions use @code{equal?}, @code{hashq-} | |
2298 | functions use @code{eq?}, @code{hashv-} functions use @code{eqv?}, and | |
3adbc48c | 2299 | the @code{hashx-} functions use an application supplied test. |
ac5fa6d1 KR |
2300 | |
2301 | A single @code{make-hash-table} creates a hash table suitable for use | |
2302 | with any set of functions, but it's imperative that just one set is | |
2303 | then used consistently, or results will be unpredictable. | |
2304 | ||
2305 | @sp 1 | |
ea2b9c2f | 2306 | Hash tables are implemented as a vector indexed by a hash value formed |
ac5fa6d1 KR |
2307 | from the key, with an association list of key/value pairs for each |
2308 | bucket in case distinct keys hash together. Direct access to the | |
2309 | pairs in those lists is provided by the @code{-handle-} functions. | |
2310 | ||
ea2b9c2f KR |
2311 | When the number of table entries goes above a threshold the vector is |
2312 | increased and the entries rehashed, to prevent the bucket lists | |
2313 | becoming too long and slowing down accesses. When the number of | |
2314 | entries goes below a threshold the vector is decreased to save space. | |
2315 | ||
2316 | @sp 1 | |
ac5fa6d1 | 2317 | For the @code{hashx-} ``extended'' routines, an application supplies a |
3adbc48c KR |
2318 | @var{hash} function producing an integer index like @code{hashq} etc |
2319 | below, and an @var{assoc} alist search function like @code{assq} etc | |
2320 | (@pxref{Retrieving Alist Entries}). Here's an example of such | |
2321 | functions implementing case-insensitive hashing of string keys, | |
2322 | ||
2323 | @example | |
2324 | (use-modules (srfi srfi-1) | |
2325 | (srfi srfi-13)) | |
ea2b9c2f | 2326 | |
3adbc48c KR |
2327 | (define (my-hash str size) |
2328 | (remainder (string-hash-ci str) size)) | |
2329 | (define (my-assoc str alist) | |
2330 | (find (lambda (pair) (string-ci=? str (car pair))) alist)) | |
2331 | ||
2332 | (define my-table (make-hash-table)) | |
2333 | (hashx-set! my-hash my-assoc my-table "foo" 123) | |
2334 | ||
2335 | (hashx-ref my-hash my-assoc my-table "FOO") | |
2336 | @result{} 123 | |
2337 | @end example | |
2338 | ||
2339 | In a @code{hashx-} @var{hash} function the aim is to spread keys | |
ea2b9c2f KR |
2340 | across the vector, so bucket lists don't become long. But the actual |
2341 | values are arbitrary as long as they're in the range 0 to | |
2342 | @math{@var{size}-1}. Helpful functions for forming a hash value, in | |
3adbc48c KR |
2343 | addition to @code{hashq} etc below, include @code{symbol-hash} |
2344 | (@pxref{Symbol Keys}), @code{string-hash} and @code{string-hash-ci} | |
2345 | (@pxref{SRFI-13 Comparison}), and @code{char-set-hash} (@pxref{SRFI-14 | |
2346 | Predicates/Comparison}). | |
ac5fa6d1 | 2347 | |
ea2b9c2f KR |
2348 | Note that currently, unfortunately, there's no @code{hashx-remove!} |
2349 | function, which rather limits the usefulness of the @code{hashx-} | |
2350 | routines. | |
2351 | ||
ac5fa6d1 KR |
2352 | @sp 1 |
2353 | @deffn {Scheme Procedure} make-hash-table [size] | |
ea2b9c2f | 2354 | Create a new hash table, with an optional minimum vector @var{size}. |
ac5fa6d1 | 2355 | |
ea2b9c2f KR |
2356 | When @var{size} is given, the table vector will still grow and shrink |
2357 | automatically, as described above, but with @var{size} as a minimum. | |
2358 | If an application knows roughly how many entries the table will hold | |
2359 | then it can use @var{size} to avoid rehashing when initial entries are | |
2360 | added. | |
4c731ece NJ |
2361 | @end deffn |
2362 | ||
2363 | @deffn {Scheme Procedure} hash-ref table key [dflt] | |
ac5fa6d1 KR |
2364 | @deffnx {Scheme Procedure} hashq-ref table key [dflt] |
2365 | @deffnx {Scheme Procedure} hashv-ref table key [dflt] | |
2366 | @deffnx {Scheme Procedure} hashx-ref hash assoc table key [dflt] | |
4c731ece | 2367 | @deffnx {C Function} scm_hash_ref (table, key, dflt) |
ac5fa6d1 KR |
2368 | @deffnx {C Function} scm_hashq_ref (table, key, dflt) |
2369 | @deffnx {C Function} scm_hashv_ref (table, key, dflt) | |
2370 | @deffnx {C Function} scm_hashx_ref (hash, assoc, table, key, dflt) | |
2371 | Lookup @var{key} in the given hash @var{table}, and return the | |
2372 | associated value. If @var{key} is not found, return @var{dflt}, or | |
2373 | @code{#f} if @var{dflt} is not given. (For the C functions, | |
2374 | @var{dflt} must be given.) | |
4c731ece NJ |
2375 | @end deffn |
2376 | ||
2377 | @deffn {Scheme Procedure} hash-set! table key val | |
ac5fa6d1 KR |
2378 | @deffnx {Scheme Procedure} hashq-set! table key val |
2379 | @deffnx {Scheme Procedure} hashv-set! table key val | |
2380 | @deffnx {Scheme Procedure} hashx-set! hash assoc table key val | |
4c731ece | 2381 | @deffnx {C Function} scm_hash_set_x (table, key, val) |
ac5fa6d1 KR |
2382 | @deffnx {C Function} scm_hashq_set_x (table, key, val) |
2383 | @deffnx {C Function} scm_hashv_set_x (table, key, val) | |
2384 | @deffnx {C Function} scm_hashx_set_x (hash, assoc, table, key, val) | |
2385 | Associate @var{val} with @var{key} in the given hash @var{table}. If | |
2386 | @var{key} is already present then it's associated value is changed. | |
2387 | If it's not present then a new entry is created. | |
4c731ece NJ |
2388 | @end deffn |
2389 | ||
2390 | @deffn {Scheme Procedure} hash-remove! table key | |
ac5fa6d1 KR |
2391 | @deffnx {Scheme Procedure} hashq-remove! table key |
2392 | @deffnx {Scheme Procedure} hashv-remove! table key | |
4c731ece | 2393 | @deffnx {C Function} scm_hash_remove_x (table, key) |
ac5fa6d1 KR |
2394 | @deffnx {C Function} scm_hashq_remove_x (table, key) |
2395 | @deffnx {C Function} scm_hashv_remove_x (table, key) | |
2396 | Remove any association for @var{key} in the given hash @var{table}. | |
2397 | If @var{key} is not in @var{table} then nothing is done. | |
4c731ece NJ |
2398 | @end deffn |
2399 | ||
2400 | @deffn {Scheme Procedure} hash key size | |
ac5fa6d1 KR |
2401 | @deffnx {Scheme Procedure} hashq key size |
2402 | @deffnx {Scheme Procedure} hashv key size | |
4c731ece | 2403 | @deffnx {C Function} scm_hash (key, size) |
ac5fa6d1 KR |
2404 | @deffnx {C Function} scm_hashq (key, size) |
2405 | @deffnx {C Function} scm_hashv (key, size) | |
2406 | Return a hash value for @var{key}. This is a number in the range | |
2407 | @math{0} to @math{@var{size}-1}, which is suitable for use in a hash | |
2408 | table of the given @var{size}. | |
4c731ece | 2409 | |
ac5fa6d1 KR |
2410 | Note that @code{hashq} and @code{hashv} may use internal addresses of |
2411 | objects, so if an object is garbage collected and re-created it can | |
2412 | have a different hash value, even when the two are notionally | |
2413 | @code{eq?}. For instance with symbols, | |
4c731ece | 2414 | |
ac5fa6d1 KR |
2415 | @example |
2416 | (hashq 'something 123) @result{} 19 | |
2417 | (gc) | |
2418 | (hashq 'something 123) @result{} 62 | |
2419 | @end example | |
4c731ece | 2420 | |
ac5fa6d1 KR |
2421 | In normal use this is not a problem, since an object entered into a |
2422 | hash table won't be garbage collected until removed. It's only if | |
2423 | hashing calculations are somehow separated from normal references that | |
2424 | its lifetime needs to be considered. | |
4c731ece NJ |
2425 | @end deffn |
2426 | ||
2427 | @deffn {Scheme Procedure} hash-get-handle table key | |
ac5fa6d1 KR |
2428 | @deffnx {Scheme Procedure} hashq-get-handle table key |
2429 | @deffnx {Scheme Procedure} hashv-get-handle table key | |
2430 | @deffnx {Scheme Procedure} hashx-get-handle hash assoc table key | |
4c731ece | 2431 | @deffnx {C Function} scm_hash_get_handle (table, key) |
ac5fa6d1 KR |
2432 | @deffnx {C Function} scm_hashq_get_handle (table, key) |
2433 | @deffnx {C Function} scm_hashv_get_handle (table, key) | |
4c731ece | 2434 | @deffnx {C Function} scm_hashx_get_handle (hash, assoc, table, key) |
ac5fa6d1 KR |
2435 | Return the @code{(@var{key} . @var{value})} pair for @var{key} in the |
2436 | given hash @var{table}, or @code{#f} if @var{key} is not in | |
2437 | @var{table}. | |
4c731ece NJ |
2438 | @end deffn |
2439 | ||
ac5fa6d1 KR |
2440 | @deffn {Scheme Procedure} hash-create-handle! table key init |
2441 | @deffnx {Scheme Procedure} hashq-create-handle! table key init | |
2442 | @deffnx {Scheme Procedure} hashv-create-handle! table key init | |
2443 | @deffnx {Scheme Procedure} hashx-create-handle! hash assoc table key init | |
2444 | @deffnx {C Function} scm_hash_create_handle_x (table, key, init) | |
4c731ece | 2445 | @deffnx {C Function} scm_hashq_create_handle_x (table, key, init) |
4c731ece | 2446 | @deffnx {C Function} scm_hashv_create_handle_x (table, key, init) |
ac5fa6d1 KR |
2447 | @deffnx {C Function} scm_hashx_create_handle_x (hash, assoc, table, key, init) |
2448 | Return the @code{(@var{key} . @var{value})} pair for @var{key} in the | |
2449 | given hash @var{table}. If @var{key} is not in @var{table} then | |
2450 | create an entry for it with @var{init} as the value, and return that | |
2451 | pair. | |
4c731ece NJ |
2452 | @end deffn |
2453 | ||
ac5fa6d1 KR |
2454 | @deffn {Scheme Procedure} hash-map proc table |
2455 | @deffnx {Scheme Procedure} hash-for-each proc table | |
2456 | @deffnx {C Function} scm_hash_map (proc, table) | |
2457 | @deffnx {C Function} scm_hash_for_each (proc, table) | |
2458 | Apply @var{proc} to the entries in the given hash @var{table}. Each | |
2459 | call is @code{(@var{proc} @var{key} @var{value})}. @code{hash-map} | |
2460 | returns a list of the results from these calls, @code{hash-for-each} | |
3adbc48c | 2461 | discards the results and returns an unspecified value. |
4c731ece | 2462 | |
ac5fa6d1 KR |
2463 | Calls are made over the table entries in an unspecified order, and for |
2464 | @code{hash-map} the order of the values in the returned list is | |
2465 | unspecified. Results will be unpredictable if @var{table} is modified | |
2466 | while iterating. | |
2467 | ||
2468 | For example the following returns a new alist comprising all the | |
2469 | entries from @code{mytable}, in no particular order. | |
2470 | ||
2471 | @example | |
2472 | (hash-map cons mytable) | |
2473 | @end example | |
4c731ece NJ |
2474 | @end deffn |
2475 | ||
2476 | @deffn {Scheme Procedure} hash-fold proc init table | |
2477 | @deffnx {C Function} scm_hash_fold (proc, init, table) | |
ac5fa6d1 KR |
2478 | Accumulate a result by applying @var{proc} to the elements of the |
2479 | given hash @var{table}. Each call is @code{(@var{proc} @var{key} | |
2480 | @var{value} @var{prior-result})}, where @var{key} and @var{value} are | |
2481 | from the @var{table} and @var{prior-result} is the return from the | |
2482 | previous @var{proc} call. For the first call, @var{prior-result} is | |
2483 | the given @var{init} value. | |
2484 | ||
2485 | Calls are made over the table entries in an unspecified order. | |
2486 | Results will be unpredictable if @var{table} is modified while | |
2487 | @code{hash-fold} is running. | |
2488 | ||
2489 | For example, the following returns a count of how many keys in | |
2490 | @code{mytable} are strings. | |
2491 | ||
2492 | @example | |
2493 | (hash-fold (lambda (key value prior) | |
2494 | (if (string? key) (1+ prior) prior)) | |
2495 | 0 mytable) | |
2496 | @end example | |
4c731ece NJ |
2497 | @end deffn |
2498 | ||
2499 | ||
2500 | @c Local Variables: | |
2501 | @c TeX-master: "guile.texi" | |
2502 | @c End: |