Mercurial > hg > xemacs-beta

comparison man/lispref/sequences.texi @ 428:3ecd8885ac67 r21-2-22

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-2-22
author cvs
date Mon, 13 Aug 2007 11:28:15 +0200
parents
children 576fb035e263
comparison
equal deleted inserted replaced
427:0a0253eac470 428:3ecd8885ac67
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 strings, vectors,
306 and bit vectors.
307
308 @defun arrayp object
309 This function returns @code{t} if @var{object} is an array (i.e., a
310 string, vector, or bit vector).
311
312 @example
313 @group
314 (arrayp "asdf")
315 @result{} t
316 (arrayp [a])
317 @result{} t
318 (arrayp #*101)
319 @result{} t
320 @end group
321 @end example
322 @end defun
323
324 @defun aref array index
325 @cindex array elements
326 This function returns the @var{index}th element of @var{array}. The
327 first element is at index zero.
328
329 @example
330 @group
331 (setq primes [2 3 5 7 11 13])
332 @result{} [2 3 5 7 11 13]
333 (aref primes 4)
334 @result{} 11
335 (elt primes 4)
336 @result{} 11
337 @end group
338
339 @group
340 (aref "abcdefg" 1)
341 @result{} ?b
342 @end group
343
344 @group
345 (aref #*1101 2)
346 @result{} 0
347 @end group
348 @end example
349
350 See also the function @code{elt}, in @ref{Sequence Functions}.
351 @end defun
352
353 @defun aset array index object
354 This function sets the @var{index}th element of @var{array} to be
355 @var{object}. It returns @var{object}.
356
357 @example
358 @group
359 (setq w [foo bar baz])
360 @result{} [foo bar baz]
361 (aset w 0 'fu)
362 @result{} fu
363 w
364 @result{} [fu bar baz]
365 @end group
366
367 @group
368 (setq x "asdfasfd")
369 @result{} "asdfasfd"
370 (aset x 3 ?Z)
371 @result{} ?Z
372 x
373 @result{} "asdZasfd"
374 @end group
375
376 @group
377 (setq bv #*1111)
378 @result{} #*1111
379 (aset bv 2 0)
380 @result{} 0
381 bv
382 @result{} #*1101
383 @end group
384 @end example
385
386 If @var{array} is a string and @var{object} is not a character, a
387 @code{wrong-type-argument} error results.
388 @end defun
389
390 @defun fillarray array object
391 This function fills the array @var{array} with @var{object}, so that
392 each element of @var{array} is @var{object}. It returns @var{array}.
393
394 @example
395 @group
396 (setq a [a b c d e f g])
397 @result{} [a b c d e f g]
398 (fillarray a 0)
399 @result{} [0 0 0 0 0 0 0]
400 a
401 @result{} [0 0 0 0 0 0 0]
402 @end group
403
404 @group
405 (setq s "When in the course")
406 @result{} "When in the course"
407 (fillarray s ?-)
408 @result{} "------------------"
409 @end group
410
411 @group
412 (setq bv #*1101)
413 @result{} #*1101
414 (fillarray bv 0)
415 @result{} #*0000
416 @end group
417 @end example
418
419 If @var{array} is a string and @var{object} is not a character, a
420 @code{wrong-type-argument} error results.
421 @end defun
422
423 The general sequence functions @code{copy-sequence} and @code{length}
424 are often useful for objects known to be arrays. @xref{Sequence Functions}.
425
426 @node Vectors
427 @section Vectors
428 @cindex vector
429
430 Arrays in Lisp, like arrays in most languages, are blocks of memory
431 whose elements can be accessed in constant time. A @dfn{vector} is a
432 general-purpose array; its elements can be any Lisp objects. (The other
433 kind of array in XEmacs Lisp is the @dfn{string}, whose elements must be
434 characters.) Vectors in XEmacs serve as obarrays (vectors of symbols),
435 although this is a shortcoming that should be fixed. They are also used
436 internally as part of the representation of a byte-compiled function; if
437 you print such a function, you will see a vector in it.
438
439 In XEmacs Lisp, the indices of the elements of a vector start from zero
440 and count up from there.
441
442 Vectors are printed with square brackets surrounding the elements.
443 Thus, a vector whose elements are the symbols @code{a}, @code{b} and
444 @code{a} is printed as @code{[a b a]}. You can write vectors in the
445 same way in Lisp input.
446
447 A vector, like a string or a number, is considered a constant for
448 evaluation: the result of evaluating it is the same vector. This does
449 not evaluate or even examine the elements of the vector.
450 @xref{Self-Evaluating Forms}.
451
452 Here are examples of these principles:
453
454 @example
455 @group
456 (setq avector [1 two '(three) "four" [five]])
457 @result{} [1 two (quote (three)) "four" [five]]
458 (eval avector)
459 @result{} [1 two (quote (three)) "four" [five]]
460 (eq avector (eval avector))
461 @result{} t
462 @end group
463 @end example
464
465 @node Vector Functions
466 @section Functions That Operate on Vectors
467
468 Here are some functions that relate to vectors:
469
470 @defun vectorp object
471 This function returns @code{t} if @var{object} is a vector.
472
473 @example
474 @group
475 (vectorp [a])
476 @result{} t
477 (vectorp "asdf")
478 @result{} nil
479 @end group
480 @end example
481 @end defun
482
483 @defun vector &rest objects
484 This function creates and returns a vector whose elements are the
485 arguments, @var{objects}.
486
487 @example
488 @group
489 (vector 'foo 23 [bar baz] "rats")
490 @result{} [foo 23 [bar baz] "rats"]
491 (vector)
492 @result{} []
493 @end group
494 @end example
495 @end defun
496
497 @defun make-vector length object
498 This function returns a new vector consisting of @var{length} elements,
499 each initialized to @var{object}.
500
501 @example
502 @group
503 (setq sleepy (make-vector 9 'Z))
504 @result{} [Z Z Z Z Z Z Z Z Z]
505 @end group
506 @end example
507 @end defun
508
509 @defun vconcat &rest sequences
510 @cindex copying vectors
511 This function returns a new vector containing all the elements of the
512 @var{sequences}. The arguments @var{sequences} may be lists, vectors,
513 or strings. If no @var{sequences} are given, an empty vector is
514 returned.
515
516 The value is a newly constructed vector that is not @code{eq} to any
517 existing vector.
518
519 @example
520 @group
521 (setq a (vconcat '(A B C) '(D E F)))
522 @result{} [A B C D E F]
523 (eq a (vconcat a))
524 @result{} nil
525 @end group
526 @group
527 (vconcat)
528 @result{} []
529 (vconcat [A B C] "aa" '(foo (6 7)))
530 @result{} [A B C 97 97 foo (6 7)]
531 @end group
532 @end example
533
534 The @code{vconcat} function also allows integers as arguments. It
535 converts them to strings of digits, making up the decimal print
536 representation of the integer, and then uses the strings instead of the
537 original integers. @strong{Don't use this feature; we plan to eliminate
538 it. If you already use this feature, change your programs now!} The
539 proper way to convert an integer to a decimal number in this way is with
540 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
541 (@pxref{String Conversion}).
542
543 For other concatenation functions, see @code{mapconcat} in @ref{Mapping
544 Functions}, @code{concat} in @ref{Creating Strings}, @code{append}
545 in @ref{Building Lists}, and @code{bvconcat} in @ref{Bit Vector Functions}.
546 @end defun
547
548 The @code{append} function provides a way to convert a vector into a
549 list with the same elements (@pxref{Building Lists}):
550
551 @example
552 @group
553 (setq avector [1 two (quote (three)) "four" [five]])
554 @result{} [1 two (quote (three)) "four" [five]]
555 (append avector nil)
556 @result{} (1 two (quote (three)) "four" [five])
557 @end group
558 @end example
559
560 @node Bit Vectors
561 @section Bit Vectors
562 @cindex bit vector
563
564 Bit vectors are specialized vectors that can only represent arrays
565 of 1's and 0's. Bit vectors have a very efficient representation
566 and are useful for representing sets of boolean (true or false) values.
567
568 There is no limit on the size of a bit vector. You could, for example,
569 create a bit vector with 100,000 elements if you really wanted to.
570
571 Bit vectors have a special printed representation consisting of
572 @samp{#*} followed by the bits of the vector. For example, a bit vector
573 whose elements are 0, 1, 1, 0, and 1, respectively, is printed as
574
575 @example
576 #*01101
577 @end example
578
579 Bit vectors are considered constants for evaluation, like vectors,
580 strings, and numbers. @xref{Self-Evaluating Forms}.
581
582 @node Bit Vector Functions
583 @section Functions That Operate on Bit Vectors
584
585 Here are some functions that relate to bit vectors:
586
587 @defun bit-vector-p object
588 This function returns @code{t} if @var{object} is a bit vector.
589
590 @example
591 @group
592 (bit-vector-p #*01)
593 @result{} t
594 (bit-vector-p [0 1])
595 @result{} nil
596 (bit-vector-p "01")
597 @result{} nil
598 @end group
599 @end example
600 @end defun
601
602 @defun bitp object
603 This function returns @code{t} if @var{object} is either 0 or 1.
604 @end defun
605
606 @defun bit-vector &rest objects
607 This function creates and returns a bit vector whose elements are the
608 arguments @var{objects}. The elements must be either of the two
609 integers 0 or 1.
610
611 @example
612 @group
613 (bit-vector 0 0 0 1 0 0 0 0 1 0)
614 @result{} #*0001000010
615 (bit-vector)
616 @result{} #*
617 @end group
618 @end example
619 @end defun
620
621 @defun make-bit-vector length object
622 This function creates and returns a bit vector consisting of
623 @var{length} elements, each initialized to @var{object}.
624
625 @example
626 @group
627 (setq picket-fence (make-bit-vector 9 1))
628 @result{} #*111111111
629 @end group
630 @end example
631 @end defun
632
633 @defun bvconcat &rest sequences
634 @cindex copying bit vectors
635 This function returns a new bit vector containing all the elements of
636 the @var{sequences}. The arguments @var{sequences} may be lists,
637 vectors, or bit vectors, all of whose elements are the integers 0 or 1.
638 If no @var{sequences} are given, an empty bit vector is returned.
639
640 The value is a newly constructed bit vector that is not @code{eq} to any
641 existing bit vector.
642
643 @example
644 @group
645 (setq a (bvconcat '(1 1 0) '(0 0 1)))
646 @result{} #*110001
647 (eq a (bvconcat a))
648 @result{} nil
649 @end group
650 @group
651 (bvconcat)
652 @result{} #*
653 (bvconcat [1 0 0 0 0] #*111 '(0 0 0 0 1))
654 @result{} #*1000011100001
655 @end group
656 @end example
657
658 For other concatenation functions, see @code{mapconcat} in @ref{Mapping
659 Functions}, @code{concat} in @ref{Creating Strings}, @code{vconcat} in
660 @ref{Vector Functions}, and @code{append} in @ref{Building Lists}.
661 @end defun
662
663 The @code{append} function provides a way to convert a bit vector into a
664 list with the same elements (@pxref{Building Lists}):
665
666 @example
667 @group
668 (setq bv #*00001110)
669 @result{} #*00001110
670 (append bv nil)
671 @result{} (0 0 0 0 1 1 1 0)
672 @end group
673 @end example