.c	Saturday  Dec 10,1983  00:07  NM+5D.9H.3M.20S.  -*- Bolio -*-

.chapter "Lists"

Note also 3consp* ((consp-fun)), 3listp* ((listp-fun)).

.section "Creating, Accessing, and Modifying List Structure"

.defun car cons
.defun1 cdr cons
.defun c....r cons
.findex caar
.findex cadr
.findex cdar
.findex cddr
.findex caaar
.findex caadr
.findex cadar
.findex caddr
.findex cdaar
.findex cdadr
.findex cddar
.findex cdddr
.findex caaaar
.findex caaadr
.findex caadar
.findex caaddr
.findex cadaar
.findex cadadr
.findex caddar
.findex cadddr
.findex cdaaar
.findex cdaadr
.findex cdadar
.findex cdaddr
.findex cddaar
.findex cddadr
.findex cdddar
.findex cddddr
.comment yow!
lan{nil} defines all compositions of 3car* and 3cdr* up to
four levels deep;  for instance, 3(cddar 2cons*)* is
equivalent to 3(cdr (cdr (car 2cons*)))*.

Actually, 2cons* may be either a cons or 3nil*;  the 3car*
and 3cdr* of 3nil* are 2always* 3nil*.

Normally in lan{nil}, 3car*, 3cdr*, and their compositions
compile into special subroutine calls into the lan{nil} kernel which
do error checking, but are much faster than function calling.
Directing the compiler to produce faster code by use of the
3speed* quality in the 3optimize* declaration will cause all
of these accesses to be completely inline coded, without checking;  see
(compilation-declarations-section-page).  (In lan{nil}, 3car*
and 3cdr* each take only one instruction.)

All of these functions may be used with 3setf* in order to update
the particular component of 2cons*.
.end_defun

.defun rplaca cons new-car
.defun1 rplacd cons new-cdr
3rplaca* modifies the 3car* of 2cons* to be 2new-car*,
and returns 2cons*;  3rplaca* modifies the 3cdr*.
See also 3setf* ((setf-section-page)) which can be used to
update any of the above car/cdr references.

These functions, and the use of 3setf* with 3car*, 3cdr*,
and friends, are normally coded by the lan{nil} compiler as special
subroutine calls into the lan{nil} kernel which do argument
checking, but are faster than function calls.  Use of the 3speed*
quality with the 3optimize* declaration may override this;  see
(compilation-declarations-section-page).
.end_defun


.defun first list
.defun1 second list
.defun1 third list
.defun1 fourth list
.defun1 fifth list
.defun1 sixth list
.defun1 seventh list
.defun1 eighth list
.defun1 ninth list
.defun1 tenth list
3car*, 3cadr*, etc.  These may all be used with 3setf*.

Note that the names of these functions use one-origin indexing:
.lisp
(third 2x*)  <==>  (nth 2 2x*)  <==>  (elt 2x* 2)
.end_lisp
.end_defun

.defun rest list
3cdr*.  This may be used with 3setf*.
.end_defun

.defun nth index list
Returns the 2index*th element of 2list*, zero origined.  Note
also that this takes its arguments in a different order than 3elt*
(and other more specialized sequence accessors).

If 2index* is not less than the length of 2list*, 3nth*
returns 3nil* by analogy to 3car* and 3cdr*.  In this it
also differences from 3elt*.
.end_defun

.defun nthcdr ntimes list
Returns 2list* after 2ntimes* 3cdr*s have been taken on
it.
.end_defun

Note also the 3`* reader-macro ((backquote-section-page)),
which is convenient for creating list structure in template form,
especially if large portions of it are constant, and 3push*
((push-fun)) and 3pop* ((pop-fun)) which can be used to
maintain a list in FIFO form in an arbitrary 3setf*able place.

.defun cons x y
Makes a 3cons* whose 3car* is 2x*, and whose 3cdr* is
2y*.
.end_defun

.defun ncons x
Equivalent to 3(cons 2x* nil)*.
.end_defun

.defun xcons x y
"Exchanged" cons.  Equivalent to 3(cons 2y* 2x*)*.  This
function is not normally used;  it is inherited from lan{maclisp},
where its existence is mainly for the benefit of the compiler in
rewriting calls to 3list* into calls it could chain together the
computations of better:
.lisp
(list 2x* 2y* 2z*)
  ==>  (xcons (xcons (ncons 2z*) 2y*) 2x*)
.end_lisp
.end_defun

.defun list &rest elements
Returns a freshly created list of its arguments.
.lisp
(list)			=>  nil
(list 'x)		=>  (x)
(list 'x 'y)		=>  (x y)
.end_lisp
.end_defun

.defun list* first-thing &rest other-things
Sort of like 3list*, but the last argument to 3list** is used
as the 3cdr* of the final cons, instead of 3nil*.
Alternatively, it may be thought of as many nested conses:
.lisp
(list* 'a)		=>  a
(list* 'a 'b)		=>  (a . b)
(list* 'a 'b 'c)	=>  (a b . c)
(list* 'a 'b nil)	=>  (a b)
.end_lisp
.end_defun

.defun make-list size-of-list &key initial-element
Creates a list of 3nil*s 2size-of-list* long, whose elements
are 2initial-element* (which defaults to 3nil*).
.end_defun

.defun append &rest lists
3(append 2x* 2y*)* returns a list which has first all of
the elements of 2x*, followed by all of the elements of 2y*;
for instance,
.lisp
(append '(a b) '(x y))	=>  (a b x y)
.end_lisp
The subpart of this list (in the example, the 3cddr*) is the
original last argument to 3append*;  3append* never copies its
last argument.
.lisp
(append 2x* 2y* 2z*)
  ==> (append 2x* (append 2y* 2z*))
.end_lisp
When given one argument, 3append* returns that argument;  with no
arguments, it returns 3nil*.

If just copying a list is desired, it is stylistically better to use
3(copy-list 2list*)* ((copy-list-fun)) rather than
3(append 2list* nil)*.
.end_defun

.defun revappend list1 list2
This is like 3(append (reverse 2list1*) 2list2*)*, but is
more efficient because it only has to make one pass over 2list1*.
.end_defun

.defun last list
Returns the last cons of 2list* (2not* the last element!),
unless 2list* is (false), in which case it returns (false).
In lan{nil}, 3last* deals properly with a non-null last
3cdr* of 2list*.  The only non-cons it will accept as an
argument however is (false).
.lisp
(last '(1 2 3 4 5))  =>  (5)
(last '(a b . c))    =>  (b . c)
(last nil)	     =>  nil
.end_lisp
.end_defun

.defun nconc &rest lists
Joins together all of the 2lists* by destructively modifying them.
Specifically, for each of the 2lists* which is not 3nil*, the
final cons (as might be returned by 3last*) is modified by
3rplacd* to be the next list.
.lisp
(setq l1 '(a b))
(setq l2 '(x y))
(nconc l1 l2)	     =>  (a b x y)
.end_lisp
and now,
.lisp
l1		     =>  (a b x y)
.end_lisp
One should be careful, however, about using 3nconc* strictly for
effect (i.e., not using the returned value), because if the first list
is 3nil* (the empty list) the desired side-effect will not occur.
.end_defun

.defun nreconc list1 list2
This is like 3(nconc (nreverse 2list1*) 2list2*)*, but can
be faster because it only has to make one pass over 2list1*.
.end_defun

.defun list-length list
3list-length* returns the length of the list 2list*.  If
2list* is circular, then 3list-length* returns 3nil*--in
this it differs from 3length*, which in lan{nil} will signal an
error but in other lan{common lisp} implementations may fail to
terminate.

It is an error for 2list* to not terminate with 3nil*
(assuming it is not circular).  In this, 3list-length* differs
from its implementation in previous releases of lan{nil}.
.end_defun

.defun copy-list list
Copies the top-level conses of 2list*.  This may be used to
replace the common idiom
.lisp
(append 2list* ())
.end_lisp
and, additionally, handles a non-null last 3cdr* of 2list*
gracefully.
.end_defun

.defun copy-alist a-list
Like 3copy-list*, and additionally, each top-level element of
2a-list* which is a cons has that first cons copied also
(2not* the entire top-level of the a-list entry).

Note that this function name contains "alist", a term which is spelled
"a-list" everywhere else now.

This replaces the lan{lispm} function fun_i{copyalist}, which
exists identically in lan{nil}.
.end_defun

.defun copy-tree tree
Returns a copy of 2tree*.  Recurses through both the 2car* and
the 3cdr*, terminating at non-conses.  That is, only conses are
copied.  This replaces the old lan{maclisp} idiom
.lisp
(subst nil nil 2tree*)
.end_lisp
which has been changed incompatibly by lan{common lisp}
((subst-fun)).

This function is the lan{common lisp} equivalent of the lan{lispm}
fun_i{copytree} function, which is defined in lan{nil} as a
synonym for 3copy-tree*.
.end_defun

.defun butlast list &optional (n 1)
This returns a copy of 2list*, but without the last 2n*
elements.  If the length of the list is less than or equal to 2n*,
3nil* is returned.
.lisp
(butlast '(1 2 3))    =>  (1 2)
(butlast '(1 2 3) 2)  =>  (1)
(butlast '(1))        =>  nil
(butlast nil)         =>  nil
.end_lisp
.end_defun

.defun nbutlast list &optional (n 1)
Destructive version of 3butlast*;  the last 2n* elements of
2list* are "spliced out", by 3rplacd*.  3nbutlast* should
be used for value, however, because if the length of the list is less
than or equal to 2n*, 3nil* is returned and no "splicing" is
performed.
.end_defun

.defun tailp sublist list
3tailp* returns 3t* if 2sublist* is a sublist of
2list*, 3nil* otherwise.  What this means is that after taking
some number of 3cdr*s of 2list* (possibly zero), one gets to a
list 3eq* to 2list*.
.end_defun

.defun ldiff list sublist
If 3(tailp 2sublist* 2list*) is true, 3ldiff* ("list
difference") returns a list of the elements of 2list* up to but
not including 2sublist*.  This is the same as 
.lisp
(nbutlast 2list* (length 2sublist*))
.end_lisp

If 3(tailp 2sublist* 2list*)* is false, 3ldiff* simply
returns a copy of 2list*.
.end_defun

.section "Substitution"

These functions are extensions of the 3subst* and 3sublis*
functions which are defined by lan{maclisp} and lan{lispm}.  Note
that they by default use 3eql* to test for equality;  this is
incompatible with lan{maclisp} and an early release of
lan{nil}, in which 3subst* used 3equal* but 3sublis*
used 3eq* (but only worked on symbols).  A different test may be
specified by use of the 3:test* keyworded argument;  this is a
predicate of two arguments used to test "equality".  If it is more
convenient, the sense of the predicate may be reversed by use of the
3:test-not* keyword.

Note also that these functions only descend through list structure
("trees");  they do not look inside of vectors, arrays, or other
structures.

.defun subst new old tree &key test test-not key
Returns a copy of 2tree*, with 2new* substituted when a
of the tree matches 2old* according to the test.

This is 2incompatible* with lan{maclisp} 3subst*, in that
the result is 2not* guaranteed to always copy even if substitution
is not performed.  The lan{maclisp} idiom 3(subst nil nil
2tree*)* is replaced by the 3copy-tree* function
((copy-tree-fun)).  Be on the lookout for the use of this idiom in
old code, for it can cause obscure bugs when uncopied structure is
modified.  The lan{nil} compiler will warn about use of this idiom
and turn the 3subst* into a call to 3copy-tree* if (1) there
are no keyworded arguments supplied (2) 2new* and 2old* are
constants determinable at compile-time and (3) their values are
3eql*.  The runtime function cannot detect this idiom.
.end_defun

.defun nsubst new old tree &key test test-not key
Like 3subst*, but does not copy:  the new components are
destructively stored in 2tree*.  However, this should be used for
value, for if 2tree* matches 2old*, the result is 2new*
but no bashing of list structure is done.
.end_defun

.defun sublis a-list tree &key test test-not key
Like 3subst*, but performs substitution for several things at
once.  2a-list* is an association list of the objects to match,
and their replacements.  For example,
.lisp
(sublis '((yes . no) (t . nil)) '(t generally means yes))
  => (nil generally means no)
.end_lisp
.end_defun

.defun nsublis a-list tree &key test test-not key
Like 3sublis*, but destructive.  See also 3nsubst*.
.end_defun


.section "Using Lists as Sets"

One common use of lists is as sets of objects.  lan{nil} (and
lan{common lisp}) provide a complement of functions for doing this.

All of the functions take similar arguments.  Normally, they use
3eql* as their predicate, so that they work on numbers properly
also.  If this is not suitable for the purpose, then a predicate may
be specified by giving it as the 3:test* keyworded argument.  For
instance,
.lisp
(union '((a b) (b) (c)) '((d) (e) (a b) (b)) :test #'equal)
  => ((a b) (b) (c) (d) (e))
.end_lisp
The sense of the predicate can be reversed by using 3:test-not*
instead of 3:test*.

Sometimes the elements of the set are datastructures of some sort, and
one desires to only compare one part of the datastructure, but not
write a predicate to compare things.  If the 3:key* keyworded
argument is used, then that is a function which will be applied to
each element as it is tested, and the results of that will be given to
the equality predicate, rather than the elements themselves.  For
example,
.lisp
(union '((a) (b) (c)) '((d) (e) (a) (b)) :key #'car)
  => ((a) (b) (c) (d) (e))
.end_lisp
The 3:key*-specified function is only applied to elements
extracted from lists, never to single 2item* arguments given to
any of these functions (such as 3member*, below).
The ordering of the result may not be depended on;  neither may the
result if either of the inputs contains duplicate elements (as defined
by the predicate), nor the particular choice of element (that is, the
one from the first list or the one from the second list).  Thus,
.lisp
(union '((a) (b x) (c)) '((d) (e) (e) (b y)) :key #'car)
.end_lisp
might return either of the sets
.lisp
((a) (b x) (c) (d) (e))
.end_lisp
or
.lisp
((a) (b y) (c) (d) (e))
.end_lisp
since they are equivalent according to the test criteria.

.defun member item list &key test test-not key
If 2item* is a member of 2list* according to the specified
test (which defaults to 3#'eql*), then member returns the sublist
whose 3car* satisfied the test.  Otherwise, 3nil* is returned.
The other functions in this section are implemented in terms of this.
Note that if a function is specified with 3:key*, it is only
applied to items of 2list*, not to 2item*.

2Note that the default predicate for 3member*, 3#'eql*, is
incompatible with* lan{maclisp} 3member*.  This provides
consistency with all other similar functions.
.end_defun

.defun memq item list
This is 3member* with a test of 3#'eq*.  3memq* is not
defined by lan{common lisp}, but is inherited from lan{maclisp}.
It is specially handled by the lan{nil} compiler.
.end_defun

.defun union list1 list2 &key test test-not key
Returns the union of 2list1* and 2list2*.
.end_defun

.defun nunion list1 list2 &key test test-not key
The destructive version of 3union*.  The returned list will be
composed of conses obtained from 2list1* and/or 2list2*.  This
should be used for value, however, not for effect.
.end_defun

.defun intersection list1 list2 &key test test-not key
Returns the intersection of 2list1* and 2list2*.
.end_defun

.defun nintersection list1 list2 &key test test-not key
3intersection*, except that the conses of 2list1* and/or
2list2* are used to construct the result.
.end_defun

.defun set-difference list1 list2 &key test test-not key
Returns the set difference of 2list1* and 2list2* (a list of
the elements of 2list1* which are not present in 2list2*,
according to the predicate).
.end_defun

.defun nset-difference list1 list2 &key test test-not key
Destructive 3set-difference*;  the result is constructed from the
conses of 2list1* and/or 2list2*.
.end_defun

.defun set-exclusive-or list1 list2 &key test test-not key
Returns a list of the elements which occur in either 2list1* or
2list2*, but not both, according to the predicate.
.end_defun

.defun nset-exclusive-or list1 list2 &key test test-not key
Destructive 3set-exclusive-or*;  the result is constructed from
the conses of 2list1* and/or 2list2*.
.end_defun

.defun subsetp list1 list2 &key test test-not key
Returns 3t* if 2list1* is a subset of (but not necessarily a
proper subset of) 2list2*, 3nil* otherwise.
.end_defun

.defun adjoin item list &key test test-not key
If 2item* is a member of 2list* according to the specified
test, this just returns 2list*;  otherwise, it conses 2item*
onto the front of 2list*, and returns that.  3adjoin* could
have been defined as
.lisp
(defun adjoin (item list &rest keyworded-args
	       &key test test-not key)
  (if (apply #'member item list keyworded-args)
      list
      (cons item list)))
.end_lisp
which also shows the utility of the 3&rest* keyword combined with
3&key*.
.end_defun


.section "Association Lists"

Association lists are an abstraction built from lists which are useful
in many cases.  An term_i{association list} (or term_i{a-list},
sometimes misspelled 2alist* in this document), is a list, all
elements of which are conses;  the 3car* of each cons is the
2key*, and the 3cdr* of each cons is the data associated with
that key.  Association lists differ slightly from just lists used as
sequences utilizing a key of 3car* (or 3cdr*):  if an entry in
an association list is the atom 3nil*, then it will be ignored
totally.  Functions which deal with more general sequences or lists,
such as 3member*, 3find*, and 3position*, would blindly
apply the supplied key (e.g., 3car*) to 3nil*, and try
matching this against the item being searched for.

There are two common ways in which association lists are used.
For one, what is being constructed is basically just a table with
entries of a single key.  In this, the entries in the a-list are
conses of the key and the data associated with the key, and one uses
3assoc* with an appropriate test to do the lookup;  the data of
the key may be replaced by using 3rplacd* on the result of the
3assoc*, assuming 3assoc* did not return 3nil*.  There are
two potential disadvantages with this approach.  First, the lookup is
linear, so the lookup time grows linearly with the length of the
table.  How much this matters depends on the efficiency of the
equality predicate in use;  3eq* is extremely fast, and 3eql*
is fairly fast, so this could matter a fair amount if they are the
predicates in use.  Second, because a-lists are constructed out of
conses, they can be scattered all over virtual memory and cause poor
paging performance;  it is possible for each cons in an a-list to lie
on a different page.  If entries are only rarely added to or removed
from the table (entire entries, not just update of the 3car* or
3cdr* of an a-list entry), it might be reasonable to ensure that
the a-list lies in fairly contiguous virtual memory by copying it with
3copy-alist* ((copy-alist-fun)) when something is added to it.
Some rough
guesses, with a test of 3eq*:  if the a-list has over 50 entries,
it is probably better to use a hash table.  For 70 or 80, a hash table
is virtually guaranteed to be better, unless most of the lookups will
succeed, and find entries near to the front.  For between 5 and 10
entries, an a-list is almost undoubtedly best, and can be optimized by
copying with 3copy-alist*.  For values between 10 and 50, the
decision on which to use requires balancing additions and deletions
against wasting time (and creating garbage) using 3copy-alist*.
Probably it is best to only do the copying with 3copy-alist* for
tables which are not updated in the "normal course of program
running", i.e., which might only be updated when new files are loaded.

The other common use of a-lists is where the implicit ordering of a
list comes into play.  One entry in the association list might have
the same key as another which occurs "later" in the a-list;
since association lists are always searched in left-to-right order,
the first occurence will 2shadow* any other occurences.  A simple
lan{lisp} lexical interpreter might use an association list to hold
the lexical variable bindings, for instance.  "Binding" pushes the new
variable/value pair on the front of the "environment" a-list, and
"unbinding" pops the entry off.  For this sort of use, hash tables do
not present an alternative without some hairy hacking of "contexts".

A third possible use of an a-list is for two-way associations;  that
is, the 3car* and 3cdr* may both be viewed as keys used to
look up the other;  one uses 3assoc* to find the entry by the
3car* key, and 3rassoc* to find the entry by the 3cdr*
key.  Hash tables do not provide this sort of service;  if a-list
lookup time is prohibitive in a particular case, the alternative is to
use 2two* hash tables.

.defun assoc item a-list &key test test-not
Searches 2a-list* for an entry whose 3car* matches 2item*
according to the specified test.  If one is found, that cons is
returned;  otherwise 3nil* is returned.  If a non-null result is
returned, the datum of it may be modified by use of 3rplacd*.

Note also that since the default test is 3#'eql*, this is
incompatible with lan{maclisp} 3assoc*.  To retain the same
effect, one must use
.lisp
(assoc 2item* 2a-list* :test #'equal)
.end_lisp
or simply 3assq* (below).
Of course, often the choice of 3assoc* in lan{maclisp} is
because 2item* is a number, so 3equal* is not needed in
lan{nil} because 3eql* compares numbers correctly.
.end_defun

.defun rassoc item a-list &key test test-not key
Like 3assoc*, except that 2item* is matched against each datum
in 2a-list*, rather than each key.
.end_defun

.defun assq item a-list
This is inherited from lan{maclisp} and also is defined by
lan{lispm};  it is 2not* defined by lan{common lisp}.  It is
identical to
.lisp
(assoc 2item* 2a-list* :test #'eq)
.end_lisp
Compilation of 3assq* does 2not* produce any different code
than the above form, so the choice between the two is between
lan{common lisp} compatibility and verbosity in the source code.
.end_defun

.defun rassq item a-list
This is inherited from lan{lispm};  it is not defined by
lan{common lisp}.  It is the same as
.lisp
(rassoc item a-list :test #'eq)
.end_lisp
See 3assq* (above) for more qualifications.
.end_defun

.defun acons key datum a-list
This is the same as
.lisp
(cons (cons 2key* 2datum*) 2a-list*)
.end_lisp
but shows the intent better.
.end_defun

.defun pairlis keys data &optional a-list
Returns an a-list made by associating 2keys* and 2data* and
adding them to the front of 2a-list* (which defaults to
3nil*).  2keys* and 2data* must be lists of the same
length.
.lisp
(pairlis '(foo bar) '("Foo" "Bar") '((baz . "Baz")))
  =>  ((foo . "Foo") (bar . "Bar") (baz . "Baz"))
.end_lisp
The result will share structure with 2a-list* (that is,
2a-list* 
, so modifications to
the associations in the returned result will affect those assocations
in 2a-list* also.
.end_defun

