Sequences, Arrays, and Vectors
******************************

The sequence type is the union of two other Lisp types: lists and arrays.  In other words, any list is a sequence, and any array is a sequence.  The common property that all sequences have is that each is an ordered collection of elements.

An array is a fixed-length object with a slot for each of its elements.  All the elements are accessible in constant time.  The four types of arrays are strings, vectors, char-tables and bool-vectors.

A list is a sequence of elements, but it is not a single primitive object; it is made of cons cells, one cell per element.  Finding the Nth element requires looking through N cons cells, so elements farther from the beginning of the list take longer to access. But it is possible to add elements to the list, or remove elements.

The following diagram shows the relationship between these types:

               _____________________________________________
              |                                             |
              |          Sequence                           |
              |  ______   ________________________________  |
              | |      | |                                | |
              | | List | |             Array              | |
              | |      | |    ________       ________     | |
              | |______| |   |        |     |        |    | |
              |          |   | Vector |     | String |    | |
              |          |   |________|     |________|    | |
              |          |  ____________   _____________  | |
              |          | |            | |             | | |
              |          | | Char-table | | Bool-vector | | |
              |          | |____________| |_____________| | |
              |          |________________________________| |
              |_____________________________________________|

Sequences
=========

This section describes functions that accept any kind of sequence.

 -- Function: sequencep object
     This function returns t if OBJECT is a list, vector, string, bool-vector, or char-table, nil otherwise.  See also seqp below.

 -- Function: length sequence
     This function returns the number of elements in SEQUENCE.  The function signals the wrong-type-argument error if the argument is not a sequence or is a dotted list; it signals the circular-list error if the argument is a circular list.  For a char-table, the value returned is always one more than the maximum Emacs character code.

     See Definition of safe-length, for the related function safe-length.

          (length '(1 2 3))
              => 3

          (length ())
              => 0

          (length "foobar")
              => 6

          (length [1 2 3])
              => 3

          (length (make-bool-vector 5 nil))
              => 5

See also string-bytes, in Text Representations.

If you need to compute the width of a string on display, you should use string-width (see Size of Displayed Text), not length, since length only counts the number of characters, but does not account for the display width of each character.

 -- Function: elt sequence index
     This function returns the element of SEQUENCE indexed by INDEX.  Legitimate values of INDEX are integers ranging from 0 up to one less than the length of SEQUENCE.  If SEQUENCE is a list, out-of-range values behave as for nth.  See Definition of nth.  Otherwise, out-of-range values trigger an args-out-of-range error.

          (elt [1 2 3 4] 2)
               => 3

          (elt '(1 2 3 4) 2)
               => 3

          ;; We use string to show clearly which character elt returns.
          (string (elt "1234" 2))
               => "3"

          (elt [1 2 3 4] 4)
               error--> Args out of range: [1 2 3 4], 4

          (elt [1 2 3 4] -1)
               error--> Args out of range: [1 2 3 4], -1

     This function generalizes aref (see Array Functions) and nth (see Definition of nth).

 -- Function: copy-sequence seqr
     This function returns a copy of SEQR, which should be either a sequence or a record.  The copy is the same type of object as the original, and it has the same elements in the same order.  However, if SEQR is empty, like a string or a vector of zero length, the value returned by this function might not be a copy, but an empty object of the same type and identical to SEQR.

     Storing a new element into the copy does not affect the original SEQR, and vice versa.  However, the elements of the copy are not copies; they are identical (eq) to the elements of the original.  Therefore, changes made within these elements, as found via the copy, are also visible in the original.

     If the argument is a string with text properties, the property list in the copy is itself a copy, not shared with the original's property list.  However, the actual values of the properties are shared. See Text Properties.

     This function does not work for dotted lists.  Trying to copy a circular list may cause an infinite loop.

     See also append in Building Lists, concat in Creating Strings, and vconcat in Vector Functions, for other ways to copy sequences.

          (setq bar (list 1 2))
               => (1 2)

          (setq x (vector 'foo bar))
               => [foo (1 2)]

          (setq y (copy-sequence x))
               => [foo (1 2)]

          (eq x y)
               => nil

          (equal x y)
               => t

          (eq (elt x 1) (elt y 1))
               => t

          ;; Replacing an element of one sequence.
          (aset x 0 'quux)
          x => [quux (1 2)]
          y => [foo (1 2)]

          ;; Modifying the inside of a shared element.
          (setcar (aref x 1) 69)
          x => [quux (69 2)]
          y => [foo (69 2)]

 -- Function: reverse sequence
     This function creates a new sequence whose elements are the elements of SEQUENCE, but in reverse order.  The original argument SEQUENCE is not altered.  Note that char-tables cannot be reversed.

          (setq x '(1 2 3 4))
               => (1 2 3 4)

          (reverse x)
               => (4 3 2 1)
          x
               => (1 2 3 4)

          (setq x [1 2 3 4])
               => [1 2 3 4]

          (reverse x)
               => [4 3 2 1]
          x
               => [1 2 3 4]

          (setq x "xyzzy")
               => "xyzzy"

          (reverse x)
               => "yzzyx"
          x
               => "xyzzy"

 -- Function: nreverse sequence
     This function reverses the order of the elements of SEQUENCE. Unlike reverse the original SEQUENCE may be modified.

     For example:

          (setq x (list 'a 'b 'c))
               => (a b c)

          x
               => (a b c)
          (nreverse x)
               => (c b a)

          ;; The cons cell that was first is now last.
          x
               => (a)

     To avoid confusion, we usually store the result of nreverse back in the same variable which held the original list:

          (setq x (nreverse x))

     Here is the nreverse of our favorite example, (a b c), presented graphically:

          Original list head:                       Reversed list:
           -------------        -------------        ------------
          | car  | cdr  |      | car  | cdr  |      | car | cdr  |
          |   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
          |      |      |   |  |      |   |  |   |  |     |   |  |
           -------------    |   --------- | -    |   -------- | -
                            |             |      |            |
                             -------------        ------------

     For the vector, it is even simpler because you don't need setq:

          (setq x (copy-sequence [1 2 3 4]))
               => [1 2 3 4]
          (nreverse x)
               => [4 3 2 1]
          x
               => [4 3 2 1]

     Note that unlike reverse, this function doesn't work with strings. Although you can alter string data by using aset, it is strongly encouraged to treat strings as immutable even when they are mutable. See Mutability.

 -- Function: sort sequence predicate
     This function sorts SEQUENCE stably.  Note that this function doesn't work for all sequences; it may be used only for lists and vectors.  If SEQUENCE is a list, it is modified destructively.  This functions returns the sorted SEQUENCE and compares elements using PREDICATE.  A stable sort is one in which elements with equal sort keys maintain their relative order before and after the sort.  Stability is important when successive sorts are used to order elements according to different criteria.

     The argument PREDICATE must be a function that accepts two arguments.  It is called with two elements of SEQUENCE.  To get an increasing order sort, the PREDICATE should return non-nil if the first element is ``less'' than the second, or nil if not.

     The comparison function PREDICATE must give reliable results for any given pair of arguments, at least within a single call to sort.  It must be antisymmetric; that is, if A is less than B, B must not be less than A.  It must be transitive---that is, if A is less than B, and B is less than C, then A must be less than C.  If you use a comparison function which does not meet these requirements, the result of sort is unpredictable.

     The destructive aspect of sort for lists is that it rearranges the cons cells forming SEQUENCE by changing CDRs.  A nondestructive sort function would create new cons cells to store the elements in their sorted order.  If you wish to make a sorted copy without destroying the original, copy it first with copy-sequence and then sort.

     Sorting does not change the CARs of the cons cells in SEQUENCE; the cons cell that originally contained the element a in SEQUENCE still has a in its CAR after sorting, but it now appears in a different position in the list due to the change of CDRs.  For example:

          (setq nums (list 1 3 2 6 5 4 0))
               => (1 3 2 6 5 4 0)

          (sort nums #'<)
               => (0 1 2 3 4 5 6)

          nums
               => (1 2 3 4 5 6)

     Warning: Note that the list in nums no longer contains 0; this is the same cons cell that it was before, but it is no longer the first one in the list.  Don't assume a variable that formerly held the argument now holds the entire sorted list!  Instead, save the result of sort and use that.  Most often we store the result back into the variable that held the original list:

          (setq nums (sort nums #'<))

     For the better understanding of what stable sort is, consider the following vector example.  After sorting, all items whose car is 8 are grouped at the beginning of vector, but their relative order is preserved. All items whose car is 9 are grouped at the end of vector, but their relative order is also preserved:

          (setq
            vector
            (vector '(8 . "xxx") '(9 . "aaa") '(8 . "bbb") '(9 . "zzz")
                    '(9 . "ppp") '(8 . "ttt") '(8 . "eee") '(9 . "fff")))
               => [(8 . "xxx") (9 . "aaa") (8 . "bbb") (9 . "zzz")
                   (9 . "ppp") (8 . "ttt") (8 . "eee") (9 . "fff")]

          (sort vector (lambda (x y) (< (car x) (car y))))
               => [(8 . "xxx") (8 . "bbb") (8 . "ttt") (8 . "eee")
                   (9 . "aaa") (9 . "zzz") (9 . "ppp") (9 . "fff")]

     See Sorting, for more functions that perform sorting. See documentation in Accessing Documentation, for a useful example of sort.

The seq.el library provides the following additional sequence manipulation macros and functions, prefixed with seq-.  To use them, you must first load the seq library.

All functions defined in this library are free of side-effects; i.e., they do not modify any sequence (list, vector, or string) that you pass as an argument.  Unless otherwise stated, the result is a sequence of the same type as the input.  For those functions that take a predicate, this should be a function of one argument.

The seq.el library can be extended to work with additional types of sequential data-structures.  For that purpose, all functions are defined using cl-defgeneric.  See Generic Functions, for more details about using cl-defgeneric for adding extensions.

 -- Function: seq-elt sequence index
     This function returns the element of SEQUENCE at the specified INDEX, which is an integer whose valid value range is zero to one less than the length of SEQUENCE.  For out-of-range values on built-in sequence types, seq-elt behaves like elt. For the details, see Definition of elt.

          (seq-elt [1 2 3 4] 2)
          => 3

     seq-elt returns places settable using setf (see Setting Generalized Variables).

          (setq vec [1 2 3 4])
          (setf (seq-elt vec 2) 5)
          vec
          => [1 2 5 4]

 -- Function: seq-length sequence
     This function returns the number of elements in SEQUENCE.  For built-in sequence types, seq-length behaves like length. See Definition of length.

 -- Function: seqp object
     This function returns non-nil if OBJECT is a sequence (a list or array), or any additional type of sequence defined via seq.el generic functions.  This is an extensible variant of sequencep.

          (seqp [1 2])
          => t

          (seqp 2)
          => nil

 -- Function: seq-drop sequence n
     This function returns all but the first N (an integer) elements of SEQUENCE.  If N is negative or zero, the result is SEQUENCE.

          (seq-drop [1 2 3 4 5 6] 3)
          => [4 5 6]

          (seq-drop "hello world" -4)
          => "hello world"

 -- Function: seq-take sequence n
     This function returns the first N (an integer) elements of SEQUENCE.  If N is negative or zero, the result is nil.

          (seq-take '(1 2 3 4) 3)
          => (1 2 3)

          (seq-take [1 2 3 4] 0)
          => []

 -- Function: seq-take-while predicate sequence
     This function returns the members of SEQUENCE in order, stopping before the first one for which PREDICATE returns nil.

          (seq-take-while (lambda (elt) (> elt 0)) '(1 2 3 -1 -2))
          => (1 2 3)

          (seq-take-while (lambda (elt) (> elt 0)) [-1 4 6])
          => []

 -- Function: seq-drop-while predicate sequence
     This function returns the members of SEQUENCE in order, starting from the first one for which PREDICATE returns nil.

          (seq-drop-while (lambda (elt) (> elt 0)) '(1 2 3 -1 -2))
          => (-1 -2)

          (seq-drop-while (lambda (elt) (< elt 0)) [1 4 6])
          => [1 4 6]

 -- Function: seq-do function sequence
     This function applies FUNCTION to each element of SEQUENCE in turn (presumably for side effects), and returns SEQUENCE.

 -- Function: seq-map function sequence
     This function returns the result of applying FUNCTION to each element of SEQUENCE.  The returned value is a list.

          (seq-map #'1+ '(2 4 6))
          => (3 5 7)

          (seq-map #'symbol-name [foo bar])
          => ("foo" "bar")

 -- Function: seq-map-indexed function sequence
     This function returns the result of applying FUNCTION to each element of SEQUENCE and its index within SEQ.  The returned value is a list.

          (seq-map-indexed (lambda (elt idx)
                             (list idx elt))
                           '(a b c))
          => ((0 a) (b 1) (c 2))

 -- Function: seq-mapn function &rest sequences
     This function returns the result of applying FUNCTION to each element of SEQUENCES.  The arity (see subr-arity) of FUNCTION must match the number of sequences. Mapping stops at the end of the shortest sequence, and the returned value is a list.

          (seq-mapn #'+ '(2 4 6) '(20 40 60))
          => (22 44 66)

          (seq-mapn #'concat '("moskito" "bite") ["bee" "sting"])
          => ("moskitobee" "bitesting")

 -- Function: seq-filter predicate sequence
     This function returns a list of all the elements in SEQUENCE for which PREDICATE returns non-nil.

          (seq-filter (lambda (elt) (> elt 0)) [1 -1 3 -3 5])
          => (1 3 5)

          (seq-filter (lambda (elt) (> elt 0)) '(-1 -3 -5))
          => nil

 -- Function: seq-remove predicate sequence
     This function returns a list of all the elements in SEQUENCE for which PREDICATE returns nil.

          (seq-remove (lambda (elt) (> elt 0)) [1 -1 3 -3 5])
          => (-1 -3)

          (seq-remove (lambda (elt) (< elt 0)) '(-1 -3 -5))
          => nil

 -- Function: seq-reduce function sequence initial-value
     This function returns the result of calling FUNCTION with INITIAL-VALUE and the first element of SEQUENCE, then calling FUNCTION with that result and the second element of SEQUENCE, then with that result and the third element of SEQUENCE, etc. FUNCTION should be a function of two arguments.  If SEQUENCE is empty, this returns INITIAL-VALUE without calling FUNCTION.

          (seq-reduce #'+ [1 2 3 4] 0)
          => 10

          (seq-reduce #'+ '(1 2 3 4) 5)
          => 15

          (seq-reduce #'+ '() 3)
          => 3

 -- Function: seq-some predicate sequence
     This function returns the first non-nil value returned by applying PREDICATE to each element of SEQUENCE in turn.

          (seq-some #'numberp ["abc" 1 nil])
          => t

          (seq-some #'numberp ["abc" "def"])
          => nil

          (seq-some #'null ["abc" 1 nil])
          => t

          (seq-some #'1+ [2 4 6])
          => 3

 -- Function: seq-find predicate sequence &optional default
     This function returns the first element in SEQUENCE for which PREDICATE returns non-nil.  If no element matches PREDICATE, the function returns DEFAULT.

     Note that this function has an ambiguity if the found element is identical to DEFAULT, as in that case it cannot be known whether an element was found or not.

          (seq-find #'numberp ["abc" 1 nil])
          => 1

          (seq-find #'numberp ["abc" "def"])
          => nil

 -- Function: seq-every-p predicate sequence
     This function returns non-nil if applying PREDICATE to every element of SEQUENCE returns non-nil.

          (seq-every-p #'numberp [2 4 6])
          => t

          (seq-every-p #'numberp [2 4 "6"])
          => nil

 -- Function: seq-empty-p sequence
     This function returns non-nil if SEQUENCE is empty.

          (seq-empty-p "not empty")
          => nil

          (seq-empty-p "")
          => t

 -- Function: seq-count predicate sequence
     This function returns the number of elements in SEQUENCE for which PREDICATE returns non-nil.

          (seq-count (lambda (elt) (> elt 0)) [-1 2 0 3 -2])
          => 2

 -- Function: seq-sort function sequence
     This function returns a copy of SEQUENCE that is sorted according to FUNCTION, a function of two arguments that returns non-nil if the first argument should sort before the second.

 -- Function: seq-sort-by function predicate sequence
     This function is similar to seq-sort, but the elements of SEQUENCE are transformed by applying FUNCTION on them before being sorted.  FUNCTION is a function of one argument.

          (seq-sort-by #'seq-length #'> ["a" "ab" "abc"])
          => ["abc" "ab" "a"]

 -- Function: seq-contains-p sequence elt &optional function
     This function returns non-nil if at least one element in SEQUENCE is equal to ELT.  If the optional argument FUNCTION is non-nil, it is a function of two arguments to use instead of the default equal.

          (seq-contains '(symbol1 symbol2) 'symbol1)
          => symbol1

          (seq-contains '(symbol1 symbol2) 'symbol3)
          => nil

 -- Function: seq-set-equal-p sequence1 sequence2 &optional testfn
     This function checks whether SEQUENCE1 and SEQUENCE2 contain the same elements, regardless of the order. If the optional argument TESTFN is non-nil, it is a function of two arguments to use instead of the default equal.

          (seq-set-equal-p '(a b c) '(c b a))
          => t

          (seq-set-equal-p '(a b c) '(c b))
          => nil

          (seq-set-equal-p '("a" "b" "c") '("c" "b" "a"))
          => t

          (seq-set-equal-p '("a" "b" "c") '("c" "b" "a") #'eq)
          => nil

 -- Function: seq-position sequence elt &optional function
     This function returns the index of the first element in SEQUENCE that is equal to ELT.  If the optional argument FUNCTION is non-nil, it is a function of two arguments to use instead of the default equal.

          (seq-position '(a b c) 'b)
          => 1

          (seq-position '(a b c) 'd)
          => nil

 -- Function: seq-uniq sequence &optional function
     This function returns a list of the elements of SEQUENCE with duplicates removed.  If the optional argument FUNCTION is non-nil, it is a function of two arguments to use instead of the default equal.

          (seq-uniq '(1 2 2 1 3))
          => (1 2 3)

          (seq-uniq '(1 2 2.0 1.0) #'=)
          => (1 2)

 -- Function: seq-subseq sequence start &optional end
     This function returns a subset of SEQUENCE from START to END, both integers (END defaults to the last element). If START or END is negative, it counts from the end of SEQUENCE.

          (seq-subseq '(1 2 3 4 5) 1)
          => (2 3 4 5)

          (seq-subseq '[1 2 3 4 5] 1 3)
          => [2 3]

          (seq-subseq '[1 2 3 4 5] -3 -1)
          => [3 4]

 -- Function: seq-concatenate type &rest sequences
     This function returns a sequence of type TYPE made of the concatenation of SEQUENCES.  TYPE may be: vector, list or string.

          (seq-concatenate 'list '(1 2) '(3 4) [5 6])
          => (1 2 3 4 5 6)

          (seq-concatenate 'string "Hello " "world")
          => "Hello world"

 -- Function: seq-mapcat function sequence &optional type
     This function returns the result of applying seq-concatenate to the result of applying FUNCTION to each element of SEQUENCE.  The result is a sequence of type TYPE, or a list if TYPE is nil.

          (seq-mapcat #'seq-reverse '((3 2 1) (6 5 4)))
          => (1 2 3 4 5 6)

 -- Function: seq-partition sequence n
     This function returns a list of the elements of SEQUENCE grouped into sub-sequences of length N.  The last sequence may contain less elements than N.  N must be an integer.  If N is a negative integer or 0, the return value is nil.

          (seq-partition '(0 1 2 3 4 5 6 7) 3)
          => ((0 1 2) (3 4 5) (6 7))

 -- Function: seq-intersection sequence1 sequence2 &optional function
     This function returns a list of the elements that appear both in SEQUENCE1 and SEQUENCE2.  If the optional argument FUNCTION is non-nil, it is a function of two arguments to use to compare elements instead of the default equal.

          (seq-intersection [2 3 4 5] [1 3 5 6 7])
          => (3 5)

 -- Function: seq-difference sequence1 sequence2 &optional function
     This function returns a list of the elements that appear in SEQUENCE1 but not in SEQUENCE2.  If the optional argument FUNCTION is non-nil, it is a function of two arguments to use to compare elements instead of the default equal.

          (seq-difference '(2 3 4 5) [1 3 5 6 7])
          => (2 4)

 -- Function: seq-group-by function sequence
     This function separates the elements of SEQUENCE into an alist whose keys are the result of applying FUNCTION to each element of SEQUENCE.  Keys are compared using equal.

          (seq-group-by #'integerp '(1 2.1 3 2 3.2))
          => ((t 1 3 2) (nil 2.1 3.2))

          (seq-group-by #'car '((a 1) (b 2) (a 3) (c 4)))
          => ((b (b 2)) (a (a 1) (a 3)) (c (c 4)))

 -- Function: seq-into sequence type
     This function converts the sequence SEQUENCE into a sequence of type TYPE.  TYPE can be one of the following symbols: vector, string or list.

          (seq-into [1 2 3] 'list)
          => (1 2 3)

          (seq-into nil 'vector)
          => []

          (seq-into "hello" 'vector)
          => [104 101 108 108 111]

 -- Function: seq-min sequence
     This function returns the smallest element of SEQUENCE.  The elements of SEQUENCE must be numbers or markers (see Markers).

          (seq-min [3 1 2])
          => 1

          (seq-min "Hello")
          => 72

 -- Function: seq-max sequence
     This function returns the largest element of SEQUENCE.  The elements of SEQUENCE must be numbers or markers.

          (seq-max [1 3 2])
          => 3

          (seq-max "Hello")
          => 111

 -- Macro: seq-doseq (var sequence) body...
     This macro is like dolist (see dolist), except that SEQUENCE can be a list, vector or string.  This is primarily useful for side-effects.

 -- Macro: seq-let var-sequence val-sequence body...
     This macro binds the variables defined in VAR-SEQUENCE to the values that are the corresponding elements of VAL-SEQUENCE. This is known as destructuring binding.  The elements of VAR-SEQUENCE can themselves include sequences, allowing for nested destructuring.

     The VAR-SEQUENCE sequence can also include the &rest marker followed by a variable name to be bound to the rest of VAL-SEQUENCE.

          (seq-let [first second] [1 2 3 4]
            (list first second))
          => (1 2)

          (seq-let (_ a _ b) '(1 2 3 4)
            (list a b))
          => (2 4)

          (seq-let [a [b [c]]] [1 [2 [3]]]
            (list a b c))
          => (1 2 3)

          (seq-let [a b &rest others] [1 2 3 4]
            others)

          => [3 4]

     The pcase patterns provide an alternative facility for destructuring binding, see Destructuring with pcase Patterns.

 -- Function: seq-random-elt sequence
     This function returns an element of SEQUENCE taken at random.

          (seq-random-elt [1 2 3 4])
          => 3
          (seq-random-elt [1 2 3 4])
          => 2
          (seq-random-elt [1 2 3 4])
          => 4
          (seq-random-elt [1 2 3 4])
          => 2
          (seq-random-elt [1 2 3 4])
          => 1

     If SEQUENCE is empty, this function signals an error.

Arrays
======

An array object has slots that hold a number of other Lisp objects, called the elements of the array.  Any element of an array may be accessed in constant time.  In contrast, the time to access an element of a list is proportional to the position of that element in the list.

Emacs defines four types of array, all one-dimensional: strings (see String Type), vectors (see Vector Type), bool-vectors (see Bool-Vector Type), and char-tables (see Char-Table Type).  Vectors and char-tables can hold elements of any type, but strings can only hold characters, and bool-vectors can only hold t and nil.

All four kinds of array share these characteristics:

  * The first element of an array has index zero, the second element has index 1, and so on.  This is called zero-origin indexing.  For example, an array of four elements has indices 0, 1, 2, and 3.

  * The length of the array is fixed once you create it; you cannot change the length of an existing array.

  * For purposes of evaluation, the array is a constant---i.e., it evaluates to itself.

  * The elements of an array may be referenced or changed with the functions aref and aset, respectively (see Array Functions).

When you create an array, other than a char-table, you must specify its length.  You cannot specify the length of a char-table, because that is determined by the range of character codes.

In principle, if you want an array of text characters, you could use either a string or a vector.  In practice, we always choose strings for such applications, for four reasons:

  * They occupy one-fourth the space of a vector of the same elements.

  * Strings are printed in a way that shows the contents more clearly as text.

  * Strings can hold text properties.  See Text Properties.

  * Many of the specialized editing and I/O facilities of Emacs accept only strings.  For example, you cannot insert a vector of characters into a buffer the way you can insert a string.  See Strings and Characters.

By contrast, for an array of keyboard input characters (such as a key sequence), a vector may be necessary, because many keyboard input characters are outside the range that will fit in a string.  See Key Sequence Input.

Functions that Operate on Arrays
================================

In this section, we describe the functions that accept all types of arrays.

 -- Function: arrayp object
     This function returns t if OBJECT is an array (i.e., a vector, a string, a bool-vector or a char-table).

          (arrayp [a])
               => t
          (arrayp "asdf")
               => t
          (arrayp (syntax-table))    ;; A char-table.
               => t

 -- Function: aref arr index
     This function returns the INDEXth element of the array or record ARR.  The first element is at index zero.

          (setq primes [2 3 5 7 11 13])
               => [2 3 5 7 11 13]
          (aref primes 4)
               => 11

          (aref "abcdefg" 1)
               => 98           ; b is ASCII code 98.

     See also the function elt, in Sequence Functions.

 -- Function: aset array index object
     This function sets the INDEXth element of ARRAY to be OBJECT.  It returns OBJECT.

          (setq w (vector 'foo 'bar 'baz))
               => [foo bar baz]
          (aset w 0 'fu)
               => fu
          w
               => [fu bar baz]

          ;; copy-sequence copies the string to be modified later.
          (setq x (copy-sequence "asdfasfd"))
               => "asdfasfd"
          (aset x 3 ?Z)
               => 90
          x
               => "asdZasfd"

     The ARRAY should be mutable.  See Mutability.

     If ARRAY is a string and OBJECT is not a character, a wrong-type-argument error results.  The function converts a unibyte string to multibyte if necessary to insert a character.

 -- Function: fillarray array object
     This function fills the array ARRAY with OBJECT, so that each element of ARRAY is OBJECT.  It returns ARRAY.

          (setq a (copy-sequence [a b c d e f g]))
               => [a b c d e f g]
          (fillarray a 0)
               => [0 0 0 0 0 0 0]
          a
               => [0 0 0 0 0 0 0]

          (setq s (copy-sequence "When in the course"))
               => "When in the course"
          (fillarray s ?-)
               => "------------------"

     If ARRAY is a string and OBJECT is not a character, a wrong-type-argument error results.

The general sequence functions copy-sequence and length are often useful for objects known to be arrays.  See Sequence Functions.

Vectors
=======

A vector is a general-purpose array whose elements can be any Lisp objects.  (By contrast, the elements of a string can only be characters.  See Strings and Characters.)  Vectors are used in Emacs for many purposes: as key sequences (see Key Sequences), as symbol-lookup tables (see Creating Symbols), as part of the representation of a byte-compiled function (see Byte Compilation), and more.

Like other arrays, vectors use zero-origin indexing: the first element has index 0.

Vectors are printed with square brackets surrounding the elements. Thus, a vector whose elements are the symbols a, b and a is printed as [a b a].  You can write vectors in the same way in Lisp input.

A vector, like a string or a number, is considered a constant for evaluation: the result of evaluating it is the same vector.  This does not evaluate or even examine the elements of the vector. See Self-Evaluating Forms.  Vectors written with square brackets should not be modified via aset or other destructive operations.  See Mutability.

Here are examples illustrating these principles:

     (setq avector [1 two '(three) "four" [five]])
          => [1 two '(three) "four" [five]]
     (eval avector)
          => [1 two '(three) "four" [five]]
     (eq avector (eval avector))
          => t

Functions for Vectors
=====================

Here are some functions that relate to vectors:

 -- Function: vectorp object
     This function returns t if OBJECT is a vector.

          (vectorp [a])
               => t
          (vectorp "asdf")
               => nil

 -- Function: vector &rest objects
     This function creates and returns a vector whose elements are the arguments, OBJECTS.

          (vector 'foo 23 [bar baz] "rats")
               => [foo 23 [bar baz] "rats"]
          (vector)
               => []

 -- Function: make-vector length object
     This function returns a new vector consisting of LENGTH elements, each initialized to OBJECT.

          (setq sleepy (make-vector 9 'Z))
               => [Z Z Z Z Z Z Z Z Z]

 -- Function: vconcat &rest sequences
     This function returns a new vector containing all the elements of SEQUENCES.  The arguments SEQUENCES may be proper lists, vectors, strings or bool-vectors.  If no SEQUENCES are given, the empty vector is returned.

     The value is either the empty vector, or is a newly constructed nonempty vector that is not eq to any existing vector.

          (setq a (vconcat '(A B C) '(D E F)))
               => [A B C D E F]
          (eq a (vconcat a))
               => nil

          (vconcat)
               => []
          (vconcat [A B C] "aa" '(foo (6 7)))
               => [A B C 97 97 foo (6 7)]

     The vconcat function also allows byte-code function objects as arguments.  This is a special feature to make it easy to access the entire contents of a byte-code function object.  See Byte-Code Objects.

     For other concatenation functions, see mapconcat in Mapping Functions, concat in Creating Strings, and append in Building Lists.

The append function also provides a way to convert a vector into a list with the same elements:

     (setq avector [1 two (quote (three)) "four" [five]])
          => [1 two '(three) "four" [five]]
     (append avector nil)
          => (1 two '(three) "four" [five])

Char-Tables
===========

A char-table is much like a vector, except that it is indexed by character codes.  Any valid character code, without modifiers, can be used as an index in a char-table.  You can access a char-table's elements with aref and aset, as with any array.  In addition, a char-table can have extra slots to hold additional data not associated with particular character codes.  Like vectors, char-tables are constants when evaluated, and can hold elements of any type.

Each char-table has a subtype, a symbol, which serves two purposes:

  * The subtype provides an easy way to tell what the char-table is for. For instance, display tables are char-tables with display-table as the subtype, and syntax tables are char-tables with syntax-table as the subtype.  The subtype can be queried using the function char-table-subtype, described below.

  * The subtype controls the number of extra slots in the char-table.  This number is specified by the subtype's char-table-extra-slots symbol property (see Symbol Properties), whose value should be an integer between 0 and 10.  If the subtype has no such symbol property, the char-table has no extra slots.

A char-table can have a parent, which is another char-table.  If it does, then whenever the char-table specifies nil for a particular character C, it inherits the value specified in the parent.  In other words, (aref CHAR-TABLE C) returns the value from the parent of CHAR-TABLE if CHAR-TABLE itself specifies nil.

A char-table can also have a default value.  If so, then (aref CHAR-TABLE C) returns the default value whenever the char-table does not specify any other non-nil value.

 -- Function: make-char-table subtype &optional init
     Return a newly-created char-table, with subtype SUBTYPE (a symbol).  Each element is initialized to INIT, which defaults to nil.  You cannot alter the subtype of a char-table after the char-table is created.

     There is no argument to specify the length of the char-table, because all char-tables have room for any valid character code as an index.

     If SUBTYPE has the char-table-extra-slots symbol property, that specifies the number of extra slots in the char-table. This should be an integer between 0 and 10; otherwise, make-char-table raises an error.  If SUBTYPE has no char-table-extra-slots symbol property (see Property Lists), the char-table has no extra slots.

 -- Function: char-table-p object
     This function returns t if OBJECT is a char-table, and nil otherwise.

 -- Function: char-table-subtype char-table
     This function returns the subtype symbol of CHAR-TABLE.

There is no special function to access default values in a char-table. To do that, use char-table-range (see below).

 -- Function: char-table-parent char-table
     This function returns the parent of CHAR-TABLE.  The parent is always either nil or another char-table.

 -- Function: set-char-table-parent char-table new-parent
     This function sets the parent of CHAR-TABLE to NEW-PARENT.

 -- Function: char-table-extra-slot char-table n
     This function returns the contents of extra slot N (zero based) of CHAR-TABLE.  The number of extra slots in a char-table is determined by its subtype.

 -- Function: set-char-table-extra-slot char-table n value
     This function stores VALUE in extra slot N (zero based) of CHAR-TABLE.

A char-table can specify an element value for a single character code; it can also specify a value for an entire character set.

 -- Function: char-table-range char-table range
     This returns the value specified in CHAR-TABLE for a range of characters RANGE.  Here are the possibilities for RANGE:

     nil
          Refers to the default value.

     CHAR
          Refers to the element for character CHAR (supposing CHAR is a valid character code).

     (FROM . TO)
          A cons cell refers to all the characters in the inclusive range [FROM..TO].

 -- Function: set-char-table-range char-table range value
     This function sets the value in CHAR-TABLE for a range of characters RANGE.  Here are the possibilities for RANGE:

     nil
          Refers to the default value.

     t
          Refers to the whole range of character codes.

     CHAR
          Refers to the element for character CHAR (supposing CHAR is a valid character code).

     (FROM . TO)
          A cons cell refers to all the characters in the inclusive range [FROM..TO].

 -- Function: map-char-table function char-table
     This function calls its argument FUNCTION for each element of CHAR-TABLE that has a non-nil value.  The call to FUNCTION is with two arguments, a key and a value.  The key is a possible RANGE argument for char-table-range---either a valid character or a cons cell (FROM . TO), specifying a range of characters that share the same value.  The value is what (char-table-range CHAR-TABLE KEY) returns.

     Overall, the key-value pairs passed to FUNCTION describe all the values stored in CHAR-TABLE.

     The return value is always nil; to make calls to map-char-table useful, FUNCTION should have side effects. For example, here is how to examine the elements of the syntax table:

          (let (accumulator)
             (map-char-table
              (lambda (key value)
                (setq accumulator
                      (cons (list
                             (if (consp key)
                                 (list (car key) (cdr key))
                               key)
                             value)
                            accumulator)))
              (syntax-table))
             accumulator)
          =>
          (((2597602 4194303) (2)) ((2597523 2597601) (3))
           ... (65379 (5 . 65378)) (65378 (4 . 65379)) (65377 (1))
           ... (12 (0)) (11 (3)) (10 (12)) (9 (0)) ((0 8) (3)))

Bool-vectors
============

A bool-vector is much like a vector, except that it stores only the values t and nil.  If you try to store any non-nil value into an element of the bool-vector, the effect is to store t there.  As with all arrays, bool-vector indices start from 0, and the length cannot be changed once the bool-vector is created. Bool-vectors are constants when evaluated.

Several functions work specifically with bool-vectors; aside from that, you manipulate them with same functions used for other kinds of arrays.

 -- Function: make-bool-vector length initial
     Return a new bool-vector of LENGTH elements, each one initialized to INITIAL.

 -- Function: bool-vector &rest objects
     This function creates and returns a bool-vector whose elements are the arguments, OBJECTS.

 -- Function: bool-vector-p object
     This returns t if OBJECT is a bool-vector, and nil otherwise.

There are also some bool-vector set operation functions, described below:

 -- Function: bool-vector-exclusive-or a b &optional c
     Return bitwise exclusive or of bool vectors A and B. If optional argument C is given, the result of this operation is stored into C.  All arguments should be bool vectors of the same length.

 -- Function: bool-vector-union a b &optional c
     Return bitwise or of bool vectors A and B.  If optional argument C is given, the result of this operation is stored into C.  All arguments should be bool vectors of the same length.

 -- Function: bool-vector-intersection a b &optional c
     Return bitwise and of bool vectors A and B.  If optional argument C is given, the result of this operation is stored into C.  All arguments should be bool vectors of the same length.

 -- Function: bool-vector-set-difference a b &optional c
     Return set difference of bool vectors A and B.  If optional argument C is given, the result of this operation is stored into C.  All arguments should be bool vectors of the same length.

 -- Function: bool-vector-not a &optional b
     Return set complement of bool vector A.  If optional argument B is given, the result of this operation is stored into B.  All arguments should be bool vectors of the same length.

 -- Function: bool-vector-subsetp a b
     Return t if every t value in A is also t in B, nil otherwise.  All arguments should be bool vectors of the same length.

 -- Function: bool-vector-count-consecutive a b i
     Return the number of consecutive elements in A equal B starting at I.  a is a bool vector, B is t or nil, and I is an index into a.

 -- Function: bool-vector-count-population a
     Return the number of elements that are t in bool vector A.

The printed form represents up to 8 boolean values as a single character:

     (bool-vector t nil t nil)
          => #&4"^E"
     (bool-vector)
          => #&0""

You can use vconcat to print a bool-vector like other vectors:

     (vconcat (bool-vector nil t nil t))
          => [nil t nil t]

Here is another example of creating, examining, and updating a bool-vector:

     (setq bv (make-bool-vector 5 t))
          => #&5"^_"
     (aref bv 1)
          => t
     (aset bv 3 nil)
          => nil
     bv
          => #&5"^W"

These results make sense because the binary codes for control-_ and control-W are 11111 and 10111, respectively.

Managing a Fixed-Size Ring of Objects
=====================================

A ring is a fixed-size data structure that supports insertion, deletion, rotation, and modulo-indexed reference and traversal.  An efficient ring data structure is implemented by the ring package.  It provides the functions listed in this section.

Note that several rings in Emacs, like the kill ring and the mark ring, are actually implemented as simple lists, not using the ring package; thus the following functions won't work on them.

 -- Function: make-ring size
     This returns a new ring capable of holding SIZE objects. SIZE should be an integer.

 -- Function: ring-p object
     This returns t if OBJECT is a ring, nil otherwise.

 -- Function: ring-size ring
     This returns the maximum capacity of the RING.

 -- Function: ring-length ring
     This returns the number of objects that RING currently contains. The value will never exceed that returned by ring-size.

 -- Function: ring-elements ring
     This returns a list of the objects in RING, in order, newest first.

 -- Function: ring-copy ring
     This returns a new ring which is a copy of RING. The new ring contains the same (eq) objects as RING.

 -- Function: ring-empty-p ring
     This returns t if RING is empty, nil otherwise.

The newest element in the ring always has index 0.  Higher indices correspond to older elements.  Indices are computed modulo the ring length.  Index -1 corresponds to the oldest element, -2 to the next-oldest, and so forth.

 -- Function: ring-ref ring index
     This returns the object in RING found at index INDEX. INDEX may be negative or greater than the ring length.  If RING is empty, ring-ref signals an error.

 -- Function: ring-insert ring object
     This inserts OBJECT into RING, making it the newest element, and returns OBJECT.

     If the ring is full, insertion removes the oldest element to make room for the new element.

 -- Function: ring-remove ring &optional index
     Remove an object from RING, and return that object.  The argument INDEX specifies which item to remove; if it is nil, that means to remove the oldest item.  If RING is empty, ring-remove signals an error.

 -- Function: ring-insert-at-beginning ring object
     This inserts OBJECT into RING, treating it as the oldest element.  The return value is not significant.

     If the ring is full, this function removes the newest element to make room for the inserted element.

 -- Function: ring-resize ring size
     Set the size of RING to SIZE.  If the new size is smaller, then the oldest items in the ring are discarded.

If you are careful not to exceed the ring size, you can use the ring as a first-in-first-out queue.  For example:

     (let ((fifo (make-ring 5)))
       (mapc (lambda (obj) (ring-insert fifo obj))
             '(0 one "two"))
       (list (ring-remove fifo) t
             (ring-remove fifo) t
             (ring-remove fifo)))
          => (0 t one t "two")