@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990-1995, 1998-1999, 2001-2014 Free Software
+@c Copyright (C) 1990-1995, 1998-1999, 2001-2015 Free Software
@c Foundation, Inc.
@c See the file elisp.texi for copying conditions.
@node Sequences Arrays Vectors
@end example
@end defun
-@defun reverse seq
+@defun reverse sequence
@cindex string reverse
@cindex list reverse
@cindex vector reverse
@cindex sequence reverse
This function creates a new sequence whose elements are the elements
-of @var{seq}, but in reverse order. The original argument @var{seq}
-is @emph{not} altered. Note that char-table cannot be reversed.
+of @var{sequence}, but in reverse order. The original argument @var{sequence}
+is @emph{not} altered. Note that char-tables cannot be reversed.
@example
@group
@end example
@end defun
-@defun nreverse seq
+@defun nreverse sequence
@cindex reversing a string
@cindex reversing a list
@cindex reversing a vector
- This function reverses the order of the elements of @var{seq}.
-If @var{seq} is a list, @code{nreverse} alters it by reversing the @sc{cdr}s
-in the cons cells. The cons cell that used to be the last one in @var{seq}
-becomes the first cons cell of the value. If @var{seq} is a vector or
-bool vector, its items are placed in the same vector in a reversed
-order. If @var{seq} is a string, it works like @code{reverse} i.e., no
-destructive modifcation in preference to treat strings as immutable.
+ This function reverses the order of the elements of @var{sequence}.
+Unlike @code{reverse} the original @var{sequence} may be modified.
For example:
@end defun
+@defun sort sequence predicate
+@cindex stable sort
+@cindex sorting lists
+@cindex sorting vectors
+This function sorts @var{sequence} stably. Note that this function doesn't work
+for all sequences; it may be used only for lists and vectors. If @var{sequence}
+is a list, it is modified destructively. This functions returns the sorted
+@var{sequence} and compares elements using @var{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 @var{predicate} must be a function that accepts two
+arguments. It is called with two elements of @var{sequence}. To get an
+increasing order sort, the @var{predicate} should return non-@code{nil} if the
+first element is ``less than'' the second, or @code{nil} if not.
+
+The comparison function @var{predicate} must give reliable results for
+any given pair of arguments, at least within a single call to
+@code{sort}. It must be @dfn{antisymmetric}; that is, if @var{a} is
+less than @var{b}, @var{b} must not be less than @var{a}. It must be
+@dfn{transitive}---that is, if @var{a} is less than @var{b}, and @var{b}
+is less than @var{c}, then @var{a} must be less than @var{c}. If you
+use a comparison function which does not meet these requirements, the
+result of @code{sort} is unpredictable.
+
+The destructive aspect of @code{sort} for lists is that it rearranges the
+cons cells forming @var{sequence} by changing @sc{cdr}s. 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 @code{copy-sequence} and then sort.
+
+Sorting does not change the @sc{car}s of the cons cells in @var{sequence};
+the cons cell that originally contained the element @code{a} in
+@var{sequence} still has @code{a} in its @sc{car} after sorting, but it now
+appears in a different position in the list due to the change of
+@sc{cdr}s. For example:
+
+@example
+@group
+(setq nums '(1 3 2 6 5 4 0))
+ @result{} (1 3 2 6 5 4 0)
+@end group
+@group
+(sort nums '<)
+ @result{} (0 1 2 3 4 5 6)
+@end group
+@group
+nums
+ @result{} (1 2 3 4 5 6)
+@end group
+@end example
+
+@noindent
+@strong{Warning}: Note that the list in @code{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 @code{sort} and use that. Most often we store the result back into
+the variable that held the original list:
+
+@example
+(setq nums (sort nums '<))
+@end example
+
+For the better understanding of what stable sort is, consider the following
+vector example. After sorting, all items whose @code{car} is 8 are grouped
+at the beginning of @code{vector}, but their relative order is preserved.
+All items whose @code{car} is 9 are grouped at the end of @code{vector},
+but their relative order is also preserved:
+
+@example
+@group
+(setq
+ vector
+ (vector '(8 . "xxx") '(9 . "aaa") '(8 . "bbb") '(9 . "zzz")
+ '(9 . "ppp") '(8 . "ttt") '(8 . "eee") '(9 . "fff")))
+ @result{} [(8 . "xxx") (9 . "aaa") (8 . "bbb") (9 . "zzz")
+ (9 . "ppp") (8 . "ttt") (8 . "eee") (9 . "fff")]
+@end group
+@group
+(sort vector (lambda (x y) (< (car x) (car y))))
+ @result{} [(8 . "xxx") (8 . "bbb") (8 . "ttt") (8 . "eee")
+ (9 . "aaa") (9 . "zzz") (9 . "ppp") (9 . "fff")]
+@end group
+@end example
+
+@xref{Sorting}, for more functions that perform sorting.
+See @code{documentation} in @ref{Accessing Documentation}, for a
+useful example of @code{sort}.
+@end defun
+
+@cindex sequence functions in seq
+@cindex seq library
+ The @file{seq.el} library provides the following additional sequence
+manipulation macros and functions, prefixed with @code{seq-}. To use
+them, you must first load the @file{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.
+
+@defun seq-drop sequence n
+ This function returns all but the first @var{n} (an integer)
+elements of @var{sequence}. If @var{n} is negative or zero,
+the result is @var{sequence}.
+
+@example
+@group
+(seq-drop [1 2 3 4 5 6] 3)
+@result{} [4 5 6]
+@end group
+@group
+(seq-drop "hello world" -4)
+@result{} "hello world"
+@end group
+@end example
+@end defun
+
+@defun seq-take sequence n
+ This function returns the first @var{n} (an integer) elements of
+@var{sequence}. If @var{n} is negative or zero, the result
+is @code{nil}.
+
+@example
+@group
+(seq-take '(1 2 3 4) 3)
+@result{} (1 2 3)
+@end group
+@group
+(seq-take [1 2 3 4] 0)
+@result{} []
+@end group
+@end example
+@end defun
+
+@defun seq-take-while predicate sequence
+ This function returns the members of @var{sequence} in order,
+stopping before the first one for which @var{predicate} returns @code{nil}.
+
+@example
+@group
+(seq-take-while (lambda (elt) (> elt 0)) '(1 2 3 -1 -2))
+@result{} (1 2 3)
+@end group
+@group
+(seq-take-while (lambda (elt) (> elt 0)) [-1 4 6])
+@result{} []
+@end group
+@end example
+@end defun
+
+@defun seq-drop-while predicate sequence
+ This function returns the members of @var{sequence} in order,
+starting from the first one for which @var{predicate} returns @code{nil}.
+
+@example
+@group
+(seq-drop-while (lambda (elt) (> elt 0)) '(1 2 3 -1 -2))
+@result{} (-1 -2)
+@end group
+@group
+(seq-drop-while (lambda (elt) (< elt 0)) [1 4 6])
+@result{} [1 4 6]
+@end group
+@end example
+@end defun
+
+@defun seq-filter predicate sequence
+@cindex filtering sequences
+ This function returns a list of all the elements in @var{sequence}
+for which @var{predicate} returns non-@code{nil}.
+
+@example
+@group
+(seq-filter (lambda (elt) (> elt 0)) [1 -1 3 -3 5])
+@result{} (1 3 5)
+@end group
+@group
+(seq-filter (lambda (elt) (> elt 0)) '(-1 -3 -5))
+@result{} nil
+@end group
+@end example
+@end defun
+
+@defun seq-remove predicate sequence
+@cindex removing from sequences
+ This function returns a list of all the elements in @var{sequence}
+for which @var{predicate} returns @code{nil}.
+
+@example
+@group
+(seq-remove (lambda (elt) (> elt 0)) [1 -1 3 -3 5])
+@result{} (-1 -3)
+@end group
+@group
+(seq-remove (lambda (elt) (< elt 0)) '(-1 -3 -5))
+@result{} nil
+@end group
+@end example
+@end defun
+
+@defun seq-reduce function sequence initial-value
+@cindex reducing sequences
+ This function returns the result of calling @var{function} with
+@var{initial-value} and the first element of @var{sequence}, then calling
+@var{function} with that result and the second element of @var{sequence},
+then with that result and the third element of @var{sequence}, etc.
+@var{function} should be a function of two arguments. If
+@var{sequence} is empty, this returns @var{initial-value} without
+calling @var{function}.
+
+@example
+@group
+(seq-reduce #'+ [1 2 3 4] 0)
+@result{} 10
+@end group
+@group
+(seq-reduce #'+ '(1 2 3 4) 5)
+@result{} 15
+@end group
+@group
+(seq-reduce #'+ '() 3)
+@result{} 3
+@end group
+@end example
+@end defun
+
+@defun seq-some-p predicate sequence
+ This function returns the first member of sequence for which @var{predicate}
+returns non-@code{nil}.
+
+@example
+@group
+(seq-some-p #'numberp ["abc" 1 nil])
+@result{} 1
+@end group
+@group
+(seq-some-p #'numberp ["abc" "def"])
+@result{} nil
+@end group
+@end example
+@end defun
+
+@defun seq-every-p predicate sequence
+ This function returns non-@code{nil} if applying @var{predicate}
+to every element of @var{sequence} returns non-@code{nil}.
+
+@example
+@group
+(seq-every-p #'numberp [2 4 6])
+@result{} t
+@end group
+@group
+(seq-some-p #'numberp [2 4 "6"])
+@result{} nil
+@end group
+@end example
+@end defun
+
+@defun seq-empty-p sequence
+ This function returns non-@code{nil} if @var{sequence} is empty.
+
+@example
+@group
+(seq-empty-p "not empty")
+@result{} nil
+@end group
+@group
+(seq-empty-p "")
+@result{} t
+@end group
+@end example
+@end defun
+
+@defun seq-count predicate sequence
+ This function returns the number of elements in @var{sequence} for which
+@var{predicate} returns non-@code{nil}.
+
+@example
+(seq-count (lambda (elt) (> elt 0)) [-1 2 0 3 -2])
+@result{} 2
+@end example
+@end defun
+
+@cindex sorting sequences
+@defun seq-sort function sequence
+ This function returns a copy of @var{sequence} that is sorted
+according to @var{function}, a function of two arguments that returns
+non-@code{nil} if the first argument should sort before the second.
+@end defun
+
+@defun seq-contains-p sequence elt &optional function
+ This function returns the first element in @var{sequence} that is equal to
+@var{elt}. If the optional argument @var{function} is non-@code{nil},
+it is a function of two arguments to use instead of the default @code{equal}.
+
+@example
+@group
+(seq-contains-p '(symbol1 symbol2) 'symbol1)
+@result{} symbol1
+@end group
+@group
+(seq-contains-p '(symbol1 symbol2) 'symbol3)
+@result{} nil
+@end group
+@end example
+
+@end defun
+
+@defun seq-uniq sequence &optional function
+ This function returns a list of the elements of @var{sequence} with
+duplicates removed. If the optional argument @var{function} is non-@code{nil},
+it is a function of two arguments to use instead of the default @code{equal}.
+
+@example
+@group
+(seq-uniq '(1 2 2 1 3))
+@result{} (1 2 3)
+@end group
+@group
+(seq-uniq '(1 2 2.0 1.0) #'=)
+@result{} [3 4]
+@end group
+@end example
+@end defun
+
+@defun seq-subseq sequence start &optional end
+ This function returns a subset of @var{sequence} from @var{start}
+to @var{end}, both integers (@var{end} defaults to the last element).
+If @var{start} or @var{end} is negative, it counts from the end of
+@var{sequence}.
+
+@example
+@group
+(seq-subseq '(1 2 3 4 5) 1)
+@result{} (2 3 4 5)
+@end group
+@group
+(seq-subseq '[1 2 3 4 5] 1 3)
+@result{} [2 3]
+@end group
+@group
+(seq-subseq '[1 2 3 4 5] -3 -1)
+@result{} [3 4]
+@end group
+@end example
+@end defun
+
+@defun seq-concatenate type &rest sequences
+ This function returns a sequence of type @var{type} made of the
+concatenation of @var{sequences}. @var{type} may be: @code{vector},
+@code{list} or @code{string}.
+
+@example
+@group
+(seq-concatenate 'list '(1 2) '(3 4) [5 6])
+@result{} (1 2 3 5 6)
+@end group
+@group
+(seq-concatenate 'string "Hello " "world")
+@result{} "Hello world"
+@end group
+@end example
+@end defun
+
+@defmac seq-doseq (var sequence [result]) body@dots{}
+@cindex sequence iteration
+This macro is like @code{dolist}, except that @var{sequence} can be a list,
+vector or string (@pxref{Iteration} for more information about the
+@code{dolist} macro). This is primarily useful for side-effects.
+@end defmac
+
@node Arrays
@section Arrays
@cindex array
@defun bool-vector-subsetp a b
Return @code{t} if every @code{t} value in @var{a} is also t in
-@var{b}, nil otherwise. All arguments should be bool vectors of the
+@var{b}, @code{nil} otherwise. All arguments should be bool vectors of the
same length.
@end defun