.c	Saturday  Dec 10,1983  20:21  NM+6D.5H.17M.34S.  -*- Bolio -*-

.chapter "Sequences"
.setq sequence-chapter-number chapter-number
.setq sequence-section-page section-page
.cindex sequences

A sequence is considered to be either a list or a vector (which is by
definition a one-dimensional array).  lan{nil} supports a number of
operations on sequences, which may be applied equivalently to lists,
vectors, strings, and bit-vectors.

Many sequence function take 2start* and
2end* arguments to delimit some subpart of the sequence being
operated on.  As a general rule, the 2start* is 2inclusive*,
and the 2end* is 2exclusive*;  thus the length of the
subsequence is the difference of the 2end* and the 2start*.
The 2start* typically defaults to 30*, and the 2end* to
the length of the sequence.
Also, the 2end*, where it is an optional argument, may be
explicitly specified as 3nil*, and will still default to the
length of the sequence.  Thus,
.lisp
(find 2item* 2sequence*)
.end_lisp
searches the entire sequence,
.lisp
(find 2item* 2sequence* :start 5)
.end_lisp
and
.lisp
(find 2item* 2sequence* :start 5 :end nil)
.end_lisp
search from element number 5 onward,
.lisp
(find 2item* 2sequence* :end 5)
.end_lisp
checks the first five elements, and
.lisp
(find 2item* 2sequence* :start 5 :end 10)
.end_lisp
searches the subsequence (which has a length of 5) which consists of
the elements with indices 5, 6, 7, 8, and 9.

Functions which operate on two sequences generally take the start and
end for each of the sequences separately;  these are keyworded
arguments named 3:start1* and 3:end1* to specify the
subsequence of the first sequence, and 3:start2* and 3:end2*
to specify the subsequence of the second sequence.  See, for instance,
3replace* ((replace-fun)).

Many sequence functions (and many other functions) perform comparisons
of various sorts.  For instance, 3find* searches for an item in a
sequence.  3(find 2item* 2sequence*)* looks for an element
of 2sequence* which is 3eql* to 2item*, and returns that
element.  The particular
test used may be customized:  a different test function may be
specified by use of the 3:test* keyworded argument, as in
.lisp
(find 2item* 2sequence* :test #'equal)
.end_lisp
which uses 3equal* rather than 3eql*.  The sense of the test
can be reversed by using 3:test-not* instead of 3:test*:
.lisp
(find 2item* 2sequence* :test-not #'equal)
.end_lisp
returns the first element of 2sequence* which is 2not* equal
to 2item*.

Often, the elements of the sequence are not what is logically being
tested for, but rather some subpart of those elements.  For this,
rather than composing a new 3:test* function, one may specify a
3:key* function.  For instance,
.lisp
(find 2item* 2sequence* :key #'car)
.end_lisp
will return the first element of 2sequence* whose 3car* is
3eql* to 2item*.  This may also be used with 3:test* or
3:test-not*.  Note that the key function is only applied to
elements extracted from sequences, never to things like the 2item*
argument to 3find*.

Another class of functions do "searching" by means of a unary
predicate.  These functions invariably come in pairs;  one in which
the test is satisfied if the test function returns a non-3nil*
value, and one in which the test is satisfied if the test function
returns 3nil*:  for instance, 3position-if* and
3position-if-not*, and 3assoc-if* and 2assoc-if-not*.
Often these functions also take a 3:key* keyworded argument also;
if that is specified, then that function is applied to the datum being
tested and the result given to the test function.  For the sequence
functions, the datum would be the element of the sequence being
examined.

Finally, for things which go grovelling through sequences
sequentially, one may specify the direction by use of the
3:from-end* keyworded argument, which if not 3nil* means that
the result will be as if the subsequence was processed from the higher
to lower indices, rather than from lower to higher.  Unless explicitly
specified for a particular function, it may 2not* be depended on
that the sequence is actually processed in that order, only that the
end result is the same;  for this reason, it is generally a bad idea
if the comparison or key functions have any side effects, or depend on
the ordering of the elements on which they are called.


.section "Accessing Sequences"

.defun elt sequence index
This is the general sequence access function.  It returns the
2index*th element of 2sequence*;  the index is taken to be
zero-origined.  This will work generally on lists, vectors, strings
(which are by definition vectors anyway), etc.  One may modify an
element of a sequence by using 3setf*.  For instance,
.lisp
(setq v (make-vector 10))
  => #(nil nil nil nil nil nil nil nil nil nil)
(setf (elt v 5) 'foo)
  => foo
.end_lisp
And now,
.lisp
v => #(nil nil nil nil nil foo nil nil nil nil)
.end_lisp
It is an error for 2index* to be negative, or not less than the
length of 2sequence* as defined by 3length*.  This means that
it is an error to index pass the end of a list (in this 3elt*
differs from 3nth*, (nth-fun)), and also in its treatment of
vectors with fill pointers (the fill pointer defines the length--to
access anywhere within such a vector, use 3aref* ((aref-fun))).
.end_defun

.defun length sequence
Returns the length of 2sequence*.  If 2sequence* is a vector
with a fill pointer, the fill pointer is returned.  In lan{nil},
3length* will detect a circular list, and signal an error;  in
other implementations, it may fail to terminate--contrast the
definition of 3list-length*, (list-length-fun).

If 2sequence* is a list, it is an error for it to not terminate in
3nil*--in this, 3length* differs from previous implementations
of lan{nil}.
.end_defun


.section "Creating New Sequences"
.setq creating-sequences-section-page section-page

Many functions which create sequences take an argument which is the
type of sequence to be created;  it is typically called the
2result-type*, or perhaps just the 2type*.  This may be, in
general, a type specifier suitable for use with 3typep*, but must
of course be a subtype of 3sequence*--that is, a subtype of
3list* or 3vector*.  The type of sequence created will be the
most specific type of sequence which is a subtype of that specified
type.  At this time, the lan{nil} sequence
code has not been integrated with the lan{nil} array type code, so
it is possible that complicated type specifications will not work.
The following types will always work:  3list*, 3string*,
3simple-string*, 3bit-vector*, 3simple-bit-vector*,
3simple-vector*, and 3vector*.  3vector*, which is really
an abbreviation for the type specifier 3(array * (*))*, i.e., a
one-dimensional array of unspecified element-type, will create a
vector of element-type 3t*, i.e., a general vector.


.defun make-sequence result-type size &key initial-element
Makes a sequence of the given type and size.  The types of most
interest are 3list*, 3string*, 3vector*, and
3bit-vector*.  If the 3:initial-element* keyworded argument is
given, then the sequence is initialized with that element.  Otherwise,
the initialization depends on the type of the sequence.  For instance,
.lisp
(make-sequence 'list 5 :initial-element t)
  => (t t t t t)
(make-sequence 'string 5 :initial-element #\*)
  => "*****"
.end_lisp
.end_defun

.defun concatenate result-type &rest sequences
Creates a sequence of type 2result-type* (as might be given to
3make-sequence*), and stores in it the concatenation of all the
elements of 2sequences*.  For instance,
.lisp
(concatenate 'string "foo" "bar" "baz")
  =>  "foobarbaz"
(concatenate 'list "foo" "bar" '(1 2))
  => (#\f #\o #\o #\b #\a #\r 1 2)
.end_lisp
.end_defun

.defun subseq sequence start &optional end
Returns a sequence of the same general type as 2sequence*, containing
elements from 2start* up to (but not including) 2end*.
.lisp
(subseq "foo on you" 4)		=>  "on you"
(subseq "foo on you" 4 6)	=>  "on"
(subseq "foo on you" 4 3)	=>  2is an error*
(subseq '(a b c d) 1 3)		=>  (b c)
.end_lisp
Note that the result of 3subseq* never shares with the original
sequence.  Thus, 3(subseq 2list* 5)* is not the same as
3(nthcdr 5 2list*)*.  In fact, 3subseq* would signal an
error in this case if the 2list* did not have at least 5 elements.

The result of 3subseq* will always be a simple sequence;  if, for
instance, 2sequence* is an adjustable array of element-type
3string-char* and has a fill pointer, the result will just be a
simple string.
.end_defun

.defun copy-seq sequence
Copies the sequence 2sequence*.  This might be necessary if the
result is going to be modified, for instance.  The result of
3copy-seq* will always be a simple sequence, as described under
3subseq*.
.end_defun

See also the 3map* function, (map-fun), which produces a
sequence of the results of applying a function to the corresponding
elements of some input sequences.


.section "Searching through Sequences"

.defun find item sequence &key from-end start end test test-not key
3find* searches through the specified subsequence of
2sequence* until it finds an element which satisfies the specified
comparison against 2item*, in which case it returns that element;
if no match is found, 3find* returns 3nil*.  If a non-null
2from-end* argument is specified, then the result (if there is a
match) will be the "rightmost" element which matches 2item*,
otherwise it will be the "leftmost".
.end_defun

.defun find-if test sequence &key from-end start end key
.defun1 find-if-not test sequence &key from-end start end key
3find-if* returns an element of the specifed subsequence of
2sequence* which satisfies the function 2test*, or 3nil*
if no such element is found.  If a
2key* argument is specified, then 2test* is called on the
result of calling 2key* on an element of the sequence;  otherwise,
2test* is called on the element directly.  If a non-null
2from-end* argument is specified, then the result will be the
rightmost such element within the subsequence;  otherwise, it will be
the leftmost.

3find-if-not* is similar, but succeeds if the result of calling
2test* is 3nil*.
.end_defun

.defun position item sequence &key from-end start end test test-not key
If there is an element of the specified subsequence of 2sequence*
which matches 2item* according to the specified test, then
3position* returns its index (the index within 2sequence*, not
within the subsequence);  otherwise, 3position* returns 3nil*.
If a non-null 2from-end* argument is specified, then the result is
the index of the leftmost element satisfying the test;  otherwise, it
is the index of the rightmost such element.
.end_defun

.defun position-if test sequence &key from-end start end key
.defun1 position-if-not test sequence &key from-end start end key
3position-if* returns the index of an element within the specified
subsequence which satisfies the test function 2test*.  If
2key* is specified, it is a function called on the element of the
sequence, and that result is given to 2test* instead of the
element itself.  If a non-null 2from-end* argument is specified,
then the index will be of the rightmost such element;  otherwise, of
the leftmost.  If no such element is found in the subsequence,
3nil* is returned.  As with 3position* and all similar
functions, the index is the index within 2sequence*, not within
the subsequence.

3position-if-not* is similar, but succeeds if the result of
calling 2test* is 3nil*.
.end_defun

.defun count item sequence &key from-end start end test test-not key
3count* returns the count of elements within the specified
subsequence of 2sequence* which satisfy the specified comparison
against 2item*.  The test function may depend on the order in
which the elements are processed:  if a non-null 2from-end*
argument is specified, then the elements will be processed from right
to left (i.e., decreasing indices);  otherwise, from left to right
(increasing indices).  As usual, the first argument to the test is
2item*, and the second is the element of 2sequence* if no
2key* is specified, otherwise the result of calling 2key* on
the element.
.end_defun

.defun count-if test sequence &key from-end start end key
.defun1 count-if-not test sequence &key from-end start end key
3count-if* returns the count of the elements of subsequence which
satisfy the unary predicate 2test*.  If no 2key* is specified,
2test* is called on the elements of the subsequence;  otherwise,
it is called on the result of applying 2key* to each element.  If
a non-null 2from-end* argument is specified, then the elements are
processed from right to left (decreasing indices), otherwise from left
to right.

3count-if-not* is similar, but reverses the sense of 2test*.
.end_defun

.c .defun mismatch...
.c .defun search...

.section "Miscellaneous Operations on Sequences"

.defun reverse sequence
Returns a copy of 2sequence*, with the elements in the opposite
order.
.end_defun

.defun nreverse sequence
Reverses 2sequence*, destructively;  it does not create a copy.
Note that if 2sequence* is a list, one should always use the
return value of 3nreverse*;  that is, do something like
.lisp
(setq l (nreverse l))
.end_lisp
rather than just
.lisp
(nreverse l)
.end_lisp
This is in general true for all destructive list operations, such as
3sort* and 3delq*.  The reason is that although the cons cells
of the input list are reused, the pointer returned is not necessarily
the same as the original "first" cons of the list.
.end_defun

.defun fill sequence element &key start end
Replaces the elements of 2sequence* with 2element*, from
2start* (default 0) up to 2end* (default length of the
sequence).
.lisp
(setq a '(0 1 2 3 4 5 6))
(fill a nil :start 2 :end 4)
  =>  (0 1 nil nil 4 5 6)
.end_lisp
And now,
.lisp
a  =>  (0 1 nil nil 4 5 6)
.end_lisp
.end_defun

.defun replace sequence1 sequence2 &key start1 end1 start2 end2
Replaces the elements of the specified subsequence of 2sequence1*
by the elements of the specified subsequence of 2sequence2*.
.lisp
(setq v (make-sequence 'vector 10))
  => #(nil nil nil nil nil nil nil nil nil nil)
(replace v '(1 2 3 4 5 6))
  => #(1 2 3 4 5 6 nil nil nil nil)
v => #(1 2 3 4 5 6 nil nil nil nil)
.end_lisp
The number of elements transfered is the minimum of the lengths of the
two subsequences, i.e.,
.lisp
(min (- end1 start1) (- end2 start2))
.end_lisp
.end_defun

.defun remove item sequence &key from-end start end test test-not key count
3remove* returns a copy of 2sequence* of the same general
type, except that elements within the specified subsequence which
match 2item* according to the specified test are not copied.  If
the 2count* argument is specified, then it should be a
non-negative integer which limits the number of matching elements
which get "ignored";  if it is not specified, 2all* matching
elements within the specified subsequence will be missing from the
result.  The 2from-end* flag is only really meaningful if a
2count* is specified;  if a non-null 2from-end* is specified,
then the rightmost 2count* elements of the specified subsequence
will be missing from the result, otherwise the leftmost.
.end_defun

.defun remove-if test sequence &key from-end start end key count
.defun1 remove-if-not test sequence &key from-end start end key count
Like all similar extensions.
.end_defun

.defun delete item sequence &key from-end start end test test-not key count
This is the destructive version of 3remove*, q.v.;  it will attempt to
use 2sequence* to construct its result.  The result may or may not
be 3eq* to 2sequence*, and 2sequence* may or may not be
actually modified to produce the result:  lan{nil} will attempt to
do this the "best way" it can.  For this reason, 3delete* should
2only* be used for value, never strictly for effect.

3delete* will succeed in side-effecting 2sequence* to produce
its result if 2sequence* is (1) a list, (2) an adjustable vector
of any type, or (3) a vector with a fill pointer.  The result is still
not guaranteed to be 3eq* to 2sequence*.
.end_defun

.defun delete-if test sequence &key from-end start end key count
.defun delete-if-not test sequence &key from-end start end key count
Similar, by extension.
.end_defun

.defun substitute new old sequence &key from-end start end test test-not key count
3substitute* returns a new sequence in which the elements within
the specified subsequence matching 2old* according to the
specified test have 2new* substituted.  While 3substitute*
does not modify 2sequence*, the result may share with
2sequence*;  in particular, if 2sequence* is a list, the
result may share a tail.

If a 2count* argument is specified, then this is a
non-negative integer which limits the number of substitutions made.
In this case, specifying a non-null 2from-end* argument causes the
rightmost 2count* elements matching 2old* to undergo
substitution, otherwise the leftmost.
.end_defun

.defun substitute-if new test sequence &key from-end start end key count
.defun1 substitute-if-not new test sequence &key from-end start end key count
Similar, by extension.
.end_defun

.defun nsubstitute new old sequence &key from-end start end test test-not key count
The destructive version of 3substitute*;  2sequence* is
modified.
.end_defun

.defun nsubstitute-if new test sequence &key from-end start end key count
.defun1 nsubstitute-if-not new test sequence &key from-end start end key count
Similar.
.end_defun



.section "Iteration over Sequences"

The following functions iterate a user-specified function over one or
more sequences in various ways.  They might not be handled specially by the
lan{nil} compiler yet, however, so cases where the function is a
3#'(lambda ...)* form will not compile if the lambda expression
contains free references to lexical variables in the containing code.
Also, because the sequences are general sequences, the compiler will
probably have to access them using 3elt*, which may be inefficient
for long lists.

.defun map result-type function &rest sequences
This is the general sequence mapping function.  Note that this is
different from the lan{maclisp} and lan{zetalisp} 3map*
function, which is renamed to 3mapl* by lan{common lisp}.

The result is a new sequence of type 2result-type* (see
(creating-sequences-section-page)), containing the results of applying
2function* to the elements of 2sequences*.  There must be at
least one 2sequence* specified;  2function* gets as many
arguments as there are sequences--first it gets called on all of the
first (index 0) elements, then on all the second elements, etc.  The
iteration terminates when the end of any of the sequences is reached,
so the result will have the same length as the shortest input
sequence.
.lisp
(map 'list #'cons "abc" '(a b c d e f))
  => ((#\a . a) (#\b . b) (#\c . c))
.end_lisp
If 2result-type* is 3list*, and the input sequences are all
lists, then this is effectively the same as 3mapcar* ((mapcar-fun)).
.end_defun

.defun some predicate &rest sequences
3some* applies the function 2predicate* to the corresponding
elements of 2sequences* (of which there must be at least one), in
order.  If the result of some application is not 3nil*, then
3some* immediately terminates the iteration and returns that
value;  if all the applications returned 3nil*, 3some* returns
3nil*.

The predicate may depend on being called on the elements of the
sequences in order.  Only as many elements as there are in the
shortest sequence are processed.

The effect of this may also be obtained by use of the 3thereis*
clause in the 3loop* macro ((loop-fun)).
.end_defun

.defun every predicate &rest sequences
Like 3some*, but returns 3t* if the result of applying
2predicate* to the elements of 2sequences* is never 3nil*;
if some application of 2predicate* is 3nil*, then 3every*
terminates immediately and returns 3nil*.

The effect of this may also be obtained by use of the 3always*
clause in the 3loop* macro ((loop-fun)).
.end_defun

.defun notany predicate &rest sequences
Returns 3t* if the result of applying the function 2predicate*
to the corresponding elements of 2sequences* is always 3nil*;
if the result of that application is not 3nil*, then 3notany*
immediately terminates the iteration and returns 3nil*.

The effect of this may also be obtained by use of the 3never*
clause in the 3loop* macro ((loop-fun)).
.end_defun

.defun notevery predicate &rest sequences
If the result of some application of 2predicate* to the
corresponding elements of 2sequences* is 3nil*, then
3notevery* terminates its iteration and returns 3t*;
otherwise, it returns 3nil*.
.end_defun


.section "Sorting Sequences"

.defun sort sequence predicate &key key
This is the lan{common lisp} 3sort* function;  when it is used
without a 2key*, it is lan{maclisp} compatible.

2sequence* is destructively sorted according to the predicate
2predicate*, which receives two arguments and should return a
non-null value only if its first argument is strictly less than its
second argument.  If 2key* is specified, then it is a function of
one element which is applied to the sequence element before being
passed on to the predicate.

For lan{maclisp} compatibility, if 2sequence* is a list, then
the sort is 2stable*;  equivalent pairs of items (those where the
two keys are neither strictly less than each other) remain in their
original order.  When 2sequence* is a vector, a quicksort
algorithm is used.
.end_defun

.defun sortcar sequence predicate
This is provided for lan{maclisp} compatibility.  It is just like
.lisp
(sort 2sequence* 2predicate* :key #'car)
.end_lisp
.end_defun

.defun stable-sort sequence predicate &key key
Like 3sort*, but 2guarantees* that the sort will be stable (see
3sort*).  If 2sequence* is a vector, then a bubble sort is
used.
.end_defun

