Mercurial > hg > xemacs-beta

comparison man/lispref/sequences.texi @ 0:376386a54a3c r19-14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r19-14
author cvs
date Mon, 13 Aug 2007 08:45:50 +0200
parents
children bcdc7deadc19
comparison
equal deleted inserted replaced
-1:000000000000 0:376386a54a3c
1 @c -*-texinfo-*-
2 @c This is part of the XEmacs Lisp Reference Manual.
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
4 @c Copyright (C) 1996 Ben Wing.
5 @c See the file lispref.texi for copying conditions.
6 @setfilename ../../info/sequences.info
7 @node Sequences Arrays Vectors, Symbols, Lists, Top
8 @chapter Sequences, Arrays, and Vectors
9 @cindex sequence
10
11 Recall that the @dfn{sequence} type is the union of four other Lisp
12 types: lists, vectors, bit vectors, and strings. In other words, any
13 list is a sequence, any vector is a sequence, any bit vector is a
14 sequence, and any string is a sequence. The common property that all
15 sequences have is that each is an ordered collection of elements.
16
17 An @dfn{array} is a single primitive object that has a slot for each
18 elements. All the elements are accessible in constant time, but the
19 length of an existing array cannot be changed. Strings, vectors, and
20 bit vectors are the three types of arrays.
21
22 A list is a sequence of elements, but it is not a single primitive
23 object; it is made of cons cells, one cell per element. Finding the
24 @var{n}th element requires looking through @var{n} cons cells, so
25 elements farther from the beginning of the list take longer to access.
26 But it is possible to add elements to the list, or remove elements.
27
28 The following diagram shows the relationship between these types:
29
30 @example
31 @group
32 ___________________________________
33 | |
34 | Sequence |
35 | ______ ______________________ |
36 | | | | | |
37 | | List | | Array | |
38 | | | | ________ _______ | |
39 | |______| | | | | | | |
40 | | | Vector | | String| | |
41 | | |________| |_______| | |
42 | | __________________ | |
43 | | | | | |
44 | | | Bit Vector | | |
45 | | |__________________| | |
46 | |______________________| |
47 |___________________________________|
48 @end group
49 @end example
50
51 The elements of vectors and lists may be any Lisp objects. The
52 elements of strings are all characters. The elements of bit vectors
53 are the numbers 0 and 1.
54
55 @menu
56 * Sequence Functions:: Functions that accept any kind of sequence.
57 * Arrays:: Characteristics of arrays in XEmacs Lisp.
58 * Array Functions:: Functions specifically for arrays.
59 * Vectors:: Special characteristics of XEmacs Lisp vectors.
60 * Vector Functions:: Functions specifically for vectors.
61 * Bit Vectors:: Special characteristics of XEmacs Lisp bit vectors.
62 * Bit Vector Functions:: Functions specifically for bit vectors.
63 @end menu
64
65 @node Sequence Functions
66 @section Sequences
67
68 In XEmacs Lisp, a @dfn{sequence} is either a list, a vector, a bit
69 vector, or a string. The common property that all sequences have is
70 that each is an ordered collection of elements. This section describes
71 functions that accept any kind of sequence.
72
73 @defun sequencep object
74 Returns @code{t} if @var{object} is a list, vector, bit vector, or
75 string, @code{nil} otherwise.
76 @end defun
77
78 @defun copy-sequence sequence
79 @cindex copying sequences
80 Returns a copy of @var{sequence}. The copy is the same type of object
81 as the original sequence, and it has the same elements in the same order.
82
83 Storing a new element into the copy does not affect the original
84 @var{sequence}, and vice versa. However, the elements of the new
85 sequence are not copies; they are identical (@code{eq}) to the elements
86 of the original. Therefore, changes made within these elements, as
87 found via the copied sequence, are also visible in the original
88 sequence.
89
90 If the sequence is a string with extents or text properties, the extents
91 and text properties in the copy are also copied, not shared with the
92 original. (This means that modifying the extents or text properties of
93 the original will not affect the copy.) However, the actual values of
94 the properties are shared. @xref{Extents}; @xref{Text Properties}.
95
96 See also @code{append} in @ref{Building Lists}, @code{concat} in
97 @ref{Creating Strings}, @code{vconcat} in @ref{Vectors}, and
98 @code{bvconcat} in @ref{Bit Vectors}, for other ways to copy sequences.
99
100 @example
101 @group
102 (setq bar '(1 2))
103 @result{} (1 2)
104 @end group
105 @group
106 (setq x (vector 'foo bar))
107 @result{} [foo (1 2)]
108 @end group
109 @group
110 (setq y (copy-sequence x))
111 @result{} [foo (1 2)]
112 @end group
113
114 @group
115 (eq x y)
116 @result{} nil
117 @end group
118 @group
119 (equal x y)
120 @result{} t
121 @end group
122 @group
123 (eq (elt x 1) (elt y 1))
124 @result{} t
125 @end group
126
127 @group
128 ;; @r{Replacing an element of one sequence.}
129 (aset x 0 'quux)
130 x @result{} [quux (1 2)]
131 y @result{} [foo (1 2)]
132 @end group
133
134 @group
135 ;; @r{Modifying the inside of a shared element.}
136 (setcar (aref x 1) 69)
137 x @result{} [quux (69 2)]
138 y @result{} [foo (69 2)]
139 @end group
140
141 @group
142 ;; @r{Creating a bit vector.}
143 (bit-vector 1 0 1 1 0 1 0 0)
144 @result{} #*10110100
145 @end group
146 @end example
147 @end defun
148
149 @defun length sequence
150 @cindex string length
151 @cindex list length
152 @cindex vector length
153 @cindex bit vector length
154 @cindex sequence length
155 Returns the number of elements in @var{sequence}. If @var{sequence} is
156 a cons cell that is not a list (because the final @sc{cdr} is not
157 @code{nil}), a @code{wrong-type-argument} error is signaled.
158
159 @example
160 @group
161 (length '(1 2 3))
162 @result{} 3
163 @end group
164 @group
165 (length ())
166 @result{} 0
167 @end group
168 @group
169 (length "foobar")
170 @result{} 6
171 @end group
172 @group
173 (length [1 2 3])
174 @result{} 3
175 @end group
176 @group
177 (length #*01101)
178 @result{} 5
179 @end group
180 @end example
181 @end defun
182
183 @defun elt sequence index
184 @cindex elements of sequences
185 This function returns the element of @var{sequence} indexed by
186 @var{index}. Legitimate values of @var{index} are integers ranging from
187 0 up to one less than the length of @var{sequence}. If @var{sequence}
188 is a list, then out-of-range values of @var{index} return @code{nil};
189 otherwise, they trigger an @code{args-out-of-range} error.
190
191 @example
192 @group
193 (elt [1 2 3 4] 2)
194 @result{} 3
195 @end group
196 @group
197 (elt '(1 2 3 4) 2)
198 @result{} 3
199 @end group
200 @group
201 (char-to-string (elt "1234" 2))
202 @result{} "3"
203 @end group
204 @group
205 (elt #*00010000 3)
206 @result{} 1
207 @end group
208 @group
209 (elt [1 2 3 4] 4)
210 @error{}Args out of range: [1 2 3 4], 4
211 @end group
212 @group
213 (elt [1 2 3 4] -1)
214 @error{}Args out of range: [1 2 3 4], -1
215 @end group
216 @end example
217
218 This function generalizes @code{aref} (@pxref{Array Functions}) and
219 @code{nth} (@pxref{List Elements}).
220 @end defun
221
222 @node Arrays
223 @section Arrays
224 @cindex array
225
226 An @dfn{array} object has slots that hold a number of other Lisp
227 objects, called the elements of the array. Any element of an array may
228 be accessed in constant time. In contrast, an element of a list
229 requires access time that is proportional to the position of the element
230 in the list.
231
232 When you create an array, you must specify how many elements it has.
233 The amount of space allocated depends on the number of elements.
234 Therefore, it is impossible to change the size of an array once it is
235 created; you cannot add or remove elements. However, you can replace an
236 element with a different value.
237
238 XEmacs defines three types of array, all of which are one-dimensional:
239 @dfn{strings}, @dfn{vectors}, and @dfn{bit vectors}. A vector is a
240 general array; its elements can be any Lisp objects. A string is a
241 specialized array; its elements must be characters. A bit vector is
242 another specialized array; its elements must be bits (an integer, either
243 0 or 1). Each type of array has its own read syntax. @xref{String
244 Type}, @ref{Vector Type}, and @ref{Bit Vector Type}.
245
246 All kinds of array share these characteristics:
247
248 @itemize @bullet
249 @item
250 The first element of an array has index zero, the second element has
251 index 1, and so on. This is called @dfn{zero-origin} indexing. For
252 example, an array of four elements has indices 0, 1, 2, @w{and 3}.
253
254 @item
255 The elements of an array may be referenced or changed with the functions
256 @code{aref} and @code{aset}, respectively (@pxref{Array Functions}).
257 @end itemize
258
259 In principle, if you wish to have an array of text characters, you
260 could use either a string or a vector. In practice, we always choose
261 strings for such applications, for four reasons:
262
263 @itemize @bullet
264 @item
265 They usually occupy one-fourth the space of a vector of the same
266 elements. (This is one-eighth the space for 64-bit machines such as the
267 DEC Alpha, and may also be different when @sc{MULE} support is compiled
268 into XEmacs.)
269
270 @item
271 Strings are printed in a way that shows the contents more clearly
272 as characters.
273
274 @item
275 Strings can hold extent and text properties. @xref{Extents}; @xref{Text
276 Properties}.
277
278 @item
279 Many of the specialized editing and I/O facilities of XEmacs accept only
280 strings. For example, you cannot insert a vector of characters into a
281 buffer the way you can insert a string. @xref{Strings and Characters}.
282 @end itemize
283
284 By contrast, for an array of keyboard input characters (such as a key
285 sequence), a vector may be necessary, because many keyboard input
286 characters are non-printable and are represented with symbols rather than
287 with characters. @xref{Key Sequence Input}.
288
289 Similarly, when representing an array of bits, a bit vector has
290 the following advantages over a regular vector:
291
292 @itemize @bullet
293 @item
294 They occupy 1/32nd the space of a vector of the same elements.
295 (1/64th on 64-bit machines such as the DEC Alpha.)
296
297 @item
298 Bit vectors are printed in a way that shows the contents more clearly
299 as bits.
300 @end itemize
301
302 @node Array Functions
303 @section Functions that Operate on Arrays
304
305 In this section, we describe the functions that accept both strings
306 and vectors.
307
308 @defun arrayp object
309 This function returns @code{t} if @var{object} is an array (i.e., either a
310 vector or a string).
311
312 @example
313 @group
314 (arrayp [a])
315 @result{} t
316 (arrayp "asdf")
317 @result{} t
318 @end group
319 @end example
320 @end defun
321
322 @defun aref array index
323 @cindex array elements
324 This function returns the @var{index}th element of @var{array}. The
325 first element is at index zero.
326
327 @example
328 @group
329 (setq primes [2 3 5 7 11 13])
330 @result{} [2 3 5 7 11 13]
331 (aref primes 4)
332 @result{} 11
333 (elt primes 4)
334 @result{} 11
335 @end group
336
337 @group
338 (aref "abcdefg" 1)
339 @result{} 98 ; @r{@samp{b} is @sc{ASCII} code 98.}
340 @end group
341 @end example
342
343 See also the function @code{elt}, in @ref{Sequence Functions}.
344 @end defun
345
346 @defun aset array index object
347 This function sets the @var{index}th element of @var{array} to be
348 @var{object}. It returns @var{object}.
349
350 @example
351 @group
352 (setq w [foo bar baz])
353 @result{} [foo bar baz]
354 (aset w 0 'fu)
355 @result{} fu
356 w
357 @result{} [fu bar baz]
358 @end group
359
360 @group
361 (setq x "asdfasfd")
362 @result{} "asdfasfd"
363 (aset x 3 ?Z)
364 @result{} 90
365 x
366 @result{} "asdZasfd"
367 @end group
368 @end example
369
370 If @var{array} is a string and @var{object} is not a character, a
371 @code{wrong-type-argument} error results.
372 @end defun
373
374 @defun fillarray array object
375 This function fills the array @var{array} with @var{object}, so that
376 each element of @var{array} is @var{object}. It returns @var{array}.
377
378 @example
379 @group
380 (setq a [a b c d e f g])
381 @result{} [a b c d e f g]
382 (fillarray a 0)
383 @result{} [0 0 0 0 0 0 0]
384 a
385 @result{} [0 0 0 0 0 0 0]
386 @end group
387 @group
388 (setq s "When in the course")
389 @result{} "When in the course"
390 (fillarray s ?-)
391 @result{} "------------------"
392 @end group
393 @end example
394
395 If @var{array} is a string and @var{object} is not a character, a
396 @code{wrong-type-argument} error results.
397 @end defun
398
399 The general sequence functions @code{copy-sequence} and @code{length}
400 are often useful for objects known to be arrays. @xref{Sequence Functions}.
401
402 @node Vectors
403 @section Vectors
404 @cindex vector
405
406 Arrays in Lisp, like arrays in most languages, are blocks of memory
407 whose elements can be accessed in constant time. A @dfn{vector} is a
408 general-purpose array; its elements can be any Lisp objects. (The other
409 kind of array in XEmacs Lisp is the @dfn{string}, whose elements must be
410 characters.) Vectors in XEmacs serve as obarrays (vectors of symbols),
411 although this is a shortcoming that should be fixed. They are also used
412 internally as part of the representation of a byte-compiled function; if
413 you print such a function, you will see a vector in it.
414
415 In XEmacs Lisp, the indices of the elements of a vector start from zero
416 and count up from there.
417
418 Vectors are printed with square brackets surrounding the elements.
419 Thus, a vector whose elements are the symbols @code{a}, @code{b} and
420 @code{a} is printed as @code{[a b a]}. You can write vectors in the
421 same way in Lisp input.
422
423 A vector, like a string or a number, is considered a constant for
424 evaluation: the result of evaluating it is the same vector. This does
425 not evaluate or even examine the elements of the vector.
426 @xref{Self-Evaluating Forms}.
427
428 Here are examples of these principles:
429
430 @example
431 @group
432 (setq avector [1 two '(three) "four" [five]])
433 @result{} [1 two (quote (three)) "four" [five]]
434 (eval avector)
435 @result{} [1 two (quote (three)) "four" [five]]
436 (eq avector (eval avector))
437 @result{} t
438 @end group
439 @end example
440
441 @node Vector Functions
442 @section Functions That Operate on Vectors
443
444 Here are some functions that relate to vectors:
445
446 @defun vectorp object
447 This function returns @code{t} if @var{object} is a vector.
448
449 @example
450 @group
451 (vectorp [a])
452 @result{} t
453 (vectorp "asdf")
454 @result{} nil
455 @end group
456 @end example
457 @end defun
458
459 @defun vector &rest objects
460 This function creates and returns a vector whose elements are the
461 arguments, @var{objects}.
462
463 @example
464 @group
465 (vector 'foo 23 [bar baz] "rats")
466 @result{} [foo 23 [bar baz] "rats"]
467 (vector)
468 @result{} []
469 @end group
470 @end example
471 @end defun
472
473 @defun make-vector length object
474 This function returns a new vector consisting of @var{length} elements,
475 each initialized to @var{object}.
476
477 @example
478 @group
479 (setq sleepy (make-vector 9 'Z))
480 @result{} [Z Z Z Z Z Z Z Z Z]
481 @end group
482 @end example
483 @end defun
484
485 @defun vconcat &rest sequences
486 @cindex copying vectors
487 This function returns a new vector containing all the elements of the
488 @var{sequences}. The arguments @var{sequences} may be lists, vectors,
489 or strings. If no @var{sequences} are given, an empty vector is
490 returned.
491
492 The value is a newly constructed vector that is not @code{eq} to any
493 existing vector.
494
495 @example
496 @group
497 (setq a (vconcat '(A B C) '(D E F)))
498 @result{} [A B C D E F]
499 (eq a (vconcat a))
500 @result{} nil
501 @end group
502 @group
503 (vconcat)
504 @result{} []
505 (vconcat [A B C] "aa" '(foo (6 7)))
506 @result{} [A B C 97 97 foo (6 7)]
507 @end group
508 @end example
509
510 The @code{vconcat} function also allows integers as arguments. It
511 converts them to strings of digits, making up the decimal print
512 representation of the integer, and then uses the strings instead of the
513 original integers. @strong{Don't use this feature; we plan to eliminate
514 it. If you already use this feature, change your programs now!} The
515 proper way to convert an integer to a decimal number in this way is with
516 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
517 (@pxref{String Conversion}).
518
519 For other concatenation functions, see @code{mapconcat} in @ref{Mapping
520 Functions}, @code{concat} in @ref{Creating Strings}, @code{append}
521 in @ref{Building Lists}, and @code{bvconcat} in @ref{Bit Vector Functions}.
522 @end defun
523
524 The @code{append} function provides a way to convert a vector into a
525 list with the same elements (@pxref{Building Lists}):
526
527 @example
528 @group
529 (setq avector [1 two (quote (three)) "four" [five]])
530 @result{} [1 two (quote (three)) "four" [five]]
531 (append avector nil)
532 @result{} (1 two (quote (three)) "four" [five])
533 @end group
534 @end example
535
536 @node Bit Vectors
537 @section Bit Vectors
538 @cindex bit vector
539
540 Bit vectors are specialized vectors that can only represent arrays
541 of 1's and 0's. Bit vectors have a very efficient representation
542 and are useful for representing sets of boolean (true or false) values.
543
544 There is no limit on the size of a bit vector. You could, for example,
545 create a bit vector with 100,000 elements if you really wanted to.
546
547 Bit vectors have a special printed representation consisting of
548 @samp{#*} followed by the bits of the vector. For example, a bit
549 vector whose elements are 0, 1, 1, 0, and 1, respectively, is printed
550 as
551
552 @example
553 #*01101
554 @end example
555
556 Bit vectors are considered constants for evaluation, like vectors,
557 strings, and numbers. @xref{Self-Evaluating Forms}.
558
559 @node Bit Vector Functions
560 @section Functions That Operate on Bit Vectors
561
562 Here are some functions that relate to bit vectors:
563
564 @defun bit-vector-p object
565 This function returns @code{t} if @var{object} is a bit vector.
566
567 @example
568 @group
569 (bit-vector-p #*01)
570 @result{} t
571 (bit-vector-p [0 1])
572 @result{} nil
573 (vectorp "asdf")
574 @result{} nil
575 @end group
576 @end example
577 @end defun
578
579 @defun bitp object
580 This function returns @code{t} if @var{object} is either 0 or 1.
581 @end defun
582
583 @defun bit-vector &rest objects
584 This function creates and returns a vector whose elements are the
585 arguments, @var{objects}. The elements must be either of the two
586 integers 0 or 1.
587
588 @example
589 @group
590 (bit-vector 0 0 0 1 0 0 0 0 1 0)
591 @result{} #*0001000010
592 (vector)
593 @result{} #*
594 @end group
595 @end example
596 @end defun
597
598 @defun make-bit-vector length object
599 This function returns a new bit vector consisting of @var{length} elements,
600 each initialized to @var{object}.
601
602 @example
603 @group
604 (setq sleepy (make-vector 9 1))
605 @result{} #*111111111
606 @end group
607 @end example
608 @end defun
609
610 @defun bvconcat &rest sequences
611 @cindex copying bit vectors
612 This function returns a new bit vector containing all the elements of the
613 @var{sequences}. The arguments @var{sequences} may be lists or vectors,
614 all of whose elements are the integers 0 or 1. If no @var{sequences} are
615 given, an empty bit vector is returned.
616
617 The value is a newly constructed bit vector that is not @code{eq} to any
618 existing vector.
619
620 @example
621 @group
622 (setq a (bvconcat '(1 1 0) '(0 0 1)))
623 @result{} #*110001
624 (eq a (bvconcat a))
625 @result{} nil
626 @end group
627 @group
628 (bvconcat)
629 @result{} #*
630 (bvconcat [1 0 0 0 0] #*111 '(0 0 0 0 1))
631 @result{} #*1000011100001
632 @end group
633 @end example
634
635 For other concatenation functions, see @code{mapconcat} in @ref{Mapping
636 Functions}, @code{concat} in @ref{Creating Strings}, @code{vconcat} in
637 @ref{Vector Functions}, and @code{append} in @ref{Building Lists}.
638 @end defun
639
640 The @code{append} function provides a way to convert a bit vector into a
641 list with the same elements (@pxref{Building Lists}):
642
643 @example
644 @group
645 (setq avector #*00001110)
646 @result{} #*00001110
647 (append avector nil)
648 @result{} (0 0 0 0 1 1 1 0)
649 @end group
650 @end example