9. Sequences

Common Lisp defines a number of functions that operate on sequences, which are either lists, strings, or vectors. Emacs Lisp includes a few of these, notably elt and length; this package defines most of the rest.

9.1 Sequence Basics

Many of the sequence functions take keyword arguments; see section Argument Lists. All keyword arguments are optional and, if specified, may appear in any order.

The :key argument should be passed either nil, or a function of one argument. This key function is used as a filter through which the elements of the sequence are seen; for example, (find x y :key 'car) is similar to (assoc* x y): It searches for an element of the list whose car equals x, rather than for an element which equals x itself. If :key is omitted or nil, the filter is effectively the identity function.

The :test and :test-not arguments should be either nil, or functions of two arguments. The test function is used to compare two sequence elements, or to compare a search value with sequence elements. (The two values are passed to the test function in the same order as the original sequence function arguments from which they are derived, or, if they both come from the same sequence, in the same order as they appear in that sequence.) The :test argument specifies a function which must return true (non-nil) to indicate a match; instead, you may use :test-not to give a function which returns false to indicate a match. The default test function is :test 'eql.

Many functions which take item and :test or :test-not arguments also come in -if and -if-not varieties, where a predicate function is passed instead of item, and sequence elements match if the predicate returns true on them (or false in the case of -if-not). For example:

(remove* 0 seq :test '=)  ≡  (remove-if 'zerop seq)

to remove all zeros from sequence seq.

Some operations can work on a subsequence of the argument sequence; these function take :start and :end arguments which default to zero and the length of the sequence, respectively. Only elements between start (inclusive) and end (exclusive) are affected by the operation. The end argument may be passed nil to signify the length of the sequence; otherwise, both start and end must be integers, with 0 <= start <= end <= (length seq). If the function takes two sequence arguments, the limits are defined by keywords :start1 and :end1 for the first, and :start2 and :end2 for the second.

A few functions accept a :from-end argument, which, if non-nil, causes the operation to go from right-to-left through the sequence instead of left-to-right, and a :count argument, which specifies an integer maximum number of elements to be removed or otherwise processed.

The sequence functions make no guarantees about the order in which the :test, :test-not, and :key functions are called on various elements. Therefore, it is a bad idea to depend on side effects of these functions. For example, :from-end may cause the sequence to be scanned actually in reverse, or it may be scanned forwards but computing a result “as if” it were scanned backwards. (Some functions, like mapcar* and every, do specify exactly the order in which the function is called so side effects are perfectly acceptable in those cases.)

Strings in GNU Emacs 19 may contain “text properties” as well as character data. Except as noted, it is undefined whether or not text properties are preserved by sequence functions. For example, (remove* ?A str) may or may not preserve the properties of the characters copied from str into the result.

9.2 Mapping over Sequences

These functions “map” the function you specify over the elements of lists or arrays. They are all variations on the theme of the built-in function mapcar.

Function: mapcar* function seq &rest more-seqs

This function calls function on successive parallel sets of elements from its argument sequences. Given a single seq argument it is equivalent to mapcar; given n sequences, it calls the function with the first elements of each of the sequences as the n arguments to yield the first element of the result list, then with the second elements, and so on. The mapping stops as soon as the shortest sequence runs out. The argument sequences may be any mixture of lists, strings, and vectors; the return sequence is always a list.

Common Lisp’s mapcar accepts multiple arguments but works only on lists; Emacs Lisp’s mapcar accepts a single sequence argument. This package’s mapcar* works as a compatible superset of both.

Function: map result-type function seq &rest more-seqs

This function maps function over the argument sequences, just like mapcar*, but it returns a sequence of type result-type rather than a list. result-type must be one of the following symbols: vector, string, list (in which case the effect is the same as for mapcar*), or nil (in which case the results are thrown away and map returns nil).

Function: maplist function list &rest more-lists

This function calls function on each of its argument lists, then on the cdrs of those lists, and so on, until the shortest list runs out. The results are returned in the form of a list. Thus, maplist is like mapcar* except that it passes in the list pointers themselves rather than the cars of the advancing pointers.

Function: mapc function seq &rest more-seqs

This function is like mapcar*, except that the values returned by function are ignored and thrown away rather than being collected into a list. The return value of mapc is seq, the first sequence.

Function: mapl function list &rest more-lists

This function is like maplist, except that it throws away the values returned by function.

Function: mapcan function seq &rest more-seqs

This function is like mapcar*, except that it concatenates the return values (which must be lists) using nconc, rather than simply collecting them into a list.

Function: mapcon function list &rest more-lists

This function is like maplist, except that it concatenates the return values using nconc.

Function: some predicate seq &rest more-seqs

This function calls predicate on each element of seq in turn; if predicate returns a non-nil value, some returns that value, otherwise it returns nil. Given several sequence arguments, it steps through the sequences in parallel until the shortest one runs out, just as in mapcar*. You can rely on the left-to-right order in which the elements are visited, and on the fact that mapping stops immediately as soon as predicate returns non-nil.

Function: every predicate seq &rest more-seqs

This function calls predicate on each element of the sequence(s) in turn; it returns nil as soon as predicate returns nil for any element, or t if the predicate was true for all elements.

Function: notany predicate seq &rest more-seqs

This function calls predicate on each element of the sequence(s) in turn; it returns nil as soon as predicate returns a non-nil value for any element, or t if the predicate was nil for all elements.

Function: notevery predicate seq &rest more-seqs

This function calls predicate on each element of the sequence(s) in turn; it returns a non-nil value as soon as predicate returns nil for any element, or t if the predicate was true for all elements.

Function: reduce function seq &key :from-end :start :end :initial-value :key

This function combines the elements of seq using an associative binary operation. Suppose function is * and seq is the list (2 3 4 5). The first two elements of the list are combined with (* 2 3) = 6; this is combined with the next element, (* 6 4) = 24, and that is combined with the final element: (* 24 5) = 120. Note that the * function happens to be self-reducing, so that (* 2 3 4 5) has the same effect as an explicit call to reduce.

If :from-end is true, the reduction is right-associative instead of left-associative:

(reduce '- '(1 2 3 4)) ≡ (- (- (- 1 2) 3) 4) ⇒ -8 (reduce '- '(1 2 3 4) :from-end t) ≡ (- 1 (- 2 (- 3 4))) ⇒ -2

If :key is specified, it is a function of one argument which is called on each of the sequence elements in turn.

If :initial-value is specified, it is effectively added to the front (or rear in the case of :from-end) of the sequence. The :key function is not applied to the initial value.

If the sequence, including the initial value, has exactly one element then that element is returned without ever calling function. If the sequence is empty (and there is no initial value), then function is called with no arguments to obtain the return value.

All of these mapping operations can be expressed conveniently in terms of the loop macro. In compiled code, loop will be faster since it generates the loop as in-line code with no function calls.

9.3 Sequence Functions

This section describes a number of Common Lisp functions for operating on sequences.

Function: subseq sequence start &optional end

This function returns a given subsequence of the argument sequence, which may be a list, string, or vector. The indices start and end must be in range, and start must be no greater than end. If end is omitted, it defaults to the length of the sequence. The return value is always a copy; it does not share structure with sequence.

As an extension to Common Lisp, start and/or end may be negative, in which case they represent a distance back from the end of the sequence. This is for compatibility with Emacs’ substring function. Note that subseq is the only sequence function that allows negative start and end.

You can use setf on a subseq form to replace a specified range of elements with elements from another sequence. The replacement is done as if by replace, described below.

Function: concatenate result-type &rest seqs

This function concatenates the argument sequences together to form a result sequence of type result-type, one of the symbols vector, string, or list. The arguments are always copied, even in cases such as (concatenate 'list '(1 2 3)) where the result is identical to an argument.

Function: fill seq item &key :start :end

This function fills the elements of the sequence (or the specified part of the sequence) with the value item.

Function: replace seq1 seq2 &key :start1 :end1 :start2 :end2

This function copies part of seq2 into part of seq1. The sequence seq1 is not stretched or resized; the amount of data copied is simply the shorter of the source and destination (sub)sequences. The function returns seq1.

If seq1 and seq2 are eq, then the replacement will work correctly even if the regions indicated by the start and end arguments overlap. However, if seq1 and seq2 are lists which share storage but are not eq, and the start and end arguments specify overlapping regions, the effect is undefined.

Function: remove* item seq &key :test :test-not :key :count :start :end :from-end

This returns a copy of seq with all elements matching item removed. The result may share storage with or be eq to seq in some circumstances, but the original seq will not be modified. The :test, :test-not, and :key arguments define the matching test that is used; by default, elements eql to item are removed. The :count argument specifies the maximum number of matching elements that can be removed (only the leftmost count matches are removed). The :start and :end arguments specify a region in seq in which elements will be removed; elements outside that region are not matched or removed. The :from-end argument, if true, says that elements should be deleted from the end of the sequence rather than the beginning (this matters only if count was also specified).

Function: delete* item seq &key :test :test-not :key :count :start :end :from-end

This deletes all elements of seq which match item. It is a destructive operation. Since Emacs Lisp does not support stretchable strings or vectors, this is the same as remove* for those sequence types. On lists, remove* will copy the list if necessary to preserve the original list, whereas delete* will splice out parts of the argument list. Compare append and nconc, which are analogous non-destructive and destructive list operations in Emacs Lisp.

The predicate-oriented functions remove-if, remove-if-not, delete-if, and delete-if-not are defined similarly.

Function: delete item list

This MacLisp-compatible function deletes from list all elements which are equal to item. The delete function is built-in to Emacs 19; this package defines it equivalently in Emacs 18.

Function: remove item list

This function removes from list all elements which are equal to item. This package defines it for symmetry with delete, even though remove is not built-in to Emacs 19.

Function: remq item list

This function removes from list all elements which are eq to item. This package defines it for symmetry with delq, even though remq is not built-in to Emacs 19.

Function: remove-duplicates seq &key :test :test-not :key :start :end :from-end

This function returns a copy of seq with duplicate elements removed. Specifically, if two elements from the sequence match according to the :test, :test-not, and :key arguments, only the rightmost one is retained. If :from-end is true, the leftmost one is retained instead. If :start or :end is specified, only elements within that subsequence are examined or removed.

Function: delete-duplicates seq &key :test :test-not :key :start :end :from-end

This function deletes duplicate elements from seq. It is a destructive version of remove-duplicates.

Function: substitute new old seq &key :test :test-not :key :count :start :end :from-end

This function returns a copy of seq, with all elements matching old replaced with new. The :count, :start, :end, and :from-end arguments may be used to limit the number of substitutions made.

Function: nsubstitute new old seq &key :test :test-not :key :count :start :end :from-end

This is a destructive version of substitute; it performs the substitution using setcar or aset rather than by returning a changed copy of the sequence.

The substitute-if, substitute-if-not, nsubstitute-if, and nsubstitute-if-not functions are defined similarly. For these, a predicate is given in place of the old argument.

9.4 Searching Sequences

These functions search for elements or subsequences in a sequence. (See also member* and assoc*; see section Lists.)

Function: find item seq &key :test :test-not :key :start :end :from-end

This function searches seq for an element matching item. If it finds a match, it returns the matching element. Otherwise, it returns nil. It returns the leftmost match, unless :from-end is true, in which case it returns the rightmost match. The :start and :end arguments may be used to limit the range of elements that are searched.

Function: position item seq &key :test :test-not :key :start :end :from-end

This function is like find, except that it returns the integer position in the sequence of the matching item rather than the item itself. The position is relative to the start of the sequence as a whole, even if :start is non-zero. The function returns nil if no matching element was found.

Function: count item seq &key :test :test-not :key :start :end

This function returns the number of elements of seq which match item. The result is always a nonnegative integer.

The find-if, find-if-not, position-if, position-if-not, count-if, and count-if-not functions are defined similarly.

Function: mismatch seq1 seq2 &key :test :test-not :key :start1 :end1 :start2 :end2 :from-end

This function compares the specified parts of seq1 and seq2. If they are the same length and the corresponding elements match (according to :test, :test-not, and :key), the function returns nil. If there is a mismatch, the function returns the index (relative to seq1) of the first mismatching element. This will be the leftmost pair of elements which do not match, or the position at which the shorter of the two otherwise-matching sequences runs out.

If :from-end is true, then the elements are compared from right to left starting at (1- end1) and (1- end2). If the sequences differ, then one plus the index of the rightmost difference (relative to seq1) is returned.

An interesting example is (mismatch str1 str2 :key 'upcase), which compares two strings case-insensitively.

Function: search seq1 seq2 &key :test :test-not :key :from-end :start1 :end1 :start2 :end2

This function searches seq2 for a subsequence that matches seq1 (or part of it specified by :start1 and :end1.) Only matches which fall entirely within the region defined by :start2 and :end2 will be considered. The return value is the index of the leftmost element of the leftmost match, relative to the start of seq2, or nil if no matches were found. If :from-end is true, the function finds the rightmost matching subsequence.

9.5 Sorting Sequences

Function: sort* seq predicate &key :key

This function sorts seq into increasing order as determined by using predicate to compare pairs of elements. predicate should return true (non-nil) if and only if its first argument is less than (not equal to) its second argument. For example, < and string-lessp are suitable predicate functions for sorting numbers and strings, respectively; > would sort numbers into decreasing rather than increasing order.

This function differs from Emacs’ built-in sort in that it can operate on any type of sequence, not just lists. Also, it accepts a :key argument which is used to preprocess data fed to the predicate function. For example,

(setq data (sort data 'string-lessp :key 'downcase))

sorts data, a sequence of strings, into increasing alphabetical order without regard to case. A :key function of car would be useful for sorting association lists.

The sort* function is destructive; it sorts lists by actually rearranging the cdr pointers in suitable fashion.

Function: stable-sort seq predicate &key :key

This function sorts seq stably, meaning two elements which are equal in terms of predicate are guaranteed not to be rearranged out of their original order by the sort.

In practice, sort* and stable-sort are equivalent in Emacs Lisp because the underlying sort function is stable by default. However, this package reserves the right to use non-stable methods for sort* in the future.

Function: merge type seq1 seq2 predicate &key :key

This function merges two sequences seq1 and seq2 by interleaving their elements. The result sequence, of type type (in the sense of concatenate), has length equal to the sum of the lengths of the two input sequences. The sequences may be modified destructively. Order of elements within seq1 and seq2 is preserved in the interleaving; elements of the two sequences are compared by predicate (in the sense of sort) and the lesser element goes first in the result. When elements are equal, those from seq1 precede those from seq2 in the result. Thus, if seq1 and seq2 are both sorted according to predicate, then the result will be a merged sequence which is (stably) sorted according to predicate.

This document was generated by Aidan Kehoe on December 27, 2016 using texi2html 1.82.