source: project/wiki/eggref/4/vector-lib @ 33759

Last change on this file since 33759 was 33759, checked in by svnwiki, 2 years ago

Anonymous wiki edit for IP [73.229.188.192]: typo in the result of vector-unfold example

File size: 20.7 KB
Line 
1[[tags:eggs]]
2
3== vector-lib
4
5A library of vector operations for Chicken, based on the reference
6implementation in [[http://srfi.schemers.org/srfi-43|SRFI 43: Vector
7library]].
8
9This document contains the salient parts of the original
10[[http://srfi.schemers.org/srfi-43/srfi-43.html|SRFI 43 documentation]].
11Chicken fully implements SRFI 43, with the following notes:
12
13* {{list->vector}} and {{reverse-list->vector}} take optional {{start}} and {{end}} arguments.
14Although not documented in the SRFI proper, the functionality is present in the reference implementation.
15
16* Procedures which are exactly equivalent to their R5RS counterparts
17have been omitted from this library: {{vector vector? make-vector vector-ref? vector-set! vector-length}}.
18
19[[toc:]]
20
21== Procedures
22
23In this section containing specifications of procedures, the following notation is used to specify parameters and return values:
24
25; {{(f arg_1 arg_2 ···) -> something}} : Indicates a function {{f}} takes the parameters {{arg_1 arg_2 ···}} and returns a value of the type {{something}}. If {{something}} is {{unspecified}}, then what {{f}} returns is implementation-dependant; this SRFI does not specify what it returns, and in order to write portable code, the return value should be ignored.
26; {{vec}} : The argument in this place must be a vector, i.e. it must satisfy the predicate {{vector?}}.
27; {{i, j, start, size}} : The argument in this place must be a nonnegative integer, i.e. it must satisfy the predicates {{integer?}} and either {{zero?}} or {{positive?}}. The third case of it indicates the index at which traversal begins; the fourth case of it indicates the size of a vector.
28; {{end}} : The argument in this place must be a positive integer, i.e. it must satisfy the predicates {{integer?}} and {{positive?}}. This indicates the index directly before which traversal will stop — processing will occur until the the index of the vector is {{end}}. It is the closed right side of a range.
29; {{f}} : The argument in this place must be a function of one or more arguments, returning exactly one value.
30; {{pred?}} : The argument in this place must be a function of one or more arguments that returns one value, which is treated as a boolean.
31; {{x, y, z, seed, knil, fill, key, value}} : The argument in this place may be any Scheme value.
32; {{[something]}} : Indicates that {{something}} is an optional argument; it needn't necessarily be applied. {{Something}} needn't necessarily be one thing; for example, this usage of it is perfectly valid: {{ [start [end]] }} and is indeed used quite often.
33; {{something ···}} : Indicates that zero or more {{something}}s are allowed to be arguments.
34; {{something_1 something_2 ···}} : Indicates that at least one {{something}} must be arguments.
35; {{something_1 something_2 ··· something_n}} : Exactly equivalent to the previous argument notation, but this also indicates that {{n}} will be used later in the procedure description.
36
37It should be noted that all of the procedures that iterate across multiple vectors in parallel stop iterating and produce the final result when the end of the shortest vector is reached. The sole exception is {{vector=}}, which automatically returns {{#f}} if the vectors' lengths vary.
38
39
40=== Constructors
41
42<procedure>(vector-unfold f length initial-seed ···) -> vector</procedure><br>
43
44The fundamental vector constructor. Creates a vector whose length is {{length}} and iterates across each index {{k}} between {{0}} and {{length}}, applying {{f}} at each iteration to the current index and current seeds, in that order, to receive {{n + 1}} values: first, the element to put in the {{k}}th slot of the new vector and {{n}} new seeds for the next iteration. It is an error for the number of seeds to vary between iterations.
45
46
47
48Examples:
49
50
51
52 (vector-unfold (λ (i x) (values x (- x 1)))
53                10 0)
54   ;=> #(0 -1 -2 -3 -4 -5 -6 -7 -8 -9)
55
56Construct a vector of the sequence of integers in the range [0,{{n}}).
57
58
59 (vector-unfold values n)
60   ;=> #(0 1 2 ··· n-2 n-1)
61
62Copy {{vector}}.
63
64
65
66 (vector-unfold (λ (i) (vector-ref vector i))
67                (vector-length vector))
68
69<procedure>(vector-unfold-right f length initial-seed ···) -> vector</procedure><br>
70
71Like {{vector-unfold}}, but it uses {{f}} to generate elements from right-to-left, rather than left-to-right.
72
73
74
75Examples:
76
77
78
79Construct a vector in reverse of the integers in the range [0,{{n}}).
80
81
82
83 (vector-unfold-right (λ (i x) (values x (+ x 1)))
84                      n 0)
85   ;=> #(n-1 n-2 ··· 2 1 0)
86
87Reverse {{vector}}.
88
89
90
91 (vector-unfold-right (λ (i x) (values (vector-ref vector x) (+ x 1)))
92                      (vector-length vector) 0)
93
94<procedure>(vector-copy vec [start [end [fill]]]) -> vector</procedure><br>
95
96Allocates a new vector whose length is {{end - start}} and fills it with elements from {{vec}}, taking elements from {{vec}} starting at index {{start}} and stopping at index {{end}}. {{start}} defaults to {{0}} and {{end}} defaults to the value of {{(vector-length vec)}}. If {{end}} extends beyond the length of {{vec}}, the slots in the new vector that obviously cannot be filled by elements from {{vec}} are filled with {{fill}}, whose default value is unspecified.
97
98
99
100Examples:
101
102
103
104 (vector-copy '#(a b c d e f g h i))
105   ;=> #(a b c d e f g h i)
106
107 (vector-copy '#(a b c d e f g h i) 6)
108   ;=> #(g h i)
109
110 (vector-copy '#(a b c d e f g h i) 3 6)
111   ;=> #(d e f)
112
113 (vector-copy '#(a b c d e f g h i) 6 12 'x)
114   ;=> #(g h i x x x)
115
116<procedure>(vector-reverse-copy vec [start [end]]) -> vector</procedure><br>
117
118Like {{vector-copy}}, but it copies the elements in the reverse order from {{vec}}.
119
120
121
122Example:
123
124
125
126 (vector-reverse-copy '#(5 4 3 2 1 0) 1 5)
127   ;=> #(1 2 3 4)
128
129<procedure>(vector-append vec ···) -> vector</procedure><br>
130
131Returns a newly allocated vector that contains all elements in order from the subsequent locations in {{vec ···}}.
132
133
134
135Examples:
136
137
138
139 (vector-append '#(x) '#(y))
140   ;=> #(x y)
141
142 (vector-append '#(a) '#(b c d))
143   ;=> #(a b c d)
144
145 (vector-append '#(a #(b)) '#(#(c)))
146   ;=> #(a #(b) #(c))
147
148<procedure>(vector-concatenate list-of-vectors) -> vector</procedure><br>
149
150Appends each vector in {{list-of-vectors}}. This is equivalent to:
151
152
153
154 (apply vector-append list-of-vectors)
155
156However, it may be implemented better.
157
158
159
160Example:
161
162
163
164 (vector-concatenate '(#(a b) #(c d)))
165   ;=> #(a b c d)
166
167
168
169
170=== Predicates
171
172<procedure>(vector-empty? vec) -> boolean</procedure><br>
173
174Returns {{#t}} if {{vec}} is empty, i.e. its length is {{0}}, and {{#f}} if not.
175
176
177
178Examples:
179
180
181
182 (vector-empty? '#(a))
183   ;=> #f
184
185 (vector-empty? '#(()))
186   ;=> #f
187
188 (vector-empty? '#(#()))
189   ;=> #f
190
191 (vector-empty? '#())
192   ;=> #t
193
194<procedure>(vector= elt=? vec ···) -> boolean</procedure><br>
195
196Vector structure comparator, generalized across user-specified element comparators. Vectors {{a}} and {{b}} are considered equal by {{vector=}} iff their lengths are the same, and for each respective elements {{E_a}} and {{E_b}}, {{(elt=? E_a E_b)}} returns a true value. {{Elt=?}} is always applied to two arguments. Element comparison must be consistent with {{eq}}; that is, if {{(eq? E_a E_b)}} results in a true value, then {{(elt=? E_a E_b)}} must also result in a true value. This may be exploited to avoid unnecessary element comparisons. (The reference implementation does, but it does not consider the situation where {{elt=?}} is in fact itself {{eq?}} to avoid yet more unnecessary comparisons.)
197
198
199
200If there are only zero or one vector arguments, {{#t}} is automatically returned. The dynamic order in which comparisons of elements and of vectors are performed is left completely unspecified; do not rely on a particular order.
201
202
203
204Examples:
205
206
207
208 (vector= eq? '#(a b c d) '#(a b c d))
209   ;=> #t
210
211 (vector= eq? '#(a b c d) '#(a b d c))
212   ;=> #f
213
214 (vector= = '#(1 2 3 4 5) '#(1 2 3 4))
215   ;=> #f
216
217 (vector= = '#(1 2 3 4) '#(1 2 3 4))
218   ;=> #t
219
220The two trivial cases.
221
222
223
224 (vector= eq?)
225   ;=> #t
226
227 (vector= eq? '#(a))
228   ;=> #t
229
230Note the fact that we don't use vector literals in the next two — it is unspecified whether or not literal vectors with the same external representation are {{eq?}}.
231
232
233
234 (vector= eq? (vector (vector 'a)) (vector (vector 'a)))
235   ;=> #f
236
237 (vector= equal? (vector (vector 'a)) (vector (vector 'a)))
238   ;=> #t
239
240
241
242=== Iteration
243
244<procedure>(vector-fold kons knil vec_1 vec_2 ···) -> value</procedure><br>
245
246The fundamental vector iterator. {{Kons}} is iterated over each index in all of the vectors, stopping at the end of the shortest; {{kons}} is applied as {{ (kons i state (vector-ref vec_1 i) (vector-ref vec_2 i) ···) }} where {{state}} is the current state value — the current state value begins with {{knil}}, and becomes whatever {{kons}} returned at the respective iteration —, and {{i}} is the current index.
247
248
249
250The iteration is strictly left-to-right.
251
252
253
254Examples:
255
256
257
258Find the longest string's length in {{vector-of-strings}}.
259
260
261 (vector-fold (λ (index len str) (max (string-length str) len))
262              0 vector-of-strings)
263
264Produce a list of the reversed elements of {{vec}}.
265
266
267 (vector-fold (λ (index tail elt) (cons elt tail))
268              '() vec)
269
270Count the number of even numbers in {{vec}}.
271
272
273 (vector-fold (λ (index counter n)
274                (if (even? n) (+ counter 1) counter))
275              0 vec)
276
277<procedure>(vector-fold-right kons knil vec_1 vec_2 ···) -> value</procedure><br>
278
279Similar to {{vector-fold}}, but it iterates right to left instead of left to right.
280
281
282
283Example:
284
285
286
287Convert a vector to a list.
288
289
290 (vector-fold-right (λ (index tail elt) (cons elt tail))
291                    '() '#(a b c d))
292   ;=> (a b c d)
293
294<procedure>(vector-map f vec_1 vec_2 ···) -> vector</procedure><br>
295
296Constructs a new vector of the shortest size of the vector arguments. Each element at index {{i}} of the new vector is mapped from the old vectors by {{(f i (vector-ref vec_1 i) (vector-ref vec_2 i) ···)}}. The dynamic order of application of {{f}} is unspecified.
297
298
299
300Examples:
301
302
303
304 (vector-map (λ (i x) (* x x))
305             (vector-unfold (λ (i x) (values x (+ x 1))) 4 1))
306   ;=> #(1 4 9 16)
307
308 (vector-map (λ (i x y) (* x y))
309             (vector-unfold (λ (i x) (values x (+ x 1))) 5 1)
310             (vector-unfold (λ (i x) (values x (- x 1))) 5 5))
311   ;=> #(5 8 9 8 5)
312
313 (let ((count 0))
314  (vector-map (λ (ignored-index ignored-elt)
315                (set! count (+ count 1))
316                count)
317              '#(a b)))
318   ;=> #(1 2) OR #(2 1)
319
320 (vector-map (λ (i elt) (+ i elt))
321             '#(1 2 3 4))
322   ;=> #(1 3 5 7)
323
324<procedure>(vector-map! f vec_1 vec_2 ···) -> unspecified</procedure><br>
325
326Similar to {{vector-map}}, but rather than mapping the new elements into a new vector, the new mapped elements are destructively inserted into {{vec_1}}. Again, the dynamic order of application of {{f}} unspecified, so it is dangerous for {{f}} to apply either {{vector-ref}} or {{vector-set!}} to {{vec_1}} in {{f}}.
327
328
329
330<procedure>(vector-for-each f vec_1 vec_2 ···) -> unspecified</procedure><br>
331
332Simple vector iterator: applies {{f}} to each index in the range [0, {{length}}), where {{length}} is the length of the smallest vector argument passed, and the respective list of parallel elements from {{vec_1 vec_2 ···}} at that index. In contrast with {{vector-map}}, {{f}} is reliably applied to each subsequent elements, starting at index 0, in the vectors.
333
334
335
336Example:
337
338
339
340 (vector-for-each (λ (i x) (display x) (newline))
341                  '#("foo" "bar" "baz" "quux" "zot"))
342Displays:
343
344
345
346 foo
347 bar
348 baz
349 quux
350 zot
351
352
353
354<procedure>(vector-count pred? vec_1 vec_2 ···) -> exact nonnegative integer</procedure><br>
355
356Counts the number of parallel elements in the vectors that satisfy {{pred?}}, which is applied, for each index {{i}} in the range [0, {{length}}) — where {{length}} is the length of the smallest vector argument —, to {{i}} and each parallel element in the vectors at that index, in order.
357
358
359
360Examples:
361
362
363
364 (vector-count (λ (i elt) (even? elt))
365               '#(3 1 4 1 5 9 2 5 6))
366   ;=> 3
367
368 (vector-count (λ (i x y) (< x y))
369               '#(1 3 6 9)
370               '#(2 4 6 8 10 12))
371   ;=> 2
372
373
374
375
376=== Searching
377
378<procedure>(vector-index pred? vec_1 vec_2 ···) -> exact nonnegative integer or #f</procedure><br>
379
380Finds & returns the index of the first elements in {{vec_1 vec_2 ···}} that satisfy {{pred?}}. If no matching element is found by the end of the shortest vector, {{#f}} is returned.
381
382
383
384Examples:
385
386
387
388 (vector-index even? '#(3 1 4 1 5 9))
389   ;=> 2
390
391 (vector-index < '#(3 1 4 1 5 9 2 5 6) '#(2 7 1 8 2))
392   ;=> 1
393
394 (vector-index = '#(3 1 4 1 5 9 2 5 6) '#(2 7 1 8 2))
395   ;=> #f
396
397<procedure>(vector-index-right pred? vec_1 vec_2 ···) -> exact nonnegative integer or #f</procedure><br>
398
399Like {{vector-index}}, but it searches right-to-left, rather than left-to-right, and all of the vectors ''must'' have the same length.
400
401
402
403<procedure>(vector-skip pred? vec_1 vec_2 ···) -> exact nonnegative integer or #f</procedure><br>
404
405Finds & returns the index of the first elements in {{vec_1 vec_2 ···}} that do ''not'' satisfy {{pred?}}. If all the values in the vectors satisfy {{pred?}} until the end of the shortest vector, this returns {{#f}}. This is equivalent to:
406
407
408
409 (vector-index (λ (x_1 x_2 ···) (not (pred? x_1 x_1 ···)))
410               vec_1 vec_2 ···)
411
412Example:
413
414
415
416 (vector-skip number? '#(1 2 a b 3 4 c d))
417   ;=> 2
418
419<procedure>(vector-skip-right pred? vec_1 vec_2 ···) -> exact nonnegative integer or #f</procedure><br>
420
421Like {{vector-skip}}, but it searches for a non-matching element right-to-left, rather than left-to-right, and all of the vectors ''must'' have the same length. This is equivalent to:
422
423
424
425 (vector-index-right (λ (x_1 x_2 ···) (not (pred? x_1 x_1 ···)))
426                     vec_1 vec_2 ···)
427
428<procedure>(vector-binary-search vec value cmp) -> exact nonnegative integer or #f</procedure><br>
429
430Similar to {{vector-index}} and {{vector-index-right}}, but instead of searching left to right or right to left, this performs a binary search. {{cmp}} should be a procedure of two arguments and return a negative integer, which indicates that its first argument is less than its second, zero, which indicates that they are equal, or a positive integer, which indicates that the first argument is greater than the second argument. An example {{cmp}} might be:
431
432
433
434 (λ (char_1 char_2)
435   (cond ((char<? char_1 char_2) -1)
436         ((char=? char_1 char_2) 0)
437         (else 1)))
438
439<procedure>(vector-any pred? vec_1 vec_2 ···) -> value or #f</procedure><br>
440
441Finds the first set of elements in parallel from {{vec_1 vec_2 ···}} for which {{pred?}} returns a true value. If such a parallel set of elements exists, {{vector-any}} returns the value that {{pred?}} returned for that set of elements. The iteration is strictly left-to-right.
442
443
444
445<procedure>(vector-every pred? vec_1 vec_2 ···) -> value or #f</procedure><br>
446
447If, for every index {{i}} between 0 and the length of the shortest vector argument, the set of elements {{(vector-ref vec_1 i) (vector-ref vec_2 i) ···}} satisfies {{pred?}}, {{vector-every}} returns the value that {{pred?}} returned for the last set of elements, at the last index of the shortest vector. The iteration is strictly left-to-right.
448
449
450
451
452
453
454=== Mutators
455
456
457<procedure>(vector-swap! vec i j) -> unspecified</procedure><br>
458
459Swaps or exchanges the values of the locations in {{vec}} at {{i}} & {{j}}.
460
461
462
463<procedure>(vector-fill! vec fill [start [end]]) -> unspecified</procedure><br>
464
465[''R5RS''+] Assigns the value of every location in {{vec}} between {{start}}, which defaults to {{0}} and {{end}}, which defaults to the length of {{vec}}, to {{fill}}.
466
467
468
469<procedure>(vector-reverse! vec [start [end]]) -> unspecified</procedure><br>
470
471Destructively reverses the contents of the sequence of locations in {{vec}} between {{start}} and {{end}}. {{Start}} defaults to {{0}} and {{end}} defaults to the length of {{vec}}. Note that this does not deeply reverse.
472
473
474
475<procedure>(vector-copy! target tstart source [sstart [send]]) -> unspecified</procedure><br>
476
477Copies a block of elements from {{source}} to {{target}}, both of which must be vectors, starting in {{target}} at {{tstart}} and starting in {{source}} at {{sstart}}, ending when {{send - sstart}} elements have been copied. It is an error for {{target}} to have a length less than {{tstart + (send - sstart)}}. {{Sstart}} defaults to {{0}} and {{send}} defaults to the length of {{source}}.
478
479
480
481<procedure>(vector-reverse-copy! target tstart source [sstart [send]]) -> unspecified</procedure><br>
482
483Like {{vector-copy!}}, but this copies the elements in the reverse order. It is an error if {{target}} and {{source}} are identical vectors and the target & source ranges overlap; however, if {{tstart = sstart}}, {{vector-reverse-copy!}} behaves as {{ (vector-reverse! target tstart send) }} would.
484
485
486
487
488
489
490=== Conversion
491
492<procedure>(vector->list vec [start [end]]) -> proper-list</procedure><br>
493
494[''R5RS''+] Creates a list containing the elements in {{vec}} between {{start}}, which defaults to {{0}}, and {{end}}, which defaults to the length of {{vec}}.
495
496
497
498<procedure>(reverse-vector->list vec [start [end]]) -> proper-list</procedure><br>
499
500Like {{vector->list}}, but the resulting list contains the elements in reverse between the the specified range.
501
502<procedure>(list->vector proper-list [start [end]])</procedure>
503
504[''R5RS''+] Produce a vector containing the elements in {{proper-list}}, which
505must be a proper list, between {{start}}, whose default is 0, and {{end}},
506whose default is the length of {{list}}.  It is suggested that if the
507length of {{list}} is known in advance, the {{start}} and {{end}} arguments
508be passed, so that {{list->vector}} need not call {{length}} itself.
509
510<procedure>(reverse-list->vector proper-list [start [end]]) -> vector</procedure><br>
511
512Like {{list->vector}}, but the resulting list contains the elements in reverse of {{proper-list}}.
513
514== About this egg
515
516=== Author
517
518Taylor Campbell.  Chicken maintainer: Jim Ursetto.  Test suite by Peter Danenberg.
519
520=== Version history
521
522; 1.2 : Sync to reference implementation as of 2008-01-12
523; 1.1 : Final implementation port (2005-05-24 + patches) by Jim Ursetto
524; 1.0 : Draft implementation port by William S. Annis
525
526=== License
527
528The reference implementation is subject to the following copyright.
529
530 Copyright (C) Taylor Campbell (2003). All rights reserved.
531 
532 Permission is hereby granted, free of charge, to any person obtaining
533 a copy of this software and associated documentation files (the
534 "Software"), to deal in the Software without restriction, including
535 without limitation the rights to use, copy, modify, merge, publish,
536 distribute, sublicense, and/or sell copies of the Software, and to
537 permit persons to whom the Software is furnished to do so, subject to
538 the following conditions:
539 
540 The above copyright notice and this permission notice shall be
541 included in all copies or substantial portions of the Software.
542 
543 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
544 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
545 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
546 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
547 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
548 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
549 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
550 SOFTWARE.
551
552The Chicken extension is covered under the 3-clause BSD license.
553
554 Copyright (c) 2005-2011 Jim Ursetto.  All rights reserved.
555 
556 Redistribution and use in source and binary forms, with or without
557 modification, are permitted provided that the following conditions are met:
558 
559 - Redistributions of source code must retain the above copyright notice,
560   this list of conditions and the following disclaimer.
561 - Redistributions in binary form must reproduce the above copyright
562   notice, this list of conditions and the following disclaimer in the
563   documentation and/or other materials provided with the distribution.
564 - Neither the name of the author nor the names of its contributors may be
565   used to endorse or promote products derived from this software without
566   specific prior written permission.
567 
568 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
569 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
570 THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
571 PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
572 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
573 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
574 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
575 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
576 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
577 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
578 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
579
Note: See TracBrowser for help on using the repository browser.