2 @c This is part of the SXEmacs 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 Copyright (C) 2005 Sebastian Freundt <hroptatyr@sxemacs.org>
6 @c See the file lispref.texi for copying conditions.
7 @setfilename ../../info/sequences.info
9 @node Sequences Arrays Vectors, Symbols, Lists, Top
10 @chapter Sequences, Arrays, and Vectors
13 Recall that the @dfn{sequence} type is the union of five other Lisp
14 types: lists, double-linked lists, vectors, bit vectors, and strings.
15 In other words, any list is a sequence, any dllist is a sequence, any
16 vector is a sequence, any bit vector is a sequence, and any string is
17 a sequence. The common property that all sequences have is that each
18 is an ordered collection of elements.
20 An @dfn{array} is a single primitive object that has a slot for each
21 elements. All the elements are accessible in constant time, but the
22 length of an existing array cannot be changed. Strings, vectors, and
23 bit vectors are the three types of arrays.
25 A list (or dllist) is a sequence of elements, but it is not a single
26 primitive object; it is made of cons cells, one cell per element.
27 Finding the @var{n}th element requires looking through @var{n} cons
28 cells, so elements farther from the beginning of the list take longer
29 to access. But it is possible to add elements to the list, or remove
32 The following diagram shows the relationship between these types:
36 ___________________________________
39 | ______ ______________________ |
41 | | List | | Array | |
42 | | | | ________ _______ | |
43 | |______| | | | | | | |
44 | | | Vector | | String| | |
45 | ______ | |________| |_______| | |
46 | | | | __________________ | |
48 | | List | | | Bit Vector | | |
49 | |______| | |__________________| | |
50 | |______________________| |
51 |___________________________________|
55 The elements of vectors, lists and dllists may be any Lisp objects.
56 The elements of strings are all characters. The elements of bit vectors
57 are the numbers 0 and 1.
60 * Sequence Functions:: Functions that accept any kind of sequence.
61 * Arrays:: Characteristics of arrays in SXEmacs Lisp.
62 * Array Functions:: Functions specifically for arrays.
63 * Vectors:: Special characteristics of SXEmacs Lisp vectors.
64 * Vector Functions:: Functions specifically for vectors.
65 * Bit Vectors:: Special characteristics of SXEmacs Lisp bit vectors.
66 * Bit Vector Functions:: Functions specifically for bit vectors.
70 @node Sequence Functions
73 In SXEmacs Lisp, a @dfn{sequence} is either a list, a double-linked
74 list, a vector, a bit vector, or a string. The common property that
75 all sequences have is that each is an ordered collection of elements.
76 This section describes functions that accept any kind of sequence.
78 @defun sequencep object
79 Returns @code{t} if @var{object} is a list, dllist, vector, bit
80 vector, or string, @code{nil} otherwise.
83 @defun copy-sequence sequence
84 @cindex copying sequences
85 Returns a copy of @var{sequence}. The copy is the same type of object
86 as the original sequence, and it has the same elements in the same order.
88 Storing a new element into the copy does not affect the original
89 @var{sequence}, and vice versa. However, the elements of the new
90 sequence are not copies; they are identical (@code{eq}) to the elements
91 of the original. Therefore, changes made within these elements, as
92 found via the copied sequence, are also visible in the original
95 If the sequence is a string with extents or text properties, the extents
96 and text properties in the copy are also copied, not shared with the
97 original. (This means that modifying the extents or text properties of
98 the original will not affect the copy.) However, the actual values of
99 the properties are shared. @xref{Extents}, @xref{Text Properties}.
101 See also @code{append} in @ref{Building Lists}, @code{concat} in
102 @ref{Creating Strings}, @code{vconcat} in @ref{Vectors}, and
103 @code{bvconcat} in @ref{Bit Vectors}, for other ways to copy sequences.
111 (setq x (vector 'foo bar))
112 @result{} [foo (1 2)]
115 (setq y (copy-sequence x))
116 @result{} [foo (1 2)]
128 (eq (elt x 1) (elt y 1))
133 ;; @r{Replacing an element of one sequence.}
135 x @result{} [quux (1 2)]
136 y @result{} [foo (1 2)]
140 ;; @r{Modifying the inside of a shared element.}
141 (setcar (aref x 1) 69)
142 x @result{} [quux (69 2)]
143 y @result{} [foo (69 2)]
147 ;; @r{Creating a bit vector.}
148 (bit-vector 1 0 1 1 0 1 0 0)
154 @defun length sequence
155 @cindex string length
157 @cindex dllist length
158 @cindex vector length
159 @cindex bit vector length
160 @cindex sequence length
161 Returns the number of elements in @var{sequence}. If @var{sequence} is
162 a cons cell that is not a list (because the final @sc{cdr} is not
163 @code{nil}), a @code{wrong-type-argument} error is signaled.
175 (length (dllist 2 4))
193 @defun elt sequence index
194 @cindex elements of sequences
195 This function returns the element of @var{sequence} indexed by
196 @var{index}. Legitimate values of @var{index} are integers ranging from
197 0 up to one less than the length of @var{sequence}. If @var{sequence}
198 is a list, then out-of-range values of @var{index} return @code{nil};
199 otherwise, they trigger an @code{args-out-of-range} error.
211 (elt (dllist 1 2 3 4) 2)
215 (char-to-string (elt "1234" 2))
224 @error{}Args out of range: [1 2 3 4], 4
228 @error{}Args out of range: [1 2 3 4], -1
232 This function generalizes @code{aref} (@pxref{Array Functions}) and
233 @code{nth} (@pxref{List Elements}).
241 An @dfn{array} object has slots that hold a number of other Lisp
242 objects, called the elements of the array. Any element of an array may
243 be accessed in constant time. In contrast, an element of a list
244 requires access time that is proportional to the position of the element
247 When you create an array, you must specify how many elements it has.
248 The amount of space allocated depends on the number of elements.
249 Therefore, it is impossible to change the size of an array once it is
250 created; you cannot add or remove elements. However, you can replace an
251 element with a different value.
253 SXEmacs defines three types of array, all of which are one-dimensional:
254 @dfn{strings}, @dfn{vectors}, and @dfn{bit vectors}. A vector is a
255 general array; its elements can be any Lisp objects. A string is a
256 specialized array; its elements must be characters. A bit vector is
257 another specialized array; its elements must be bits (an integer, either
258 0 or 1). Each type of array has its own read syntax. @xref{String
259 Type}, @ref{Vector Type}, and @ref{Bit Vector Type}.
261 All kinds of array share these characteristics:
265 The first element of an array has index zero, the second element has
266 index 1, and so on. This is called @dfn{zero-origin} indexing. For
267 example, an array of four elements has indices 0, 1, 2, @w{and 3}.
270 The elements of an array may be referenced or changed with the functions
271 @code{aref} and @code{aset}, respectively (@pxref{Array Functions}).
274 In principle, if you wish to have an array of text characters, you
275 could use either a string or a vector. In practice, we always choose
276 strings for such applications, for four reasons:
280 They usually occupy one-fourth the space of a vector of the same
281 elements. (This is one-eighth the space for 64-bit machines such as the
282 DEC Alpha, and may also be different when @sc{mule} support is compiled
286 Strings are printed in a way that shows the contents more clearly
290 Strings can hold extent and text properties. @xref{Extents}, @xref{Text
294 Many of the specialized editing and I/O facilities of SXEmacs accept only
295 strings. For example, you cannot insert a vector of characters into a
296 buffer the way you can insert a string. @xref{Strings and Characters}.
299 By contrast, for an array of keyboard input characters (such as a key
300 sequence), a vector may be necessary, because many keyboard input
301 characters are non-printable and are represented with symbols rather than
302 with characters. @xref{Key Sequence Input}.
304 Similarly, when representing an array of bits, a bit vector has
305 the following advantages over a regular vector:
309 They occupy 1/32nd the space of a vector of the same elements.
310 (1/64th on 64-bit machines such as the DEC Alpha.)
313 Bit vectors are printed in a way that shows the contents more clearly
318 @node Array Functions
319 @section Functions that Operate on Arrays
321 In this section, we describe the functions that accept strings, vectors,
325 This function returns @code{t} if @var{object} is an array (i.e., a
326 string, vector, or bit vector).
340 @defun aref array index
341 @cindex array elements
342 This function returns the @var{index}th element of @var{array}. The
343 first element is at index zero.
347 (setq primes [2 3 5 7 11 13])
348 @result{} [2 3 5 7 11 13]
366 See also the function @code{elt}, in @ref{Sequence Functions}.
369 @defun aset array index object
370 This function sets the @var{index}th element of @var{array} to be
371 @var{object}. It returns @var{object}.
375 (setq w [foo bar baz])
376 @result{} [foo bar baz]
380 @result{} [fu bar baz]
402 If @var{array} is a string and @var{object} is not a character, a
403 @code{wrong-type-argument} error results.
406 @defun fillarray array object
407 This function fills the array @var{array} with @var{object}, so that
408 each element of @var{array} is @var{object}. It returns @var{array}.
412 (setq a [a b c d e f g])
413 @result{} [a b c d e f g]
415 @result{} [0 0 0 0 0 0 0]
417 @result{} [0 0 0 0 0 0 0]
421 (setq s "When in the course")
422 @result{} "When in the course"
424 @result{} "------------------"
435 If @var{array} is a string and @var{object} is not a character, a
436 @code{wrong-type-argument} error results.
439 The general sequence functions @code{copy-sequence} and @code{length}
440 are often useful for objects known to be arrays. @xref{Sequence Functions}.
447 Arrays in Lisp, like arrays in most languages, are blocks of memory
448 whose elements can be accessed in constant time. A @dfn{vector} is a
449 general-purpose array; its elements can be any Lisp objects. (The other
450 kind of array in SXEmacs Lisp is the @dfn{string}, whose elements must be
451 characters.) Vectors in SXEmacs serve as obarrays (vectors of symbols),
452 although this is a shortcoming that should be fixed. They are also used
453 internally as part of the representation of a byte-compiled function; if
454 you print such a function, you will see a vector in it.
456 In SXEmacs Lisp, the indices of the elements of a vector start from zero
457 and count up from there.
459 Vectors are printed with square brackets surrounding the elements.
460 Thus, a vector whose elements are the symbols @code{a}, @code{b} and
461 @code{a} is printed as @code{[a b a]}. You can write vectors in the
462 same way in Lisp input.
464 A vector, like a string or a number, is considered a constant for
465 evaluation: the result of evaluating it is the same vector. This does
466 not evaluate or even examine the elements of the vector.
467 @xref{Self-Evaluating Forms}.
469 Here are examples of these principles:
473 (setq avector [1 two '(three) "four" [five]])
474 @result{} [1 two (quote (three)) "four" [five]]
476 @result{} [1 two (quote (three)) "four" [five]]
477 (eq avector (eval avector))
483 @node Vector Functions
484 @section Functions That Operate on Vectors
486 Here are some functions that relate to vectors:
488 @defun vectorp object
489 This function returns @code{t} if @var{object} is a vector.
501 @defun vector &rest objects
502 This function creates and returns a vector whose elements are the
503 arguments, @var{objects}.
507 (vector 'foo 23 [bar baz] "rats")
508 @result{} [foo 23 [bar baz] "rats"]
515 @defun make-vector length object
516 This function returns a new vector consisting of @var{length} elements,
517 each initialized to @var{object}.
521 (setq sleepy (make-vector 9 'Z))
522 @result{} [Z Z Z Z Z Z Z Z Z]
527 @defun vconcat &rest sequences
528 @cindex copying vectors
529 This function returns a new vector containing all the elements of the
530 @var{sequences}. The arguments @var{sequences} may be lists, vectors,
531 or strings. If no @var{sequences} are given, an empty vector is
534 The value is a newly constructed vector that is not @code{eq} to any
539 (setq a (vconcat '(A B C) '(D E F)))
540 @result{} [A B C D E F]
547 (vconcat [A B C] "aa" '(foo (6 7)))
548 @result{} [A B C 97 97 foo (6 7)]
552 The @code{vconcat} function also allows integers as arguments. It
553 converts them to strings of digits, making up the decimal print
554 representation of the integer, and then uses the strings instead of the
555 original integers. @strong{Don't use this feature; we plan to eliminate
556 it. If you already use this feature, change your programs now!} The
557 proper way to convert an integer to a decimal number in this way is with
558 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
559 (@pxref{String Conversion}).
561 For other concatenation functions, see @code{mapconcat} in @ref{Mapping
562 Functions}, @code{concat} in @ref{Creating Strings}, @code{append}
563 in @ref{Building Lists}, and @code{bvconcat} in @ref{Bit Vector Functions}.
566 The @code{append} function provides a way to convert a vector into a
567 list with the same elements (@pxref{Building Lists}):
571 (setq avector [1 two (quote (three)) "four" [five]])
572 @result{} [1 two (quote (three)) "four" [five]]
574 @result{} (1 two (quote (three)) "four" [five])
583 Bit vectors are specialized vectors that can only represent arrays
584 of 1's and 0's. Bit vectors have a very efficient representation
585 and are useful for representing sets of boolean (true or false) values.
587 There is no limit on the size of a bit vector. You could, for example,
588 create a bit vector with 100,000 elements if you really wanted to.
590 Bit vectors have a special printed representation consisting of
591 @samp{#*} followed by the bits of the vector. For example, a bit vector
592 whose elements are 0, 1, 1, 0, and 1, respectively, is printed as
598 Bit vectors are considered constants for evaluation, like vectors,
599 strings, and numbers. @xref{Self-Evaluating Forms}.
602 @node Bit Vector Functions
603 @section Functions That Operate on Bit Vectors
605 Here are some functions that relate to bit vectors:
607 @defun bit-vector-p object
608 This function returns @code{t} if @var{object} is a bit vector.
623 This function returns @code{t} if @var{object} is either 0 or 1.
626 @defun bit-vector &rest bits
627 This function creates and returns a bit vector whose elements are the
628 arguments @var{bits}. Each argument must be a bit, i.e. one of the two
633 (bit-vector 0 0 0 1 0 0 0 0 1 0)
634 @result{} #*0001000010
641 @defun make-bit-vector length bit
642 This function creates and returns a bit vector consisting of
643 @var{length} elements, each initialized to @var{bit}, which must be
644 one of the two integers 0 or 1.
648 (setq picket-fence (make-bit-vector 9 1))
649 @result{} #*111111111
654 @defun bvconcat &rest sequences
655 @cindex copying bit vectors
656 This function returns a new bit vector containing all the elements of
657 the @var{sequences}. The arguments @var{sequences} may be lists,
658 vectors, or bit vectors, all of whose elements are the integers 0 or 1.
659 If no @var{sequences} are given, an empty bit vector is returned.
661 The value is a newly constructed bit vector that is not @code{eq} to any
666 (setq a (bvconcat '(1 1 0) '(0 0 1)))
674 (bvconcat [1 0 0 0 0] #*111 '(0 0 0 0 1))
675 @result{} #*1000011100001
679 For other concatenation functions, see @code{mapconcat} in @ref{Mapping
680 Functions}, @code{concat} in @ref{Creating Strings}, @code{vconcat} in
681 @ref{Vector Functions}, and @code{append} in @ref{Building Lists}.
684 The @code{append} function provides a way to convert a bit vector into a
685 list with the same elements (@pxref{Building Lists}):
692 @result{} (0 0 0 0 1 1 1 0)