mirror of
https://github.com/justinethier/cyclone.git
synced 2025-05-18 21:29:18 +02:00
360 lines
12 KiB
Markdown
360 lines
12 KiB
Markdown
# SRFI 133 - Vector Library
|
|
|
|
The `(srfi 133)` provides a vector library.
|
|
|
|
See the [SRFI document](http://srfi.schemers.org/srfi-133/srfi-133.html) for more information.
|
|
|
|
## Constructors
|
|
[`vector-unfold`](#vector-unfold)
|
|
[`vector-unfold-right`](#vector-unfold-right)
|
|
[`vector-reverse-copy`](#vector-reverse-copy)
|
|
[`vector-concatenate`](#vector-concatenate)
|
|
[`vector-append-subvectors`](#vector-append-subvectors)
|
|
|
|
## Predicates
|
|
[`vector-empty?`](#vector-empty)
|
|
[`vector=`](#vector)
|
|
|
|
## Iteration
|
|
[`vector-fold`](#vector-fold)
|
|
[`vector-fold-right`](#vector-fold-right)
|
|
[`vector-map!`](#vector-map)
|
|
[`vector-count`](#vector-count)
|
|
[`vector-cumulate`](#vector-cumulate)
|
|
|
|
## Searching
|
|
[`vector-index`](#vector-index)
|
|
[`vector-index-right`](#vector-index-right)
|
|
[`vector-skip`](#vector-skip)
|
|
[`vector-skip-right`](#vector-skip-right)
|
|
[`vector-binary-search`](#vector-binary-search)
|
|
[`vector-any`](#vector-any)
|
|
[`vector-every`](#vector-every)
|
|
[`vector-partition`](#vector-partition)
|
|
|
|
## Mutators
|
|
[`vector-swap!`](#vector-swap)
|
|
[`vector-reverse!`](#vector-reverse)
|
|
[`vector-reverse-copy!`](#vector-reverse-copy)
|
|
[`vector-unfold!`](#vector-unfold)
|
|
[`vector-unfold-right!`](#vector-unfold-right)
|
|
|
|
## Conversion
|
|
[`reverse-vector->list`](#reverse-vector-list)
|
|
[`reverse-list->vector`](#reverse-list-vector)
|
|
|
|
# vector-unfold
|
|
|
|
(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. Note that the termination condition is different from the `unfold` procedure of SRFI 1.
|
|
|
|
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))
|
|
|
|
# vector-unfold-right
|
|
|
|
(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. The first `index` used is `length - 1`. Note that the termination condition is different from the `unfold-right` procedure of SRFI 1.
|
|
|
|
Examples:
|
|
|
|
Construct a vector of pairs of non-negative integers whose values sum to 4.
|
|
|
|
(vector-unfold-right (λ (i x) (values (cons i x) (+ x 1))) 5 0)
|
|
#((0 . 4) (1 . 3) (2 . 2) (3 . 1) (4 . 0))
|
|
|
|
Reverse vector.
|
|
|
|
(vector-unfold-right (λ (i x) (values (vector-ref vector x) (+ x 1)))
|
|
(vector-length vector)
|
|
0)
|
|
|
|
|
|
# vector-reverse-copy
|
|
|
|
(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)
|
|
|
|
# vector-concatenate
|
|
|
|
(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)
|
|
|
|
# vector-append-subvectors
|
|
|
|
(vector-append-subvectors [vec start end] ...) -> vector
|
|
|
|
Returns a vector that contains every element of each `vec` from `start` to `end` in the specified order. This procedure is a generalization of `vector-append`.
|
|
|
|
Example:
|
|
|
|
(vector-append-subvectors '#(a b c d e) 0 2 '#(f g h i j) 2 4)
|
|
#(a b h i)
|
|
|
|
# vector-empty?
|
|
|
|
(vector-empty? vec) -> boolean
|
|
|
|
Returns `#t` if `vec` is empty, i.e. its length is `0`, and `#f` if not.
|
|
|
|
# vector=
|
|
|
|
(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 element `Ea` and `Eb`, `(elt=? Ea Eb)` returns a true value. `Elt=?` is always applied to two arguments.
|
|
|
|
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
|
|
|
|
# vector-fold
|
|
|
|
(vector-fold kons knil vec1 vec2 ...) -> value
|
|
|
|
The fundamental vector iterator. `Kons` is iterated over each value in all of the vectors, stopping at the end of the shortest; `kons` is applied as `(kons state (vector-ref vec1 i) (vector-ref vec2 i) ...)` where `state` is the current state value. The current state value begins with `knil`, and becomes whatever `kons` returned on the previous 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 (λ (len str) (max (string-length str) len))
|
|
0 vector-of-strings)
|
|
|
|
Produce a list of the reversed elements of `vec`.
|
|
|
|
(vector-fold (λ (tail elt) (cons elt tail))
|
|
'() vec)
|
|
|
|
Count the number of even numbers in `vec`.
|
|
|
|
(vector-fold (λ (counter n)
|
|
(if (even? n) (+ counter 1) counter))
|
|
0 vec)
|
|
|
|
# vector-fold-right
|
|
|
|
(vector-fold-right kons knil vec1 vec2 ...) -> 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 (λ (tail elt) (cons elt tail))
|
|
'() '#(a b c d))
|
|
(a b c d)
|
|
|
|
# vector-map!
|
|
|
|
(vector-map! f vec1 vec2 ...) -> unspecified
|
|
|
|
Similar to `vector-map`, but rather than mapping the new elements into a new vector, the new mapped elements are destructively inserted into `vec1`. Again, the dynamic order of application of `f` is unspecified, so it is dangerous for `f` to apply either `vector-ref` or `vector-set!` to `vec1` in `f`.
|
|
|
|
# vector-count
|
|
|
|
(vector-count pred? vec1 vec2 ...) -> 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 each parallel element in the vectors, in order.
|
|
|
|
Examples:
|
|
|
|
(vector-count even? '#(3 1 4 1 5 9 2 5 6))
|
|
3
|
|
|
|
(vector-count < '#(1 3 6 9) '#(2 4 6 8 10 12))
|
|
2
|
|
|
|
# vector-cumulate
|
|
|
|
(vector-cumulate f knil vec) -> vector
|
|
|
|
Returns a newly allocated vector `new` with the same length as `vec`. Each element `i` of `new` is set to the result of invoking `f` on `newi-1` and `veci`, except that for the first call on `f`, the first argument is `knil`. The new vector is returned.
|
|
|
|
Example:
|
|
|
|
(vector-cumulate + 0 '#(3 1 4 1 5 9 2 5 6))
|
|
#(3 4 8 9 14 23 25 30 36)
|
|
|
|
# vector-index
|
|
|
|
(vector-index pred? vec1 vec2 ...) -> exact nonnegative integer or #f
|
|
|
|
Finds & returns the index of the first elements in `vec1 vec2 ...` 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
|
|
|
|
# vector-index-right
|
|
|
|
(vector-index-right pred? vec1 vec2 ...) -> 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.
|
|
|
|
# vector-skip
|
|
|
|
(vector-skip pred? vec1 vec2 ...) -> exact nonnegative integer or #f
|
|
|
|
Finds & returns the index of the first elements in `vec1 vec2 ...` 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 (λ (x1 x2 ...) (not (pred? x1 x1 ...)))
|
|
vec1 vec2 ...)
|
|
|
|
Example:
|
|
|
|
(vector-skip number? '#(1 2 a b 3 4 c d))
|
|
2
|
|
|
|
# vector-skip-right
|
|
|
|
(vector-skip-right pred? vec1 vec2 ...) -> 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 it is an error if all of the vectors do not have the same length. This is equivalent to:
|
|
|
|
(vector-index-right (λ (x1 x2 ...) (not (pred? x1 x1 ...)))
|
|
vec1 vec2 ...)
|
|
|
|
# vector-binary-search
|
|
|
|
(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. If there is more than one element of `vec` that matches value in the sense of `cmp`, `vector-binary-search` may return the index of any of them.
|
|
|
|
`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:
|
|
|
|
(lambdaλ (char1 char2)
|
|
(cond ((char<? char1 char2) -1)
|
|
((char=? char1 char2) 0)
|
|
(else 1)))
|
|
|
|
# vector-any
|
|
|
|
(vector-any pred? vec1 vec2 ...) -> value or #f
|
|
|
|
Finds the first set of elements in parallel from `vec1 vec2 ...` 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.
|
|
|
|
# vector-every
|
|
|
|
(vector-every pred? vec1 vec2 ...) -> value or #f
|
|
|
|
If, for every index `i` between `0` and the length of the shortest vector argument, the set of elements `(vector-ref vec1 i) (vector-ref vec2 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.
|
|
|
|
# vector-partition
|
|
|
|
(vector-partition pred? vec) -> vector and integer
|
|
|
|
A vector the same size as `vec` is newly allocated and filled with all the elements of `vec` that satisfy `pred?` in their original order followed by all the elements that do not satisfy `pred?`, also in their original order.
|
|
|
|
Two values are returned, the newly allocated vector and the index of the leftmost element that does not satisfy `pred?`.
|
|
|
|
# vector-swap!
|
|
|
|
(vector-swap! vec i j) -> unspecified
|
|
|
|
Swaps or exchanges the values of the locations in `vec` at `i` & `j`.
|
|
|
|
# vector-reverse!
|
|
|
|
(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.
|
|
|
|
# vector-reverse-copy!
|
|
|
|
(vector-reverse-copy! to at from [start [end]]) -> unspecified
|
|
|
|
Like `vector-copy!`, but the elements appear in to in reverse order.
|
|
|
|
# vector-unfold!
|
|
|
|
(vector-unfold! f vec start end initial-seed ...) -> unspecified
|
|
|
|
Like `vector-unfold`, but the elements are copied into the vector `vec` starting at element `start` rather than into a newly allocated vector. Terminates when `end-start` elements have been generated.
|
|
|
|
# vector-unfold-right!
|
|
|
|
(vector-unfold-right! f vec start end initial-seed ...) -> unspecified
|
|
|
|
`Like `vector-unfold!`, but the elements are copied in reverse order into the vector `vec` starting at the index preceding `end`.
|
|
|
|
# reverse-vector->list
|
|
|
|
(reverse-vector->list vec [start [end]]) -> proper-list
|
|
|
|
Like `vector->list`, but the resulting list contains the elements in reverse of `vec`.
|
|
|
|
# reverse-list->vector
|
|
|
|
(reverse-list->vector proper-list) -> vector
|
|
|
|
Like `list->vector`, but the resulting vector contains the elements in reverse of `proper-list`.
|
|
|