File: vectors.texi

package info (click to toggle)
mit-scheme-doc 7.7.90%2B20080130-1
  • links: PTS
  • area: non-free
  • in suites: lenny
  • size: 1,624 kB
  • ctags: 10
  • sloc: makefile: 217; sh: 216
file content (311 lines) | stat: -rw-r--r-- 10,935 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
@c This file is part of the MIT/GNU Scheme Reference Manual.
@c $Id: vectors.texi,v 1.3 2008/01/30 20:06:12 cph Exp $

@c Copyright (C) 1986, 1987, 1988, 1989, 1990, 1991, 1992, 1993, 1994,
@c     1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
@c     2005, 2006, 2007, 2008 Massachusetts Institute of Technology
@c See file scheme.texinfo for copying conditions.

@node Vectors, Bit Strings, Lists, Top
@chapter Vectors

@cindex vector (defn)
@dfn{Vectors} are heterogenous structures whose elements are indexed by
exact non-negative integers.  A vector typically occupies less space
than a list of the same length, and the average time required to access
a randomly chosen element is typically less for the vector than for the
list.

@cindex length, of vector (defn)
@cindex index, of vector (defn)
@cindex valid index, of vector (defn)
@cindex vector length (defn)
@cindex vector index (defn)
The @dfn{length} of a vector is the number of elements that it contains.
This number is an exact non-negative integer that is fixed when the
vector is created.  The @dfn{valid indexes} of a vector are the exact
non-negative integers less than the length of the vector.  The first
element in a vector is indexed by zero, and the last element is indexed
by one less than the length of the vector.

@cindex external representation, for vector
@cindex #( as external representation
@cindex parenthesis, as external representation
@findex #(
Vectors are written using the notation @code{#(@var{object} @dots{})}.
For example, a vector of length 3 containing the number zero in element
0, the list @code{(2 2 2 2)} in element 1, and the string @code{"Anna"}
in element 2 can be written as

@example
#(0 (2 2 2 2) "Anna")
@end example

@noindent
Note that this is the external representation of a vector, not an
expression evaluating to a vector.  Like list constants, vector
constants must be quoted:

@example
'#(0 (2 2 2 2) "Anna")          @result{}  #(0 (2 2 2 2) "Anna")
@end example

@cindex subvector (defn)
@cindex start, of subvector (defn)
@cindex end, of subvector (defn)
@cindex index, of subvector (defn)
@cindex valid index, of subvector (defn)
A number of the vector procedures operate on subvectors.  A
@dfn{subvector} is a segment of a vector that is specified by two exact
non-negative integers, @var{start} and @var{end}.  @var{Start} is the
index of the first element that is included in the subvector, and
@var{end} is one greater than the index of the last element that is
included in the subvector.  Thus if @var{start} and @var{end} are the
same, they refer to a null subvector, and if @var{start} is zero and
@var{end} is the length of the vector, they refer to the entire vector.
The @dfn{valid indexes} of a subvector are the exact integers between
@var{start} inclusive and @var{end} exclusive.

@menu
* Construction of Vectors::     
* Selecting Vector Components::  
* Cutting Vectors::             
* Modifying Vectors::           
@end menu

@node Construction of Vectors, Selecting Vector Components, Vectors, Vectors
@section Construction of Vectors
@cindex construction, of vector

@deffn {procedure} make-vector k [object]
Returns a newly allocated vector of @var{k} elements.  If @var{object}
is specified, @code{make-vector} initializes each element of the vector
to @var{object}.  Otherwise the initial elements of the result are
unspecified.
@end deffn

@deffn procedure vector object @dots{}
@findex list
Returns a newly allocated vector whose elements are the given arguments.
@code{vector} is analogous to @code{list}.

@example
(vector 'a 'b 'c)                       @result{}  #(a b c)
@end example
@end deffn

@deffn procedure vector-copy vector
@cindex copying, of vector
Returns a newly allocated vector that is a copy of @var{vector}.
@end deffn

@deffn procedure list->vector list
@cindex list, converting to vector
@findex vector->list
Returns a newly allocated vector initialized to the elements of
@var{list}.  The inverse of @code{list->vector} is @code{vector->list}.

@example
(list->vector '(dididit dah))           @result{}  #(dididit dah)
@end example
@end deffn

@deffn procedure make-initialized-vector k initialization
Similar to @code{make-vector}, except that the elements of the result
are determined by calling the procedure @var{initialization} on the
indices.  For example:

@example
@group
(make-initialized-vector 5 (lambda (x) (* x x)))
     @result{}  #(0 1 4 9 16)
@end group
@end example
@end deffn

@deffn procedure vector-grow vector k
@cindex growing, of vector
@var{K} must be greater than or equal to the length of @var{vector}.
Returns a newly allocated vector of length @var{k}.  The first
@code{(vector-length @var{vector})} elements of the result are
initialized from the corresponding elements of @var{vector}.  The
remaining elements of the result are unspecified.
@end deffn

@deffn procedure vector-map procedure vector
@cindex mapping, of vector
@var{Procedure} must be a procedure of one argument.  @code{vector-map}
applies @var{procedure} element-wise to the elements of @var{vector} and
returns a newly allocated vector of the results, in order from left to
right.  The dynamic order in which @var{procedure} is applied to the
elements of @var{vector} is unspecified.

@example
@group
(vector-map cadr '#((a b) (d e) (g h)))     @result{}  #(b e h)
(vector-map (lambda (n) (expt n n)) '#(1 2 3 4))
                                            @result{}  #(1 4 27 256)
(vector-map + '#(5 7 9))                    @result{}  #(5 7 9)
@end group
@end example
@end deffn

@node Selecting Vector Components, Cutting Vectors, Construction of Vectors, Vectors
@section Selecting Vector Components
@cindex selection, of vector component
@cindex component selection, of vector

@deffn procedure vector? object
@cindex type predicate, for vector
Returns @code{#t} if @var{object} is a vector; otherwise returns
@code{#f}.
@end deffn

@deffn procedure vector-length vector
Returns the number of elements in @var{vector}.
@end deffn

@deffn procedure vector-ref vector k
Returns the contents of element @var{k} of @var{vector}.  @var{K} must
be a valid index of @var{vector}.

@example
(vector-ref '#(1 1 2 3 5 8 13 21) 5)    @result{}  8
@end example
@end deffn

@deffn procedure vector-set! vector k object
Stores @var{object} in element @var{k} of @var{vector} and returns an
unspecified value.  @var{K} must be a valid index of
@var{vector}.

@example
@group
(let ((vec (vector 0 '(2 2 2 2) "Anna")))
  (vector-set! vec 1 '("Sue" "Sue"))
  vec)
     @result{}  #(0 ("Sue" "Sue") "Anna")
@end group
@end example
@end deffn

@deffn procedure vector-first vector
@deffnx procedure vector-second vector
@deffnx procedure vector-third vector
@deffnx procedure vector-fourth vector
@deffnx procedure vector-fifth vector
@deffnx procedure vector-sixth vector
@deffnx procedure vector-seventh vector
@deffnx procedure vector-eighth vector
These procedures access the first several elements of @var{vector} in
the obvious way.  It is an error if the implicit index of one of these
procedurs is not a valid index of @var{vector}.
@end deffn

@deffn procedure vector-binary-search vector key<? unwrap-key key
@cindex searching, of vector
Searches @var{vector} for an element with a key matching @var{key},
returning the element if one is found or @code{#f} if none.  The
search operation takes time proportional to the logarithm of the length
of @var{vector}.  @var{Unwrap-key} must be a procedure that maps each
element of @var{vector} to a key.  @var{Key<?} must be a procedure that
implements a total ordering on the keys of the elements.

@example
@group
(define (translate number)
  (vector-binary-search '#((1 . i)
                           (2 . ii)
                           (3 . iii)
                           (6 . vi))
                        < car number))
(translate 2)  @result{}  (2 . ii)
(translate 4)  @result{}  #F
@end group
@end example
@end deffn

@node Cutting Vectors, Modifying Vectors, Selecting Vector Components, Vectors
@section Cutting Vectors
@cindex cutting, of vector

@deffn procedure subvector vector start end
Returns a newly allocated vector that contains the elements of
@var{vector} between index @var{start} (inclusive) and @var{end}
(exclusive).
@end deffn

@deffn procedure vector-head vector end
Equivalent to

@example
(subvector @var{vector} 0 @var{end})
@end example
@end deffn

@deffn procedure vector-tail vector start
Equivalent to

@example
(subvector @var{vector} @var{start} (vector-length @var{vector}))
@end example
@end deffn

@node Modifying Vectors,  , Cutting Vectors, Vectors
@section Modifying Vectors
@cindex modification, of vector
@cindex filling, of vector
@cindex moving, of vector elements

@deffn {procedure} vector-fill! vector object
@deffnx procedure subvector-fill! vector start end object
Stores @var{object} in every element of the vector (subvector) and
returns an unspecified value.
@end deffn

@deffn procedure subvector-move-left! vector1 start1 end1 vector2 start2
@deffnx procedure subvector-move-right! vector1 start1 end1 vector2 start2
Destructively copies the elements of @var{vector1}, starting with index
@var{start1} (inclusive) and ending with @var{end1} (exclusive), into
@var{vector2} starting at index @var{start2} (inclusive).
@var{Vector1}, @var{start1}, and @var{end1} must specify a valid
subvector, and @var{start2} must be a valid index for @var{vector2}.
The length of the source subvector must not exceed the length of
@var{vector2} minus the index @var{start2}.

The elements are copied as follows (note that this is only important when
@var{vector1} and @var{vector2} are @code{eqv?}):

@table @code
@item subvector-move-left!
The copy starts at the left end and moves toward the right (from smaller
indices to larger).  Thus if @var{vector1} and @var{vector2} are the
same, this procedure moves the elements toward the left inside the
vector.

@item subvector-move-right!
The copy starts at the right end and moves toward the left (from larger
indices to smaller).  Thus if @var{vector1} and @var{vector2} are the
same, this procedure moves the elements toward the right inside the
vector.
@end table
@end deffn

@deffn procedure sort! vector procedure
@deffnx procedure merge-sort! vector procedure
@deffnx procedure quick-sort! vector procedure
@var{Procedure} must be a procedure of two arguments that defines a
@dfn{total ordering} on the elements of @var{vector}.  The elements of
@var{vector} are rearranged so that they are sorted in the order defined
by @var{procedure}.  The elements are rearranged in place, that is,
@var{vector} is destructively modified so that its elements are in the
new order.

@code{sort!} returns @var{vector} as its value.

Two sorting algorithms are implemented: @code{merge-sort!} and
@code{quick-sort!}.  The procedure @code{sort!} is an alias for
@code{merge-sort!}.

See also the definition of @code{sort}.
@end deffn