vector-lib

A library of vector operations for Chicken, based on the reference implementation in SRFI 43: Vector library.

This document contains the salient parts of the original SRFI 43 documentation. Chicken fully implements SRFI 43, with the following notes:

  1. vector-lib
  2. Procedures
    1. Constructors
    2. Predicates
    3. Iteration
    4. Searching
    5. Mutators
    6. Conversion
  3. About this egg
    1. Author
    2. Repository
    3. Version history
    4. License

Procedures

In this section containing specifications of procedures, the following notation is used to specify parameters and return values:

(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.
vec
The argument in this place must be a vector, i.e. it must satisfy the predicate vector?.
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.
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.
f
The argument in this place must be a function of one or more arguments, returning exactly one value.
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.
x, y, z, seed, knil, fill, key, value
The argument in this place may be any Scheme value.
[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.
something ···
Indicates that zero or more somethings are allowed to be arguments.
something_1 something_2 ···
Indicates that at least one something must be arguments.
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.

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.

Constructors

[procedure] (vector-unfold f length initial-seed ···) -> vector

The 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 kth 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.

Examples:

(vector-unfold (λ (i x) (values x (- x 1)))
               10 0)
  ;=> #(0 -1 -2 -3 -4 -5 -6 -7 -8 -9)

Construct a vector of the sequence of integers in the range [0,n).

(vector-unfold values n)
  ;=> #(0 1 2 ··· n-2 n-1)

Copy vector.

(vector-unfold (λ (i) (vector-ref vector i))
               (vector-length vector))
[procedure] (vector-unfold-right f length initial-seed ···) -> vector

Like vector-unfold, but it uses f to generate elements from right-to-left, rather than left-to-right.

Examples:

Construct a vector in reverse of the integers in the range [0,n).

(vector-unfold-right (λ (i x) (values x (+ x 1)))
                     n 0)
  ;=> #(n-1 n-2 ··· 2 1 0)

Reverse vector.

(vector-unfold-right (λ (i x) (values (vector-ref vector x) (+ x 1)))
                     (vector-length vector) 0)
[procedure] (vector-copy vec [start [end [fill]]]) -> vector

Allocates 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.

Examples:

(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)
[procedure] (vector-reverse-copy vec [start [end]]) -> vector

Like vector-copy, but it copies the elements in the reverse order from vec.

Example:

(vector-reverse-copy '#(5 4 3 2 1 0) 1 5)
  ;=> #(1 2 3 4)
[procedure] (vector-append vec ···) -> vector

Returns a newly allocated vector that contains all elements in order from the subsequent locations in vec ···.

Examples:

(vector-append '#(x) '#(y))
  ;=> #(x y)
(vector-append '#(a) '#(b c d))
  ;=> #(a b c d)
(vector-append '#(a #(b)) '#(#(c)))
  ;=> #(a #(b) #(c))
[procedure] (vector-concatenate list-of-vectors) -> vector

Appends each vector in list-of-vectors. This is equivalent to:

(apply vector-append list-of-vectors)

However, it may be implemented better.

Example:

(vector-concatenate '(#(a b) #(c d)))
  ;=> #(a b c d)

Predicates

[procedure] (vector-empty? vec) -> boolean

Returns #t if vec is empty, i.e. its length is 0, and #f if not.

Examples:

(vector-empty? '#(a))
  ;=> #f
(vector-empty? '#(()))
  ;=> #f
(vector-empty? '#(#()))
  ;=> #f
(vector-empty? '#())
  ;=> #t
[procedure] (vector= elt=? vec ···) -> boolean

Vector 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.)

If 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.

Examples:

(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

The two trivial cases.

(vector= eq?)
  ;=> #t
(vector= eq? '#(a))
  ;=> #t

Note 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?.

(vector= eq? (vector (vector 'a)) (vector (vector 'a)))
  ;=> #f
(vector= equal? (vector (vector 'a)) (vector (vector 'a)))
  ;=> #t

Iteration

[procedure] (vector-fold kons knil vec_1 vec_2 ···) -> value

The 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.

The iteration is strictly left-to-right.

Examples:

Find the longest string's length in vector-of-strings.

(vector-fold (λ (index len str) (max (string-length str) len))
             0 vector-of-strings)

Produce a list of the reversed elements of vec.

(vector-fold (λ (index tail elt) (cons elt tail))
             '() vec)

Count the number of even numbers in vec.

(vector-fold (λ (index counter n)
               (if (even? n) (+ counter 1) counter))
             0 vec)
[procedure] (vector-fold-right kons knil vec_1 vec_2 ···) -> value

Similar to vector-fold, but it iterates right to left instead of left to right.

Example:

Convert a vector to a list.

(vector-fold-right (λ (index tail elt) (cons elt tail))
                   '() '#(a b c d))
  ;=> (a b c d)
[procedure] (vector-map f vec_1 vec_2 ···) -> vector

Constructs 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.

Examples:

(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)
[procedure] (vector-map! f vec_1 vec_2 ···) -> unspecified

Similar 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.

[procedure] (vector-for-each f vec_1 vec_2 ···) -> unspecified

Simple 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.

Example:

(vector-for-each (λ (i x) (display x) (newline))
                 '#("foo" "bar" "baz" "quux" "zot"))

Displays:

foo
bar
baz
quux
zot
[procedure] (vector-count pred? vec_1 vec_2 ···) -> exact nonnegative integer

Counts 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.

Examples:

(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

Searching

[procedure] (vector-index pred? vec_1 vec_2 ···) -> exact nonnegative integer or #f

Finds & 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.

Examples:

(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
[procedure] (vector-index-right pred? vec_1 vec_2 ···) -> exact nonnegative integer or #f

Like vector-index, but it searches right-to-left, rather than left-to-right, and all of the vectors must have the same length.

[procedure] (vector-skip pred? vec_1 vec_2 ···) -> exact nonnegative integer or #f

Finds & 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:

(vector-index (λ (x_1 x_2 ···) (not (pred? x_1 x_1 ···)))
              vec_1 vec_2 ···)

Example:

(vector-skip number? '#(1 2 a b 3 4 c d))
  ;=> 2
[procedure] (vector-skip-right pred? vec_1 vec_2 ···) -> exact nonnegative integer or #f

Like 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:

(vector-index-right (λ (x_1 x_2 ···) (not (pred? x_1 x_1 ···)))
                    vec_1 vec_2 ···)
[procedure] (vector-binary-search vec value cmp) -> exact nonnegative integer or #f

Similar 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:

(λ (char_1 char_2)
  (cond ((char<? char_1 char_2) -1)
        ((char=? char_1 char_2) 0)
        (else 1)))
[procedure] (vector-any pred? vec_1 vec_2 ···) -> value or #f

Finds 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.

[procedure] (vector-every pred? vec_1 vec_2 ···) -> value or #f

If, 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.

Mutators

[procedure] (vector-swap! vec i j) -> unspecified

Swaps or exchanges the values of the locations in vec at i & j.

[procedure] (vector-fill! vec fill [start [end]]) -> unspecified

[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.

[procedure] (vector-reverse! vec [start [end]]) -> unspecified

Destructively 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.

[procedure] (vector-copy! target tstart source [sstart [send]]) -> unspecified

Copies 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.

[procedure] (vector-reverse-copy! target tstart source [sstart [send]]) -> unspecified

Like 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.

Conversion

[procedure] (vector->list vec [start [end]]) -> proper-list

[R5RS+] Creates a list containing the elements in vec between start, which defaults to 0, and end, which defaults to the length of vec.

[procedure] (reverse-vector->list vec [start [end]]) -> proper-list

Like vector->list, but the resulting list contains the elements in reverse between the the specified range.

[procedure] (list->vector proper-list [start [end]])

[R5RS+] Produce a vector containing the elements in proper-list, which must be a proper list, between start, whose default is 0, and end, whose default is the length of list. It is suggested that if the length of list is known in advance, the start and end arguments be passed, so that list->vector need not call length itself.

[procedure] (reverse-list->vector proper-list [start [end]]) -> vector

Like list->vector, but the resulting list contains the elements in reverse of proper-list.

About this egg

Author

Taylor Campbell. Chicken maintainer: Jim Ursetto. Test suite by Peter Danenberg.

Repository

This egg is hosted on the CHICKEN Subversion repository:

https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/vector-lib

If you want to check out the source code repository of this egg and you are not familiar with Subversion, see this page.

Version history
2.1.1
Fix segfault when calling certain procedures with non-fixnum as vector index (fixes #1631)
2.1
Test suite bug fix
2.0
Port to CHICKEN 5
1.2
Sync to reference implementation as of 2008-01-12
1.1
Final implementation port (2005-05-24 + patches) by Jim Ursetto
1.0
Draft implementation port by William S. Annis

License

The reference implementation is subject to the following copyright.

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.

The Chicken extension is covered under the 3-clause BSD license.

Copyright (c) 2005-2011 Jim Ursetto.  All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

- Redistributions of source code must retain the above copyright notice,
  this list of conditions and the following disclaimer. 
- Redistributions in binary form must reproduce the above copyright 
  notice, this list of conditions and the following disclaimer in the
  documentation and/or other materials provided with the distribution. 
- Neither the name of the author nor the names of its contributors may be 
  used to endorse or promote products derived from this software without 
  specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.