]> code.delx.au - gnu-emacs/blob - lispref/sequences.texi
*** empty log message ***
[gnu-emacs] / lispref / sequences.texi
1 @c -*-texinfo-*-
2 @c This is part of the GNU Emacs Lisp Reference Manual.
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998 Free Software Foundation, Inc.
4 @c See the file elisp.texi for copying conditions.
5 @setfilename ../info/sequences
6 @node Sequences Arrays Vectors, Hash Tables, Lists, Top
7 @chapter Sequences, Arrays, and Vectors
8 @cindex sequence
9
10 Recall that the @dfn{sequence} type is the union of two other Lisp
11 types: lists and arrays. In other words, any list is a sequence, and
12 any array is a sequence. The common property that all sequences have is
13 that each is an ordered collection of elements.
14
15 An @dfn{array} is a single primitive object that has a slot for each
16 of its elements. All the elements are accessible in constant time, but
17 the length of an existing array cannot be changed. Strings, vectors,
18 char-tables and bool-vectors are the four types of arrays.
19
20 A list is a sequence of elements, but it is not a single primitive
21 object; it is made of cons cells, one cell per element. Finding the
22 @var{n}th element requires looking through @var{n} cons cells, so
23 elements farther from the beginning of the list take longer to access.
24 But it is possible to add elements to the list, or remove elements.
25
26 The following diagram shows the relationship between these types:
27
28 @example
29 @group
30 _____________________________________________
31 | |
32 | Sequence |
33 | ______ ________________________________ |
34 | | | | | |
35 | | List | | Array | |
36 | | | | ________ ________ | |
37 | |______| | | | | | | |
38 | | | Vector | | String | | |
39 | | |________| |________| | |
40 | | ____________ _____________ | |
41 | | | | | | | |
42 | | | Char-table | | Bool-vector | | |
43 | | |____________| |_____________| | |
44 | |________________________________| |
45 |_____________________________________________|
46 @end group
47 @end example
48
49 The elements of vectors and lists may be any Lisp objects. The
50 elements of strings are all characters.
51
52 @menu
53 * Sequence Functions:: Functions that accept any kind of sequence.
54 * Arrays:: Characteristics of arrays in Emacs Lisp.
55 * Array Functions:: Functions specifically for arrays.
56 * Vectors:: Special characteristics of Emacs Lisp vectors.
57 * Vector Functions:: Functions specifically for vectors.
58 * Char-Tables:: How to work with char-tables.
59 * Bool-Vectors:: How to work with bool-vectors.
60 @end menu
61
62 @node Sequence Functions
63 @section Sequences
64
65 In Emacs Lisp, a @dfn{sequence} is either a list or an array. The
66 common property of all sequences is that they are ordered collections of
67 elements. This section describes functions that accept any kind of
68 sequence.
69
70 @defun sequencep object
71 Returns @code{t} if @var{object} is a list, vector, or
72 string, @code{nil} otherwise.
73 @end defun
74
75 @defun length sequence
76 @cindex string length
77 @cindex list length
78 @cindex vector length
79 @cindex sequence length
80 This function returns the number of elements in @var{sequence}. If
81 @var{sequence} is a cons cell that is not a list (because the final
82 @sc{cdr} is not @code{nil}), a @code{wrong-type-argument} error is
83 signaled.
84
85 @xref{List Elements}, for the related function @code{safe-length}.
86
87 @example
88 @group
89 (length '(1 2 3))
90 @result{} 3
91 @end group
92 @group
93 (length ())
94 @result{} 0
95 @end group
96 @group
97 (length "foobar")
98 @result{} 6
99 @end group
100 @group
101 (length [1 2 3])
102 @result{} 3
103 @end group
104 @group
105 (length (make-bool-vector 5 nil))
106 @result{} 5
107 @end group
108 @end example
109 @end defun
110
111 @defun elt sequence index
112 @cindex elements of sequences
113 This function returns the element of @var{sequence} indexed by
114 @var{index}. Legitimate values of @var{index} are integers ranging from
115 0 up to one less than the length of @var{sequence}. If @var{sequence}
116 is a list, then out-of-range values of @var{index} return @code{nil};
117 otherwise, they trigger an @code{args-out-of-range} error.
118
119 @example
120 @group
121 (elt [1 2 3 4] 2)
122 @result{} 3
123 @end group
124 @group
125 (elt '(1 2 3 4) 2)
126 @result{} 3
127 @end group
128 @group
129 ;; @r{We use @code{string} to show clearly which character @code{elt} returns.}
130 (string (elt "1234" 2))
131 @result{} "3"
132 @end group
133 @group
134 (elt [1 2 3 4] 4)
135 @error{} Args out of range: [1 2 3 4], 4
136 @end group
137 @group
138 (elt [1 2 3 4] -1)
139 @error{} Args out of range: [1 2 3 4], -1
140 @end group
141 @end example
142
143 This function generalizes @code{aref} (@pxref{Array Functions}) and
144 @code{nth} (@pxref{List Elements}).
145 @end defun
146
147 @defun copy-sequence sequence
148 @cindex copying sequences
149 Returns a copy of @var{sequence}. The copy is the same type of object
150 as the original sequence, and it has the same elements in the same order.
151
152 Storing a new element into the copy does not affect the original
153 @var{sequence}, and vice versa. However, the elements of the new
154 sequence are not copies; they are identical (@code{eq}) to the elements
155 of the original. Therefore, changes made within these elements, as
156 found via the copied sequence, are also visible in the original
157 sequence.
158
159 If the sequence is a string with text properties, the property list in
160 the copy is itself a copy, not shared with the original's property
161 list. However, the actual values of the properties are shared.
162 @xref{Text Properties}.
163
164 See also @code{append} in @ref{Building Lists}, @code{concat} in
165 @ref{Creating Strings}, and @code{vconcat} in @ref{Vectors}, for other
166 ways to copy sequences.
167
168 @example
169 @group
170 (setq bar '(1 2))
171 @result{} (1 2)
172 @end group
173 @group
174 (setq x (vector 'foo bar))
175 @result{} [foo (1 2)]
176 @end group
177 @group
178 (setq y (copy-sequence x))
179 @result{} [foo (1 2)]
180 @end group
181
182 @group
183 (eq x y)
184 @result{} nil
185 @end group
186 @group
187 (equal x y)
188 @result{} t
189 @end group
190 @group
191 (eq (elt x 1) (elt y 1))
192 @result{} t
193 @end group
194
195 @group
196 ;; @r{Replacing an element of one sequence.}
197 (aset x 0 'quux)
198 x @result{} [quux (1 2)]
199 y @result{} [foo (1 2)]
200 @end group
201
202 @group
203 ;; @r{Modifying the inside of a shared element.}
204 (setcar (aref x 1) 69)
205 x @result{} [quux (69 2)]
206 y @result{} [foo (69 2)]
207 @end group
208 @end example
209 @end defun
210
211 @node Arrays
212 @section Arrays
213 @cindex array
214
215 An @dfn{array} object has slots that hold a number of other Lisp
216 objects, called the elements of the array. Any element of an array may
217 be accessed in constant time. In contrast, an element of a list
218 requires access time that is proportional to the position of the element
219 in the list.
220
221 Emacs defines four types of array, all one-dimensional: @dfn{strings},
222 @dfn{vectors}, @dfn{bool-vectors} and @dfn{char-tables}. A vector is a
223 general array; its elements can be any Lisp objects. A string is a
224 specialized array; its elements must be characters. Each type of array
225 has its own read syntax.
226 @xref{String Type}, and @ref{Vector Type}.
227
228 All four kinds of array share these characteristics:
229
230 @itemize @bullet
231 @item
232 The first element of an array has index zero, the second element has
233 index 1, and so on. This is called @dfn{zero-origin} indexing. For
234 example, an array of four elements has indices 0, 1, 2, @w{and 3}.
235
236 @item
237 The length of the array is fixed once you create it; you cannot
238 change the length of an existing array.
239
240 @item
241 The array is a constant, for evaluation---in other words, it evaluates
242 to itself.
243
244 @item
245 The elements of an array may be referenced or changed with the functions
246 @code{aref} and @code{aset}, respectively (@pxref{Array Functions}).
247 @end itemize
248
249 When you create an array, other than a char-table, you must specify
250 its length. You cannot specify the length of a char-table, because that
251 is determined by the range of character codes.
252
253 In principle, if you want an array of text characters, you could use
254 either a string or a vector. In practice, we always choose strings for
255 such applications, for four reasons:
256
257 @itemize @bullet
258 @item
259 They occupy one-fourth the space of a vector of the same elements.
260
261 @item
262 Strings are printed in a way that shows the contents more clearly
263 as text.
264
265 @item
266 Strings can hold text properties. @xref{Text Properties}.
267
268 @item
269 Many of the specialized editing and I/O facilities of Emacs accept only
270 strings. For example, you cannot insert a vector of characters into a
271 buffer the way you can insert a string. @xref{Strings and Characters}.
272 @end itemize
273
274 By contrast, for an array of keyboard input characters (such as a key
275 sequence), a vector may be necessary, because many keyboard input
276 characters are outside the range that will fit in a string. @xref{Key
277 Sequence Input}.
278
279 @node Array Functions
280 @section Functions that Operate on Arrays
281
282 In this section, we describe the functions that accept all types of
283 arrays.
284
285 @defun arrayp object
286 This function returns @code{t} if @var{object} is an array (i.e., a
287 vector, a string, a bool-vector or a char-table).
288
289 @example
290 @group
291 (arrayp [a])
292 @result{} t
293 (arrayp "asdf")
294 @result{} t
295 (arrayp (syntax-table)) ;; @r{A char-table.}
296 @result{} t
297 @end group
298 @end example
299 @end defun
300
301 @defun aref array index
302 @cindex array elements
303 This function returns the @var{index}th element of @var{array}. The
304 first element is at index zero.
305
306 @example
307 @group
308 (setq primes [2 3 5 7 11 13])
309 @result{} [2 3 5 7 11 13]
310 (aref primes 4)
311 @result{} 11
312 @end group
313 @group
314 (aref "abcdefg" 1)
315 @result{} 98 ; @r{@samp{b} is @sc{ascii} code 98.}
316 @end group
317 @end example
318
319 See also the function @code{elt}, in @ref{Sequence Functions}.
320 @end defun
321
322 @defun aset array index object
323 This function sets the @var{index}th element of @var{array} to be
324 @var{object}. It returns @var{object}.
325
326 @example
327 @group
328 (setq w [foo bar baz])
329 @result{} [foo bar baz]
330 (aset w 0 'fu)
331 @result{} fu
332 w
333 @result{} [fu bar baz]
334 @end group
335
336 @group
337 (setq x "asdfasfd")
338 @result{} "asdfasfd"
339 (aset x 3 ?Z)
340 @result{} 90
341 x
342 @result{} "asdZasfd"
343 @end group
344 @end example
345
346 If @var{array} is a string and @var{object} is not a character, a
347 @code{wrong-type-argument} error results. If @var{array} is a string
348 and @var{object} is character, but @var{object} does not use the same
349 number of bytes as the character currently stored in @code{(aref
350 @var{object} @var{index})}, that is also an error. @xref{Splitting
351 Characters}.
352 @end defun
353
354 @defun fillarray array object
355 This function fills the array @var{array} with @var{object}, so that
356 each element of @var{array} is @var{object}. It returns @var{array}.
357
358 @example
359 @group
360 (setq a [a b c d e f g])
361 @result{} [a b c d e f g]
362 (fillarray a 0)
363 @result{} [0 0 0 0 0 0 0]
364 a
365 @result{} [0 0 0 0 0 0 0]
366 @end group
367 @group
368 (setq s "When in the course")
369 @result{} "When in the course"
370 (fillarray s ?-)
371 @result{} "------------------"
372 @end group
373 @end example
374
375 If @var{array} is a string and @var{object} is not a character, a
376 @code{wrong-type-argument} error results.
377 @end defun
378
379 The general sequence functions @code{copy-sequence} and @code{length}
380 are often useful for objects known to be arrays. @xref{Sequence Functions}.
381
382 @node Vectors
383 @section Vectors
384 @cindex vector
385
386 Arrays in Lisp, like arrays in most languages, are blocks of memory
387 whose elements can be accessed in constant time. A @dfn{vector} is a
388 general-purpose array of specified length; its elements can be any Lisp
389 objects. (By contrast, a string can hold only characters as elements.)
390 Vectors in Emacs are used for obarrays (vectors of symbols), and as part
391 of keymaps (vectors of commands). They are also used internally as part
392 of the representation of a byte-compiled function; if you print such a
393 function, you will see a vector in it.
394
395 In Emacs Lisp, the indices of the elements of a vector start from zero
396 and count up from there.
397
398 Vectors are printed with square brackets surrounding the elements.
399 Thus, a vector whose elements are the symbols @code{a}, @code{b} and
400 @code{a} is printed as @code{[a b a]}. You can write vectors in the
401 same way in Lisp input.
402
403 A vector, like a string or a number, is considered a constant for
404 evaluation: the result of evaluating it is the same vector. This does
405 not evaluate or even examine the elements of the vector.
406 @xref{Self-Evaluating Forms}.
407
408 Here are examples illustrating these principles:
409
410 @example
411 @group
412 (setq avector [1 two '(three) "four" [five]])
413 @result{} [1 two (quote (three)) "four" [five]]
414 (eval avector)
415 @result{} [1 two (quote (three)) "four" [five]]
416 (eq avector (eval avector))
417 @result{} t
418 @end group
419 @end example
420
421 @node Vector Functions
422 @section Functions for Vectors
423
424 Here are some functions that relate to vectors:
425
426 @defun vectorp object
427 This function returns @code{t} if @var{object} is a vector.
428
429 @example
430 @group
431 (vectorp [a])
432 @result{} t
433 (vectorp "asdf")
434 @result{} nil
435 @end group
436 @end example
437 @end defun
438
439 @defun vector &rest objects
440 This function creates and returns a vector whose elements are the
441 arguments, @var{objects}.
442
443 @example
444 @group
445 (vector 'foo 23 [bar baz] "rats")
446 @result{} [foo 23 [bar baz] "rats"]
447 (vector)
448 @result{} []
449 @end group
450 @end example
451 @end defun
452
453 @defun make-vector length object
454 This function returns a new vector consisting of @var{length} elements,
455 each initialized to @var{object}.
456
457 @example
458 @group
459 (setq sleepy (make-vector 9 'Z))
460 @result{} [Z Z Z Z Z Z Z Z Z]
461 @end group
462 @end example
463 @end defun
464
465 @defun vconcat &rest sequences
466 @cindex copying vectors
467 This function returns a new vector containing all the elements of the
468 @var{sequences}. The arguments @var{sequences} may be any kind of
469 arrays, including lists, vectors, or strings. If no @var{sequences} are
470 given, an empty vector is returned.
471
472 The value is a newly constructed vector that is not @code{eq} to any
473 existing vector.
474
475 @example
476 @group
477 (setq a (vconcat '(A B C) '(D E F)))
478 @result{} [A B C D E F]
479 (eq a (vconcat a))
480 @result{} nil
481 @end group
482 @group
483 (vconcat)
484 @result{} []
485 (vconcat [A B C] "aa" '(foo (6 7)))
486 @result{} [A B C 97 97 foo (6 7)]
487 @end group
488 @end example
489
490 The @code{vconcat} function also allows byte-code function objects as
491 arguments. This is a special feature to make it easy to access the entire
492 contents of a byte-code function object. @xref{Byte-Code Objects}.
493
494 The @code{vconcat} function also allows integers as arguments. It
495 converts them to strings of digits, making up the decimal print
496 representation of the integer, and then uses the strings instead of the
497 original integers. @strong{Don't use this feature; we plan to eliminate
498 it. If you already use this feature, change your programs now!} The
499 proper way to convert an integer to a decimal number in this way is with
500 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
501 (@pxref{String Conversion}).
502
503 For other concatenation functions, see @code{mapconcat} in @ref{Mapping
504 Functions}, @code{concat} in @ref{Creating Strings}, and @code{append}
505 in @ref{Building Lists}.
506 @end defun
507
508 The @code{append} function provides a way to convert a vector into a
509 list with the same elements (@pxref{Building Lists}):
510
511 @example
512 @group
513 (setq avector [1 two (quote (three)) "four" [five]])
514 @result{} [1 two (quote (three)) "four" [five]]
515 (append avector nil)
516 @result{} (1 two (quote (three)) "four" [five])
517 @end group
518 @end example
519
520 @node Char-Tables
521 @section Char-Tables
522 @cindex char-tables
523 @cindex extra slots of char-table
524
525 A char-table is much like a vector, except that it is indexed by
526 character codes. Any valid character code, without modifiers, can be
527 used as an index in a char-table. You can access a char-table's
528 elements with @code{aref} and @code{aset}, as with any array. In
529 addition, a char-table can have @dfn{extra slots} to hold additional
530 data not associated with particular character codes. Char-tables are
531 constants when evaluated.
532
533 @cindex subtype of char-table
534 Each char-table has a @dfn{subtype} which is a symbol. The subtype
535 has two purposes: to distinguish char-tables meant for different uses,
536 and to control the number of extra slots. For example, display tables
537 are char-tables with @code{display-table} as the subtype, and syntax
538 tables are char-tables with @code{syntax-table} as the subtype. A valid
539 subtype must have a @code{char-table-extra-slots} property which is an
540 integer between 0 and 10. This integer specifies the number of
541 @dfn{extra slots} in the char-table.
542
543 @cindex parent of char-table
544 A char-table can have a @dfn{parent}. which is another char-table. If
545 it does, then whenever the char-table specifies @code{nil} for a
546 particular character @var{c}, it inherits the value specified in the
547 parent. In other words, @code{(aref @var{char-table} @var{c})} returns
548 the value from the parent of @var{char-table} if @var{char-table} itself
549 specifies @code{nil}.
550
551 @cindex default value of char-table
552 A char-table can also have a @dfn{default value}. If so, then
553 @code{(aref @var{char-table} @var{c})} returns the default value
554 whenever the char-table does not specify any other non-@code{nil} value.
555
556 @defun make-char-table subtype &optional init
557 @tindex make-char-table
558 Return a newly created char-table, with subtype @var{subtype}. Each
559 element is initialized to @var{init}, which defaults to @code{nil}. You
560 cannot alter the subtype of a char-table after the char-table is
561 created.
562
563 There is no argument to specify the length of the char-table, because
564 all char-tables have room for any valid character code as an index.
565 @end defun
566
567 @defun char-table-p object
568 @tindex char-table-p
569 This function returns @code{t} if @var{object} is a char-table,
570 otherwise @code{nil}.
571 @end defun
572
573 @defun char-table-subtype char-table
574 @tindex char-table-subtype
575 This function returns the subtype symbol of @var{char-table}.
576 @end defun
577
578 @defun set-char-table-default char-table new-default
579 @tindex set-char-table-default
580 This function sets the default value of @var{char-table} to
581 @var{new-default}.
582
583 There is no special function to access the default value of a char-table.
584 To do that, use @code{(char-table-range @var{char-table} nil)}.
585 @end defun
586
587 @defun char-table-parent char-table
588 @tindex char-table-parent
589 This function returns the parent of @var{char-table}. The parent is
590 always either @code{nil} or another char-table.
591 @end defun
592
593 @defun set-char-table-parent char-table new-parent
594 @tindex set-char-table-parent
595 This function sets the parent of @var{char-table} to @var{new-parent}.
596 @end defun
597
598 @defun char-table-extra-slot char-table n
599 @tindex char-table-extra-slot
600 This function returns the contents of extra slot @var{n} of
601 @var{char-table}. The number of extra slots in a char-table is
602 determined by its subtype.
603 @end defun
604
605 @defun set-char-table-extra-slot char-table n value
606 @tindex set-char-table-extra-slot
607 This function stores @var{value} in extra slot @var{n} of
608 @var{char-table}.
609 @end defun
610
611 A char-table can specify an element value for a single character code;
612 it can also specify a value for an entire character set.
613
614 @defun char-table-range char-table range
615 @tindex char-table-range
616 This returns the value specified in @var{char-table} for a range of
617 characters @var{range}. Here are the possibilities for @var{range}:
618
619 @table @asis
620 @item @code{nil}
621 Refers to the default value.
622
623 @item @var{char}
624 Refers to the element for character @var{char}
625 (supposing @var{char} is a valid character code).
626
627 @item @var{charset}
628 Refers to the value specified for the whole character set
629 @var{charset} (@pxref{Character Sets}).
630
631 @item @var{generic-char}
632 A generic character stands for a character set; specifying the generic
633 character as argument is equivalent to specifying the character set
634 name. @xref{Splitting Characters}, for a description of generic characters.
635 @end table
636 @end defun
637
638 @defun set-char-table-range char-table range value
639 @tindex set-char-table-range
640 This function sets the value in @var{char-table} for a range of
641 characters @var{range}. Here are the possibilities for @var{range}:
642
643 @table @asis
644 @item @code{nil}
645 Refers to the default value.
646
647 @item @code{t}
648 Refers to the whole range of character codes.
649
650 @item @var{char}
651 Refers to the element for character @var{char}
652 (supposing @var{char} is a valid character code).
653
654 @item @var{charset}
655 Refers to the value specified for the whole character set
656 @var{charset} (@pxref{Character Sets}).
657
658 @item @var{generic-char}
659 A generic character stands for a character set; specifying the generic
660 character as argument is equivalent to specifying the character set
661 name. @xref{Splitting Characters}, for a description of generic characters.
662 @end table
663 @end defun
664
665 @defun map-char-table function char-table
666 @tindex map-char-table
667 This function calls @var{function} for each element of @var{char-table}.
668 @var{function} is called with two arguments, a key and a value. The key
669 is a possible @var{range} argument for @code{char-table-range}---either
670 a valid character or a generic character---and the value is
671 @code{(char-table-range @var{char-table} @var{key})}.
672
673 Overall, the key-value pairs passed to @var{function} describe all the
674 values stored in @var{char-table}.
675
676 The return value is always @code{nil}; to make this function useful,
677 @var{function} should have side effects. For example,
678 here is how to examine each element of the syntax table:
679
680 @example
681 (let (accumulator)
682 (map-char-table
683 #'(lambda (key value)
684 (setq accumulator
685 (cons (list key value) accumulator)))
686 (syntax-table))
687 accumulator)
688 @result{}
689 ((475008 nil) (474880 nil) (474752 nil) (474624 nil)
690 ... (5 (3)) (4 (3)) (3 (3)) (2 (3)) (1 (3)) (0 (3)))
691 @end example
692 @end defun
693
694 @node Bool-Vectors
695 @section Bool-vectors
696 @cindex Bool-vectors
697
698 A bool-vector is much like a vector, except that it stores only the
699 values @code{t} and @code{nil}. If you try to store any non-@code{nil}
700 value into an element of the bool-vector, the effect is to store
701 @code{t} there. As with all arrays, bool-vector indices start from 0,
702 and the length cannot be changed once the bool-vector is created.
703 Bool-vectors are constants when evaluated.
704
705 There are two special functions for working with bool-vectors; aside
706 from that, you manipulate them with same functions used for other kinds
707 of arrays.
708
709 @defun make-bool-vector length initial
710 @tindex make-bool-vector
711 Return a new book-vector of @var{length} elements,
712 each one initialized to @var{initial}.
713 @end defun
714
715 @defun bool-vector-p object
716 @tindex bool-vector-p
717 This returns @code{t} if @var{object} is a bool-vector,
718 and @code{nil} otherwise.
719 @end defun
720