;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Introduction to Generic Sequence Functions =Text: 3INTRODUCTION TO GENERIC SEQUENCE FUNCTIONS* The type specifier 2sequence* is defined to include lists and vectors (arrays of rank one). Lists and vectors are similar in that both can be regarded as sequences of elements: there is a first element, a second element, and so on. Element 1n* of a list is 2(nth 1n* 1list*)*, and element 1n* of a vector is 2(aref 1vector* 1n*)*. Many useful operations which apply in principle to a sequence of objects can work equally well on lists and vectors. These are the generic sequence functions. All the generic sequence functions accept 2nil* as a sequence of length zero. =Node: Primitive Sequence Operations =Text: 3PRIMITIVE SEQUENCE OPERATIONS make-sequence* 1type* 1size* &key 1initial-element* Creates a sequence of type 1type*, 1size* elements long. 1size* must be an integer and 1type* must be either 2list* or some kind of array type. 1type* could be just 2array* or 2vector* to make a general vector, it could be 2(vector (byte 8))* to make an 2art-8b* vector, and so on. If 1initial-element* is specified, each element of the new sequence contains 1initial-element*. Otherwise, the new sequence is initialized to contain 2nil* if that is possible, zero otherwise (for numeric array types). 3(make-sequence 'list 3)* 3 => (nil nil nil)* 3(make-sequence 'array 5 :initial-element t)* 3 => #(t t t t t)* 3(make-sequence '(vector bit) 5)* 3 => #*00000 elt* 1sequence* 1index* Returns the element at index 1index* in 1sequence*. If 1sequence* is a list, this is 2(nth 1index** 1sequence2)**. If 1sequence* is a vector, this is 2(aref 1index* 1sequence*)*. Being microcoded, 2elt* is as fast as either 2nth* or 2aref*. 2(setf (elt 1sequence* 1index*) 1value*)* is the way to set an element of a sequence. 3length* 1sequence* Returns the length of 1sequence*, as an integer. For a vector with a fill pointer, this is the fill pointer value. For a list, it is the traditional Lisp function; note that lists ending with atoms other than 2nil* are accepted, so that the length of 2(a b . c)* is 2. =Node: Simple Sequence Operations =Text: 3SIMPLE SEQUENCE OPERATIONS copy-seq* 1sequence* Returns a new sequence of the same type, length and contents as 1sequence*. 3concatenate* 1result-type* &rest 1sequences* Returns a new sequence, of type 1result-type*, whose contents are made from the contents of all the 1sequences*. 1result-type* can be 2list* or any array type, just as in 2make-sequence* above. Examples: 3(concatenate 'list '(1 2) '#(A 3)) => (1 2 A 3)* 3(concatenate 'vector '(1 2) '#(A 3) => #(1 2 A 3) subseq* 1sequence* 1start* &optional 1end* Returns a new sequence whose elements are a subsequence of 1sequence*. The new sequence is of the same type as 1sequence*. 1start* is the index of the first element of 1sequence* to take. 1end* is the index of where to stop--the first element 1not* to take. 1end* can also be 2nil*, meaning take everything from 1start* up to the end of 1sequence*. Examples: 3(subseq "Foobar" 3 5) => "ba"* 3(subseq '(a b c) 1) => (b c)* It is also possible to 2setf* a call to 2subseq*. This means to store into part of the sequence passed to 2subseq*. Thus, 3(setf (subseq "Foobar" 3 5) "le")* modifies the string 2"Foobar"* so that it contains 2"Fooler"* instead. 3replace* 1into-sequence-1* 1from-sequence-2* &key 1(start1* 301)** 1end1* 1(start2* 301)** 1end2* Copies part of 1from-sequence-2* into part of 1to-sequence-1*. 1start2* and 1end2* are the indices of the part of 1from-sequence-2* to copy from, and 1start1* and 1end1* are the indices of the part of 1to-sequence-1* to copy into. If the number of elements to copy out of 1from-sequence-2* is less than the number of elements of 1to-sequence-1* to be copied into, the extra elements of 1to-sequence-1* are not changed. If the number of elements to copy out is more than there is room for, the last extra elements are ignored. If the two sequence arguments are the same sequence, then the elements to be copied are copied first into a temporary sequence (if necessary) to make sure that no element is overwritten before it is copied. Example: 3(setq str "Elbow")* 3(replace str str :start1 2 :end1 5 :start2 1 :end2 4)* modifies 2str* to contain 2"Ellbo"*. 1into-sequence-1* is returned as the value of 2replace*. 3fill* 1sequence* 1item* &key 1(start* 301)** 1end* Modifies the contents of 1sequence* by setting all the elements to 1item*. 1start* and 1end* may be specified to limit the operation to some contiguous portion of 1sequence*; then the elements before 1start* or after 1end* are unchanged. If 1end* is 2nil*, the filling goes to the end of 1sequence*. The value returned by 2fill* is 1sequence*. Example: 3(setq l '(a b c d e))* 3(fill l 'lose :start 2)* 3l => (a b lose lose lose) reverse* 1sequence* Returns a new sequence containing the same elements as 1sequence* but in reverse order. The new sequence is of the same type and length as 1sequence*. 2reverse* does not modify its argument, unlike 2nreverse* which is faster but does modify its argument. The list created by 2reverse* is not cdr-coded. 3(reverse "foo") => "oof"* 3(reverse '(a b (c d) e)) => (e (c d) b a) nreverse* 1sequence* Modifies 1sequence* destructively to have its elements in reverse order, and returns 1sequence* as modified. For a vector, this is done by copying the elements to different positions. For a list, this is done by modifying cdr pointers. This has two important consequences: it is most efficient when the list is not cdr-coded, and the rearranged list starts with the cell that used to be at the end. Although the altered list as a whole contains the same cells as the original, the actual value of the altered list is not 2eq* to the original list. For this reason, one must always store the value of 2nreverse* into the place where the list will be used. Do not just use 2nreverse* for effect on a list. 3(setq a '#(1 2 3 4 5))* 3(nreverse a)* 3(concatenate 'list a) => (5 4 3 2 1)* 3(setq b '(1 2 3 4 5)* 3 c b* 3 d (last b))* 3(setq b (nreverse b))* 3b => (5 4 3 2 1)* 3c => (1)* 3(eq b d) => t* 2nreverse* is most frequently used after a loop which computes elements for a new list one by one. These elements can be put on the new list with 2push*, but this produces a list which has the elements in reverse order (first one generated at the end of the list). 3(let (accumulate)* 3 (dolist (x input)* 3 (push (car x) accumulate)* 3 (push (cdr x) accumulate))* 3 (nreverse accumulate))* Currently, 2nreverse* is inefficient with cdr-coded lists (see 4(MANLISTSTR-1)Cdr-Coding*), because it just uses 2rplacd* in the straightforward way. This may be fixed someday. In the meantime 2reverse* might be preferable in some cases. =Node: Mapping On Sequences =Text: 3MAPPING ON SEQUENCES cli:map* 1result-type* 1function* &rest 1sequences* The Common Lisp 2map* function maps 1function* over successive elements of each 1sequence*, constructing and returning a sequence of the results that 1function* returns. The constructed sequence is of type 1result-type* (see 2make-sequence*, 4(GENERIC-1)Primitive Sequence Operations*). 1function* is called first on the first elements of all the sequences, then on the second elements of all, and so on until some argument sequence is exhausted. 3(map 'list 'list '(1 2 3) '#(A B C D))* 3 => ((1 A) (2 B) (3 C))* 3(setq vect (map '(vector (mod 16.)) '+* 3'(3 4 5 6 7) (circular-list 1)))* 3(concatenate 'list vect) => (2 3 4 5 6)* 3(array-element-type vect) => (mod 16.)* 1result-type* can also be 2nil*. Then the values returned by 1function* are thrown away, no sequence is constructed, and 2map* returns 2nil*. This function is available under the name 2map* in Common Lisp programs. In traditional Zetalisp programs, 2map* is another function which does something related but different; see 4(FLOWCTL-2)Mapping*. Traditional programs can call this function as 2cli:map*. 3cli:some* 1predicate* &rest 1sequences* Applies 1predicate* to successive elements of each sequence. If 1predicate* ever returns a non-2nil* value, 2cli:some* immediately returns the same value. If one of the argument sequences is exhausted, 2cli:some* returns 2nil*. Each time 1predicate* is called, it receives one argument from each sequence. The first time, it gets the first element of each sequence, then the second element of each, and so on until a sequence is exhausted. Examples: 3(cli:some 'plusp '(-4 0 5 6)) => 5* 3(cli:some '> '(-4 0 5 6) '(0 12 12 12)) => nil* 3(cli:some '> '(-4 0 5 6) '(3 3 3 3)) => 5* 3(cli:some '> '(-4 0 5 6) '(3 3)) => nil* This function is available under the name 2some* in Common Lisp programs. In traditional Zetalisp programs, 2some* is another function which does something related but different; see 4(MANLISTSTR-2)Lists as Tables*. Traditional programs can call this function as 2cli:some*. 3cli:every* 1predicate* &rest 1sequences* Applies 1predicate* to successive elements of each sequence. If 1predicate* ever returns 2nil*, 2cli:every* immediately returns 2nil*. If one of the argument sequences is exhausted, 2cli:every* returns 2t*. Each time 1predicate* is called, it receives one argument from each sequence. The first time, it gets the first element of each sequence, then the second element of each, and so on until a sequence is exhausted. Examples: 3(cli:every 'plusp '(-4 0 5 6)) => nil* 3(cli:every 'plusp '(5 6)) => t* This function is available under the name 2every* in Common Lisp programs. In traditional Zetalisp programs, 2every* is another function which does something related but different; see 4(MANLISTSTR-2)Lists as Tables*. Traditional programs can call this function as 2cli:every*. 3notany* 1predicate* &rest 1sequences* 3notevery* 1predicate* &rest 1sequences* These are the opposites of 2cli:some* and 2cli:every*. 2(notany ...)* is equivalent to 2(not (cli:some ...))*. 2(notevery ...)* is equivalent to 2(not (cli:every ...))*. 3reduce* 1function* 1sequence* &key 1from-end* 1(start* 301)** 1end* 1initial-value* Combines the elements of 1sequence* using 1function*, a function of two args. 1function* is applied to the first two elements; then to that result and the third element; then to that result and the fourth element; and so on. 1start* and 1end* are indices that restrict the action to a part of 1sequence*, as if the rest of 1sequence* were not there. They default to 0 and 2nil* (2nil* for 1end* means go all the way to the end of 1sequence*). If 1from-end* is non-2nil*, processing starts with the last of the elements. 1function* is first applied to the last two elements; then to the previous element and that result; then to the previous element and that result; and so on until element number 1start* has been used. If 1initial-value* is specified, it acts like an extra element of 1sequence*, used in addition to the actual elements of the specified part of 1sequence*. It comes, in effect, at the beginning if 1from-end* is 2nil*, but at the end if 1from-end* is non-2nil*, so that in any case it is the first element to be processed. If there is only one element to be processed, that element is returned and 1function* is not called. If there are no elements (1sequence* is of length zero and no 1initial-value*), 1function* is called with no arguments and its value is returned. Examples: 3(reduce '+ '(1 2 3)) => 6* 3(reduce '- '(1 2 3)) => -4* 3(reduce '- '(1 2 3) :from-end t) => 2 2;; 1 - (2 - 3)** 3(reduce 'cons '(1 2 3) :from-end t) => (1 2 . 3)* 3(reduce 'cons '(1 2 3)) => ((1 . 2) . 3)* =Node: Operating on Selected Elements =Text: 3OPERATING ON SELECTED ELEMENTS* The generic sequence functions for searching, substituting and removing elements from sequences take similar arguments whose meanings are standard. This is because they all look at each element of the sequence to decide whether it should be processed. Functions which conceptually modify the sequence come in pairs. One function in the pair copies the sequence if necessary and never modifies the argument. The copy is a list if the original sequence is a list; otherwise, the copy is an 2art-q* array. If the sequence is a list, it may be copied only partially, sharing any unchanged tail with the original argument. If no elements match, the result sequence may be 2eq* to the argument sequence. The other function in the pair may alter the original sequence and return it, or may make a copy and return that. There are two ways the function can decide which elements to operate on. The functions whose names end in 2-if* or 2-if-not* have an argument named 1predicate* which should be a function of one argument. This function is applied to each element and the value determines whether the element is processed. The other functions have an argument named 1item* or something similar which is an object to compare each element with. The elements that match 1item* are processed. By default, the comparison is done with 2eql*. You can specify any function of two arguments to be used instead, as the 1test* keyword argument. 1item* is always the first argument, and an element of the sequence is the second argument. The element matches 1item* if 1test* returns non-2nil*. Alternatively, you can specify the 1test-not* keyword argument; then the element matches if 1test-not* returns 2nil*. The elements may be tested in any order, and may be tested more than once. For predictable results, your 1predicate*, 1test* and 1test-not* functions should be side-effect free. The five keyword arguments 1start*, 1end*, 1key*, 1count* and 1from-end* have the same meanings for all of the functions, except that 1count* is not relevant for some kinds of operations. Here is what they do: 1start, end* 1start* and 1end* are indices in the sequence; they restrict the processing to the portion between those indices. Only elements in this portion are tested, replaced or removed. For the search functions, only this portion is searched. For element removal functions, elements outside the portion are unchanged. 1start* is the index of the first element to be processed, and 1end* is the index of the element after the last element to be processed. 1end* can also be 2nil*, meaning that processing should continue to the end of the sequence. 1start* always defaults to 0, and 1end* always defaults to 2nil*. 1key* 1key*, if not 2nil*, is a function of one argument which is applied to each element of the sequence to get a value which is passed to the 1test*, 1test-not* or 1predicate* function in place of the element. For example, if 1key* is 2car*, the car of each element is compared or tested. The default for 1key* is 2nil*, which means to compare or test the element itself. 1from-end* If 1from-end* is non-2nil*, elements are (conceptually) processed in the reverse of the sequence order, from the later elements to the earlier ones. In some functions this argument makes no difference, or matters only when 1count* is non-2nil*. Note: the actual testing of elements may happen in any order. 1count* 1count*, if not 2nil*, should be an integer specifying the number of matching elements to be processed. For example, if 1count* is 2, only the first two elements that match are removed, replaced, etc. If 1from-end* is non-2nil*, the last two matching elements are the ones removed or replaced. The default for 1count* is 2nil*, which means all elements are tested and all matching ones are processed. =Node: Removing Elements from Sequences =Text: 3REMOVING ELEMENTS FROM SEQUENCES* These functions remove certain elements of a sequence. The 2remove* series functions copy the argument; the 2delete* series functions can modify it destructively (currently they always copy anyway if the argument is a vector). 3remove-if* 1predicate* 1sequence* &key 1(start* 301)** 1end* 1count* 1key* 1from-end* 3delete-if* 1predicate* 1sequence* &key 1(start* 301)** 1end* 1count* 1key* 1from-end* Returns a sequence like 1sequence* but missing any elements that satisfy 1predicate*. 1predicate* is a function of one argument which is applied to one element at a time; if 1predicate* returns non-2nil*, that element is removed. 2remove-if* copies structure as necessary to avoid modifying 1sequence*, while 2delete-if* can either modify the original sequence and return it or make a copy and return that. (Currently, a list is always modified, and a vector is always copied, but don't depend on this.) The 1start*, 1end*, 1key* 1count* and 1from-end* arguments are handled in the standard way. 3(remove-if 'plusp '(1 -1 2 -2 3 -3)) => (-1 -2 -3)* 3(remove-if 'plusp '(1 -1 2 -2 3 -3) :count 2)* 3 => (-1 -2 3 -3)* 3(remove-if 'plusp '(1 -1 2 -2 3 -3) :count 2 :from-end t)* 3 => (1 -1 -2 -3)* 3(remove-if 'plusp '(1 -1 2 -2 3 -3) :start 4)* 3 => (1 -1 2 -2 -3)* 3(remove-if 'zerop '(1 -1 2 -2 3 -3) :key '1-)* 3 => (-1 2 -2 3 -3) remove-if-not* 1predicate* 1sequence* &key 1(start* 301)** 1end* 1count* 1key* 1from-end* 3delete-if-not* 1predicate* 1sequence* &key 1(start* 301)** 1end* 1count* 1key* 1from-end* Like 2remove-if* and 2delete-if* except that the elements removed are those for which 1predicate* returns 2nil*. 3cli:remove* 1item* 1sequence* &key 1(test* 3'eql1)** 1test-not* 1(start* 301)** 1end* 1count* 1key* 1from-end* 3cli:delete* 1item* 1sequence* &key 1(test* 3'eql1)** 1test-not* 1(start* 301)** 1end* 1count* 1key* 1from-end* The Common Lisp functions for eliminating elements from a sequence test the elements of 1sequence* one by one by comparison with 1item*, using the 1test* or 1test-not* function, and eliminate the elements that match. 2cli:remove* copies structure as necessary to avoid modifying 1sequence*, while 2cli:delete* can either modify the original sequence and return it or make a copy and return that. (Currently, a list is always modified, and a vector is always copied.) The 1start*, 1end*, 1key* 1count* and 1from-end* arguments are handled in the standard way. 3(cli:remove 'x '(x (a) (x) (a x)))* 3 => ((a) (x) (a x))* 3(cli:remove 'x '((a) (x) (a x)) :test 'memq)* 3 => ((a))* 3(cli:remove 'x '((a) (x) (a x)) :test-not 'memq)* 3 => ((x) (a x))* 3(cli:remove 'x '((a) (x) (a x)) * 3 :test 'memq :count 1)* 3 => ((a) (a x))* 3(cli:remove 'x '((a) (x) (a x)) :key 'car)* 3 => ((a) (a x))* These functions are available under the names 2remove* and 2delete* in Common Lisp programs. Traditional Zetalisp provides functions 2remove* and 2delete* which serve similar functions, on lists only, and with different calling sequences; see 4(MANLISTSTR-2)Lists as Tables* and 4(MANLISTSTR-2)Lists as Tables*. Traditional programs can call these functions as 2cli:remove* and 2cli:delete*. 3remove-duplicates* 1sequence* &key 1(test* 3'eql1)** 1test-not* 1(start* 301)** 1end* 1key* 1from-end* 3delete-duplicates* 1sequence* &key 1(test* 3'eql1)** 1test-not* 1(start* 301)** 1end* 1key* 1from-end* 2remove-duplicates* returns a new sequence like 1sequence* except that all but one of any set of matching elements have been removed. 2delete-duplicates* is the same except that it may destructively modify and then return 1sequence* itself. Elements are compared using 1test*, a function of two arguments. Two elements match if 1test* returns non-2nil*. Each element is compared with all the following elements and slated for removal if it matches any of them. If 1test-not* is specified, it is used instead of 1test*, but then elements match if 1test-not* returns 2nil*. If neither 1test* nor 1test-not* is specified, 2eql* is used for 1test*. If 1key* is non-2nil*, it should be a function of one argument. 1key* is applied to each element, and the value 1key* returns is passed to 1test* or 1test-not*. If 1from-end* is non-2nil*, then elements are processed (conceptually) from the end of 1sequence* forward. Each element is compared with all the preceding ones and slated for removal if it matches any of them. For a well-behaved comparison function, the only difference 1from-end* makes is which elements of a matching set are removed. Normally the last one is kept; with 1from-end*, it is the first one that is kept. If 1start* or 1end* is used to restrict processing to a portion of 1sequence*, both removal and comparison are restricted. An element is removed only if it is itself within the specified portion, and matches another element within the specified portion. =Node: Substitution Functions =Text: 3SUBSTITUTION FUNCTIONS* The functions in this section substitute a new value for certain of the elements in a sequence--those that match a specified object or satisfy a predicate. For example, you could replace every 2t* in the sequence with 2nil*, leaving all elements other than 2t* unchanged. The 2substitute* series functions make a copy and return it, leaving the original sequence unmodified. The 2nsubstitute* series functions always alter the original sequence destructively and return it. They do not use up any storage. Note the difference between these functions and the function 2cli:subst*. 2subst* operates only on lists, and it searches all levels of list structure in both car and cdr positions. 2substitute*, when given a list, considers for replacement only the elements of the list. 3substitute-if* 1newitem* 1predicate* 1sequence* &key 1start* 1end* 1count* 1key* 1from-end* 3nsubstitute-if* 1newitem* 1predicate* 1sequence* &key 1start* 1end* 1count* 1key* 1from-end* 2substitute-if* returns a new sequence like 1sequence* but with 1newitem* substituted for each element of 1sequence* that satisfies 1predicate*. 1sequence* itself is unchanged. If it is a list, only enough of it is copied to avoid changing 1sequence*. 2nsubstitute-if* replaces elements in 1sequence* itself, modifying it destructively, and returns 1sequence*. 1start*, 1end*, 1key*, 1count* and 1from-end* are handled in the standard fashion as described above. 3(substitute-if 0 'plusp '(1 -1 2 -2 3) :from-end t :count 2)* 3 => (1 -1 0 -2 0) substitute-if-not* 1newitem* 1predicate* 1sequence* &key 1start* 1end* 1count* 1key* 1from-end* 3nsubstitute-if-not* 1newitem* 1predicate* 1sequence* &key 1start* 1end* 1count* 1key* 1from-end* Like 2substitute-if* and 2nsubstitute-if* except that the elements replaced are those for which 1predicate* returns 2nil*. 3substitute* 1newitem* 1olditem* 1sequence* &key 1(test* 3'eql1)** 1test-not* 1start* 1end* 1count* 1key* 1from-end 3nsubstitute** 1newitem* 1olditem* 1sequence* &key 1(test* 3'eql1)** 1test-not* 1start* 1end* 1count* 1key* 1from-end* Like 2substitute-if* and 2nsubstitute-if* except that elements are tested by comparison with 1olditem*, using 1test* or 1test-not* as a comparison function. 1start*, 1end*, 1key*, 1count* and 1from-end* are handled in the standard fashion as described above. 3(substitute 'a 'b '(a b (a b)))* 3 => (a a (a b))* =Node: Searching for Elements =Text: 3SEARCHING FOR ELEMENTS* The functions in this section find an element or elements of a sequence which satisfy a predicate or match a specified object. The 2position* series functions find one element and return the index of the element found in the specified sequence. The 2find* series functions return the element itself. The 2count* series functions find all the elements that match and returns the number of them that were found. All of the functions accept the keyword arguments 1start*, 1end*, 1count* and 1from-end*, and handle them in the standard way described in 4(GENERIC-1)Operating on Selected Elements*. 3position-if* 1predicate* 1sequence* &key 1(start* 301)** 1end* 1key* 1from-end* 3find-if* 1predicate* 1sequence* &key 1(start* 301)** 1end* 1key* 1from-end* Find the first element of 1sequence* (last element, if 1from-end* is non-2nil*) which satisfies 1predicate*. 2position-if* returns the index in sequence of the element found; 2find-if* returns the element itself. If no element is found, the value is 2nil* for either function. See 4(GENERIC-1)Operating on Selected Elements* for a description of the standard arguments 1start*, 1end* and 1key*. If 1start* or 1end* is used to restrict operation to a portion of 1sequence*, elements outside the portion are not tested, but the index returned is still the index in the entire sequence. 3(position-if 'plusp '(-3 -2 -1 0 1 2 3))* 3 => 4* 3(find-if 'plusp '(-3 -2 -1 0 1 2 3))* 3 => 1* 3(position-if 'plusp '(-3 -2 -1 0 1 2 3) :start 5)* 3 => 5* 3(position-if 'plusp '(-3 -2 -1 0 1 2 3) :from-end t)* 3 => 6* 3(find-if 'plusp '(-3 -2 -1 0 1 2 3) :from-end t)* 3 => 3 position-if-not* 1predicate* 1sequence* &key 1(start* 301)** 1end* 1key* 1from-end* 3find-if-not* 1predicate* 1sequence* &key 1(start* 301)** 1end* 1key* 1from-end* Like 2position-if* and 2find-if* but search for an element for which 1predicate* returns 2nil*. 3position* 1item* 1sequence* 1sequence* &key 1test* 1test-not* 1(start* 301)** 1end* 1key* 1from-end* 3find* 1item* 1sequence* 1sequence* &key 1test* 1test-not* 1(start* 301)** 1end* 1key* 1from-end* Like 2position-if* and 2find-if* but search for an element which matches 1item*, using 1test* or 1test-not* for comparison. 3(position #\A "BabA" :test 'char-equal) => 1* 3(position #/A "BabA" :test 'equalp) => 1* 3(position #\A "BabA" :test 'char=) => 3* 3(position #/A "BabA" :test 'eq) => 3* 2find-position-in-list* is equivalent to 2position* with 2eq* as the value of 1test*. 3count-if* 1predicate* 1sequence* &key 1start* 1end* 1key* Tests each element of 1sequence* with 1predicate* and counts how many times 1predicate* returns non-2nil*. This number is returned. 1start*, 1end* and 1key* are used in the standard way, as described in 4(GENERIC-1)Operating on Selected Elements*. The 1from-end* keyword argument is accepted without error, but it has no effect. 3(count-if 'symbolp #(a b "foo" 3)) => 2 count-if-not* 1predicate* 1sequence* &key 1start* 1end* 1key* Like 2count-if* but returns the number of elements for which 1predicate* returns 2nil*. 3count* 1item* 1sequence* &key 1test* 1test-not* 1start* 1end* 1key* Like 2count* but returns the number of elements which match 1item*. 1test* or 1test-not* is the function used for the comparison. 3(count 4 '(1 2 3 4 5) :test '>) => 3* =Node: Comparison Functions =Text: 3COMPARISON FUNCTIONS mismatch* 1sequence1* 1sequence2* &key 1(test* 3'eql1)** 1test-not* 1(start1* 301)** 1end1* 1(start2* 301)** 1end2* 1key* 1from-end* Compares successive elements of 1sequence1* with successive elements of 1sequence2*, returning 2nil* if they all match, or else the index in 1sequence1* of the first mismatch. If the sequences differ in length but match as far as they go, the value is the index in 1sequence1* of the place where one sequence ran out. If 1sequence1* is the one which ran out, this value equals the length of 1sequence1*, so it isn't the index of an actual element, but it still describes the place where comparison stopped. Elements are compared using the function 1test*, which should accept two arguments. If it returns non-2nil*, the elements are considered to match. If you specify 1test-not* instead of 1test*, it is used similarly as a function, but the elements match if 1test-not* returns 2nil*. If 1key* is non-2nil*, it should be a function of one argument. It is applied to each element to get an object to pass to 1test* or 1test-not* in place of the element. Thus, if 2car* is supplied as 1key*, the cars of the elements are compared using 1test* or 1test-not*. 1start1* and 1end1* can be used to specify a portion of 1sequence1* to use in the comparison, and 1start2* and 1end2* can be used to specify a portion of 1sequence2*. The comparison uses the first element of each sequence portion, then the second element of each sequence portion, and so on. If the two specified portions differ in length, comparison stops where the first one runs out. In any case, the index returned by 2mismatch* is still relative to the whole of 1sequence1*. If 1from-end* is non-2nil*, the comparison proceeds conceptually from the end of each sequence or portion. The first comparison uses the last element of each sequence portion, the second comparison uses the next-to-the-last element of each sequence portion, and so on. When a mismatch is encountered, the value returned is 1one greater than* the index of the first mismatch encountered in order of processing (closest to the ends of the sequences). 3(mismatch "Foo" "Fox") => 2* 3(mismatch "Foo" "FOO" :test 'char-equal) => nil* 3(mismatch "Foo" "FOO" :key 'char-upcase) => nil* 3(mismatch '(a b) #(a b c)) => 2* 3(mismatch "Win" "The Winner" :start2 4 :end2 7) => nil* 3(mismatch "Foo" "Boo" :from-end t) => 1 search* 1for-sequence-1* 1in-sequence-2* &key 1from-end* 1test* 1test-not* 1key* 1(start1* 301)** 1end1* 1(start2* 301)** 1end2* Searches 1in-sequence-2* (or portion of it) for a subsequence that matches 1for-sequence-1* (or portion of it) element by element, and returns the index in 1in-sequence-2* of the beginning of the matching subsequence. If no matching subsequence is found, the value is 2nil*, The comparison of each subsequence of 1in-sequence-2* is done with 2mismatch*, and the 1test*, 1test-not* and 1key* arguments are used only to pass along to 2mismatch*. Normally, subsequences are considered starting with the beginning of the specified portion of 1in-sequence-2* and proceeding toward the end. The value is therefore the index of the earliest subsequence that matches. If 1from-end* is non-2nil*, the subsequences are tried in the reverse order, and the value identifies the latest subsequence that matches. In either case, the value identifies the beginning of the subsequence found. 3(search '(#\A #\B) "cabbage" :test 'char-equal) => 1* =Node: Sorting and Merging =Text: 3SORTING AND MERGING* Several functions are provided for sorting vectors and lists. These functions use algorithms which always terminate no matter what sorting predicate is used, provided only that the predicate always terminates. The main sorting functions are not 1stable*; that is, equal items may not stay in their original order. If you want a stable sort, use the stable versions. But if you don't care about stability, don't use them since stable algorithms are significantly slower. After sorting, the argument (be it list or vector) has been rearranged internally so as to be completely ordered. In the case of a vector argument, this is accomplished by permuting the elements of the vector, while in the list case, the list is reordered by 2rplacd*'s in the same manner as 2nreverse*. Thus if the argument should not be clobbered, the user must sort a copy of the argument, obtainable by 2fillarray* or 2copylist*, as appropriate. Furthermore, 2sort* of a list is like 2delq* in that it should not be used for effect; the result is conceptually the same as the argument but in fact is a different Lisp object. Should the comparison predicate cause an error, such as a wrong type argument error, the state of the list or vector being sorted is undefined. However, if the error is corrected the sort proceeds correctly. The sorting package is smart about compact lists; it sorts compact sublists as if they were vectors. See 4(MANLISTSTR-1)Cdr-Coding* for an explanation of compact lists, and MIT AI Lab Memo 587 by Guy L. Steele Jr. for an explanation of the sorting algorithm. 3sort* 1sequence* 1predicate* The first argument to 2sort* is a vector or a list whose elements are to be sorted. The second is a predicate, which must be applicable to all the objects in the sequence. The predicate should take two arguments, and return non-2nil* if and only if the first argument is strictly less than the second (in some appropriate sense). The 2sort* function proceeds to reorder the elements of the sequence according to the predicate, and returns a modified sequence. Note that since sorting requires many comparisons, and thus many calls to the predicate, sorting is much faster if the predicate is a compiled function rather than interpreted. Example: Sort a list alphabetically by the first symbol found at any level in each element. 3(defun mostcar (x)* 3 (cond ((symbolp x) x)* 3 ((mostcar (car x)))))* 3(sort 'fooarray* 3 #'(lambda (x y)* 3 (string-lessp (mostcar x) (mostcar y))))* If 2fooarray* contained these items before the sort: 3(Tokens (The alien lurks tonight))* 3(Carpenters (Close to you))* 3((Rolling Stones) (Brown sugar))* 3((Beach Boys) (I get around))* 3(Beatles (I want to hold you up))* then after the sort 2fooarray* would contain: 3((Beach Boys) (I get around))* 3(Beatles (I want to hold you up))* 3(Carpenters (Close to you))* 3((Rolling Stones) (Brown sugar))* 3(Tokens (The alien lurks tonight))* When 2sort* is given a list, it may change the order of the conses of the list (using 2rplacd*), and so it cannot be used merely for side-effect; only the 1returned value* of 2sort* is the sorted list. The original list may have some of its elements missing when 2sort* returns. If you need both the original list and the sorted list, you must copy the original and sort the copy (see 2copylist*, 4(MANLISTSTR-1)Lists*). Sorting a vector just moves the elements of the vector into different places, and so sorting a vector for side-effect only is all right. If the argument to 2sort* is a vector with a fill pointer, note that, like most functions, 2sort* considers the active length of the vector to be the length, and so only the active part of the vector is sorted (see 2array-active-length*, 4(ARRAYS-2)Getting Information About an Array*). 3sortcar* 1sequence* 1predicate* 2sortcar* is the same as 2sort* except that the predicate is applied to the cars of the elements of 1sequence*, instead of directly to the elements of 1sequence*. Example: 3(sortcar '((3 . dog) (1 . cat) (2 . bird)) #'<)* 3 => ((1 . cat) (2 . bird) (3 . dog))* Remember that 2sortcar*, when given a list, may change the order of the conses of the list (using 2rplacd*), and so it cannot be used merely for side-effect; only the 1returned value* of 2sortcar* is the sorted list. The original list is destroyed by sorting. 3stable-sort* 1sequence* 1predicate* 2stable-sort* is like 2sort*, but if two elements of 1sequence* are equal, i.e. 1predicate* returns 2nil* when applied to them in either order, then they remain in their original order. 3stable-sortcar* 1sequence* 1predicate* 2stable-sortcar* is like 2sortcar*, but if two elements of 1sequence* are equal, i.e. 1predicate* returns 2nil* when applied to their cars in either order, then they remain in their original order. 3sort-grouped-array* 1array* 1group-size* 1predicate* 2sort-grouped-array* considers its array argument to be composed of records of 1group-size* elements each. These records are considered as units, and are sorted with respect to one another. The 1predicate* is applied to the first element of each record; so the first elements act as the keys on which the records are sorted. 3sort-grouped-array-group-key* 1array* 1group-size* 1predicate* This is like 2sort-grouped-array* except that the 1predicate* is applied to four arguments: an array, an index into that array, a second array, and an index into the second array. 1predicate* should consider each index as the subscript of the first element of a record in the corresponding array, and compare the two records. This is more general than 2sort-grouped-array* since the function can get at all of the elements of the relevant records, instead of only the first element. 3merge* 1result-type* 1sequence1* 1sequence2* 1predicate* &key 1key* Returns a single sequence containing the elements of 1sequence1* and 1sequence2* interleaved in order according to 1predicate*. The length of the result sequence is the sum of the lengths of 1sequence1* and 1sequence2*. 1result-type* specifies the type of sequence to create, as in 2make-sequence*. The interleaving is done by taking the next element of 1sequence1* unless the next element of 1sequence2* is ``less'' than it according to 1predicate*. Therefore, if each of the argument sequences is sorted, the result of 2merge* is also sorted. 1key*, if non-2nil*, is applied to each element to get the object to pass to 1predicate*, rather than the element itself. Thus, if 1key* is 2car*, the cars of the elements are compared rather than the entire elements. 3(merge 'list '(1 2 5 6) '(3 5.0 5.1) '<)* 3 => (1 2 3 5 5.0 5.1 6)