by Taylor Campbell
This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-43@nospamsrfi.schemers.org
. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
This SRFI proposes a comprehensive and complete library of vector operations accompanied by a freely available and complete reference implementation. The reference implementation is unencumbered by copyright, and useable with no modifications on any Scheme system that is R5RS-compliant. It also provides several hooks for implementation-specific optimization as well.
Because this SRFI is more of a library or module specification than a request for additions to readers or any other internal implementation detail, in an implementation that supports a module or structure or package or library or unit (et cetera) systems, these procedures should be contained in a module / structure / package / library / unit called vector-lib.
R5RS provides very few list-processing procedures, for which reason SRFI 1 (list-lib) exists. However, R5RS provides even fewer vector operations — while it provides mapping, appending, et cetera operations for lists, it specifies only nine vector manipulation operations —:
Many Scheme implementations provide several vector operations beyond the miniscule set that R5RS defines (the typical vector-append, vector-map, et cetera), but often these procedures have different names, take arguments in different orders, don't take the same number of arguments, or have some other flaw that makes them unportable. For this reason, this SRFI is proposed.
It should be noted that no vector sorting procedures are provided by this SRFI, because there already is a SRFI for such a purpose (SRFI 32 (sort-lib)), which includes routines for sorting not only vectors but also lists.
Here is an index of the procedures provided by this package. Those marked by bold are provided in R5RS and those marked by bold italic are defined by R5RS but are modified from their original definitions.
make-vector
vector
vector-unfold
vector-unfold-right
vector-copy
vector-reverse-copy
vector-append
vector-concatenate
vector?
vector-empty?
vector=
vector-ref
vector-length
vector-fold
vector-fold-right
vector-map
vector-map!
vector-for-each
vector-count
vector-index
vector-index-right
vector-skip
vector-skip-right
vector-binary-search
vector-any
vector-every
vector-set!
vector-swap!
vector-fill!
vector-reverse!
vector-copy!
vector-reverse-copy!
vector->list
reverse-vector->list
list->vector
reverse-list->vector
In this section containing specifications of procedures, the following notation is used to specify parameters and return values:
[start [end]]
It 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.
(make-vector 5 3)
#(3 3 3 3 3)
(vector 0 1 2 3 4)
#(0 1 2 3 4)
(vector-unfold (λ (i x) (values x (- x 1)))
10 0)
#(0 -1 -2 -3 -4 -5 -6 -7 -8 -8)
(vector-unfold values n)
#(0 1 2 ··· n-2 n-1)
(vector-unfold (λ (i) (vector-ref vector i))
(vector-length vector))
(vector-unfold-right (λ (i x) (values x (+ x 1))) n 0)
#(n-1 n-2 ··· 2 1 0)
(vector-unfold-right (λ (i x)
(values (vector-ref vector x)
(+ x 1)))
(vector-length vector)
0)
(vector-copy '#(a b c d e f g h i))
#(a b c d e f g h i)
(vector-copy '#(a b c d e f g h i) 6)
#(g h i)
(vector-copy '#(a b c d e f g h i) 3 6)
#(d e f)
(vector-copy '#(a b c d e f g h i) 6 12 'x)
#(g h i x x x)
(vector-reverse-copy '#(5 4 3 2 1 0) 1 5)
#(1 2 3 4)
(vector-append '#(x) '#(y))
#(x y)
(vector-append '#(a) '#(b c d))
#(a b c d)
(vector-append '#(a #(b)) '#(#(c)))
#(a #(b) #(c))
(apply vector-append
list-of-vectors)
(vector-concatenate '(#(a b) #(c d)))
#(a b c d)
(vector? '#(a b c))
#t
(vector? '(a b c))
#f
(vector? #t)
#f
(vector? '#())
#t
(vector? '())
#f
(vector-empty? '#(a))
#f
(vector-empty? '#(()))
#f
(vector-empty? '#(#()))
#f
(vector-empty? '#())
#t
(vector= eq? '#(a b c d) '#(a b c d))
#t
(vector= eq? '#(a b c d) '#(a b d c))
#f
(vector= = '#(1 2 3 4 5) '#(1 2 3 4))
#f
(vector= = '#(1 2 3 4) '#(1 2 3 4))
#t
(vector= eq?)
#t
(vector= eq? '#(a))
#t
(vector= eq? (vector (vector 'a)) (vector (vector 'a)))
#f
(vector= equal? (vector (vector 'a)) (vector (vector 'a)))
#t
(vector-ref '#(a b c d) 2)
c
(vector-length '#(a b c))
3
(vector-fold (λ (index len str)
(max (string-length str) len))
0 vector-of-strings)
(vector-fold (λ (index tail elt) (cons elt tail))
'() vec)
(vector-fold (λ (index counter n)
(if (even? n) (+ counter 1) counter))
0 vec)
(vector-fold-right (λ (index tail elt)
(cons elt tail))
'() '#(a b c d))
(a b c d)
(vector-map (λ (i x) (* x x))
(vector-unfold
(λ (i x) (values x (+ x 1)))
4 1))
#(1 4 9 16)
(vector-map (λ (i x y) (* x y))
(vector-unfold
(λ (i x) (values x (+ x 1)))
5 1)
(vector-unfold
(λ (i x) (values x (- x 1)))
5 5))
#(5 8 9 8 5)
(let ((count 0))
(vector-map (λ (ignored-index ignored-elt)
(set! count (+ count 1))
count)
'#(a b)))
#(1 2) OR #(2 1)
(vector-map (λ (i elt) (+ i elt)) '#(1 2 3 4))
#(1 3 5 7)
(vector-for-each (λ (i x) (display x) (newline))
'#("foo" "bar" "baz" "quux" "zot"))
foo bar baz quux zot
(vector-count (λ (i elt) (even? elt))
'#(3 1 4 1 5 9 2 5 6))
3
(vector-count (λ (i x y) (< x y))
'#(1 3 6 9) '#(2 4 6 8 10 12))
2
(vector-index even? '#(3 1 4 1 5 9))
2
(vector-index < '#(3 1 4 1 5 9 2 5 6) '#(2 7 1 8 2))
1
(vector-index = '#(3 1 4 1 5 9 2 5 6) '#(2 7 1 8 2))
#f
(vector-index
(λ (x_{1} x_{2}
···)
(not (pred? x_{1}
x_{1}
···)))
vec_{1} vec_{2}
···)
(vector-skip number? '#(1 2 a b 3 4 c d))
2
(vector-index-right
(λ (x_{1} x_{2}
···)
(not (pred? x_{1}
x_{1}
···)))
vec_{1} vec_{2}
···)
(λ (char_{1} char_{2})
(cond ((char<? char_{1}
char_{2})
-1)
((char=? char_{1}
char_{2})
0)
(else 1)))
With this SRFI comes a complete reference implementation. It is
licensed under a very open copyright with which no implementors
should have any legal issues.
The reference implementation has only one non-R5RS dependency:
SRFI 23's error procedure.
This reference implementation of all the procedures described in
this SRFI can be found here.
Thanks to Olin Shivers for his wonderfully complete list and string packages; to all the members of the #scheme IRC channel on Freenode who nitpicked a great deal, but also helped quite a lot in general, and helped test the reference implementation in various Scheme systems; to Michael Burschik for his numerous comments; to Sergei Egorov for helping to narrow down the procedures; to Mike Sperber for putting up with an extremely overdue draft; to Felix Winkelmann for continually bugging me about finishing up the SRFI so that it would be only overdue and not withdrawn; and to everyone else who gave questions, comments, thoughts, or merely attention to the SRFI.
Copyright (C) Taylor Campbell (2003). All rights reserved.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.