{Begin SubSec Lists}
{Title Lists}
{Text


{index *PRIMARY* lists}
{index *PRIMARY* list cells}

One of the most useful datatypes in Interlisp is the list cell, a data structure which contains pointers to two other objects, known as the {lisp CAR} and the {lisp CDR} of the list cell (after the accessing functions).  Very complicated structures can be built out of list cells, including lattices and trees, but list cells are most frequently used for representing simple linear lists of objects.

The following functions are used to manipulate list cells:


{FnDef {FnName CONS} {FnArgs X Y}
{Text
{fn CONS} is the primary list construction function.  It creates and returns a new list cell containing pointers to {arg X} and {arg Y}.  If {arg Y} is a list, this returns a list with {arg X} added at the beginning of {arg Y}.

{note Note:  Many Interlisp implementations try to improve performance by locating a new list cell close to its arguments.}

{note In Interlisp-D, a special encoding technique called CDR-coding has been used to create a compact representation of lists whenever possible.  --- Gadol}
}}



{FnDef {FnName CAR} {FnArgs X}
{Text
Returns the first element of the list {arg X}.  {fn CAR} of {lisp NIL} is always {lisp NIL}.  For all other nonlists (e.g., litatoms, numbers, strings, arrays), the value is undefined (and in some implementations may generate an error).
}}


{FnDef {FnName CDR} {FnArgs X}
{Text
Returns all but the first element of the list {arg X}.  {fn CDR} of {lisp NIL} is always {lisp NIL}.  The value of {fn CDR} is undefined for other nonlists.
}}


{Begin Note}
In Interlisp-D, if you call CAR  or CDR of anything other than a list or NIL, it will call \CAR.UFN or \CDR.UFN. These currently have a definition which checks the globasl variable CAR/CDRERR and if that variable is non-NIL, they will generate an error. I've tried running with CAR/CDRERR and there are many many places in the system which break in various ways. When we fix them all, we can turn CAR/CDRERR on permanently. Until then, CAR(atom) => NIL, CDR(atom) => prop list, and applying those functions to anything else return a string "{bracket car of non-list}" etc. -Larry

In Interlisp-10, these both produce unpredictable garbage.  Will I-10 ever be changed?

Probably, none of this should be documented, to allow changes.
{End Note}

{note in Interlisp-Vax, interpreted CAR,CDR of non-list except NIL causes ILLEGAL ARG error.  Compiled, get various unexprected results}


Often, combinations of the {fn CAR} and {fn CDR} functions are used to extract various components of complex list structures.  Functions of the form {lisp C{ellipsis}R} may be used for some of these combinations:{index C...R functions}

{lispcode (CAAR X)  ==>  (CAR (CAR X))}

{lispcode (CADR X)  ==>  (CAR (CDR X))}

{lispcode (CDDDDR X)  ==>  (CDR (CDR (CDR (CDR X))))}

All 30 combinations of nested {fn CAR}s and {fn CDR}s up to 4 deep are included in the system.


{FnDef {FnName RPLACD} {FnArgs X Y}
{Text
Replaces the {fn CDR} of the list cell {arg X} with {arg Y}.  This physically changes the internal structure of {arg X}, as opposed to {fn CONS}, which creates a new list cell.  It is possible to construct a circular list by using {fn RPLACD} to place a pointer to the beginning of a list in a spot at the end of the list.

The value of {fn RPLACD} is {arg X}.  An attempt to {fn RPLACD} {lisp NIL} will cause an error, {lisp ATTEMPT TO RPLAC NIL}{index ATTEMPT TO RPLAC NIL Error} (except for {lisp (RPLACD NIL NIL)}).  An attempt to {fn RPLACD} any other non-list will cause an error, {lisp ARG NOT LIST}.{index ARG NOT LIST Error}
}}


{FnDef {FnName RPLACA} {FnArgs X Y}
{Text
Similar to {fn RPLACD}, but replaces the {fn CAR} of {arg X} with {arg Y}.  The value of {fn RPLACA} is {arg X}.  An attempt to {fn RPLACA} {lisp NIL} will cause an error, {lisp ATTEMPT TO RPLAC NIL},{index ATTEMPT TO RPLAC NIL Error} (except for {lisp (RPLACA NIL NIL)}).  An attempt to {fn RPLACA} any other non-list will cause an error, {lisp ARG NOT LIST}.{index ARG NOT LIST Error}
}}




{FnDef {FnName RPLNODE} {FnArgs X A D}
{Text
Performs {lisp (RPLACA {arg X} {arg A})}, {lisp (RPLACD {arg X} {arg D})}, and returns {arg X}.
}}


{FnDef {FnName RPLNODE2} {FnArgs X Y}
{Text
Performs {lisp (RPLACA {arg X} (CAR {arg Y}))}, {lisp (RPLACD {arg X} (CDR {arg Y}))} and returns {arg X}.
}}




{FnDef {FnName FRPLACD} {FnArgs X Y}}
{FnDef {FnName FRPLACA} {FnArgs X Y}}
{FnDef {FnName FRPLNODE} {FnArgs X A D}}
{FnDef {FnName FRPLNODE2} {FnArgs X Y}
{Text
Faster versions of {fn RPLACD}, etc.

Warning:  In Interlisp-10 and Interlisp-VAX, these functions compile open with no error checks on the type of {arg X}, so a compiled {fn FRPLACD} can produce unpredictable effects.
}}



Usually, single list cells are not manipulated in isolation, but in structures known as "lists".{index *PRIMARY* lists}  By convention, a list is represented by a list cell whose {fn CAR} is the first element of the list, and whose {fn CDR} is the rest of the list (usually another list cell or the "empty list," {lisp NIL}).{index empty list}  List elements may be any Interlisp objects, including other lists.

The input syntax for a list is a sequence of Interlisp data objects (litatoms, numbers, other lists, etc.) enclosed in parentheses or brackets.  Note that {lisp ()}{index () Term} is read as the litatom {atom NIL}.  A right bracket can be used to match all left parenthesis back to the last left bracket, or terminate the lists, e.g. {lisp (A (B (C]}.

If there are two or more elements in a list, the final element can be preceded by a period{index . (in a list)}{index period (in a list) Term} delimited on both sides, indicating that {lisp CDR} of the final list cell in the list is to be the element immediately following the period, e.g. {lisp (A . B)} or {lisp (A B C . D)}, otherwise {lisp CDR} of the last list cell in a list will be {lisp NIL}.  Note that a list does not have to end in {atom NIL}.  It is simply a structure composed of one or more list cells.  The input sequence {lisp (A B C . NIL)} is equivalent to {lisp (A B C)}, and {lisp (A B . (C D))} is equivalent to {lisp (A B C D)}.  Note however that {lisp (A B . C D)} will create a list containing the five litatoms {lisp A}, {lisp B}, {lisp %.}, {lisp C}, and {lisp D}.

Lists are printed by printing a left parenthesis, and then printing the first element of the list, then printing a space, then printing the second element, etc. until the final list cell is reached.  The individual elements of a list are printed by {lisp PRIN1} if the list is being printed by {lisp PRIN1}, and by {lisp PRIN2} if the list is being printed by {lisp PRINT} or {lisp PRIN2}.  Lists are considered to terminate when {lisp CDR} of some node is not a list.  If {lisp CDR} of this terminal node is {atom NIL} (the usual case), {lisp CAR} of the terminal node is printed followed by a right parenthesis. If {lisp CDR} of the terminal node is {it not} {atom NIL}, {lisp CAR} of the terminal node is printed, followed by a space, a period, another space, {lisp CDR} of the terminal node, and then the right parenthesis.  Note that a list input as {lisp (A B C . NIL)} will print as {lisp (A B C)}, and a list input as {lisp (A B . (C D))} will print as {lisp (A B C D)}.  Note also that {lisp PRINTLEVEL} affects the printing of lists ({PageRef Fn PRINTLEVEL}), and that carriage returns may be inserted where dictated by {lisp LINELENGTH} ({PageRef Fn LINELENGTH}).


Note:  One must be careful when testing the equality of list structures.  {fn EQ} will be true only when the two lists are the {it exact} same list.  For example,

{lispcode
← (SETQ A '(1 2))
(1 2)
← (SETQ B A)
(1 2)
← (EQ A B)
T
← (SETQ C '(1 2))
(1 2)
← (EQ A C)
NIL
← (EQUAL A C)
T}

In the example above, the values of {lisp A} and {lisp B} are the exact same list, so they are {fn EQ}.  However, the value of {lisp C} is a totally different list, although it happens to have the same elements.  {fn EQUAL} should be used to compare the elements of two lists.  In general, one should notice whether list manipulation functions use {fn EQ} or {fn EQUAL} for comparing lists.  This is a frequent source of errors.

{note one should also be careful when dealing with destructive operators.}


Interlisp provides an extensive set of list manipulation functions:

{index *BEGIN* list functions}



{Begin SubSec Creating Lists}
{Title Creating Lists}
{Text

{FnDef {FnName MKLIST} {FnArgs X}
{Text
"Make List."  If {arg X} is a list or {lisp NIL}, returns {arg X};  Otherwise, returns {lisp (LIST {arg X})}.
}}


{FnDef {FnName LIST} {FnArgs X{SUB 1} X{SUB 2} {ellipsis} X{SUB N}}
{Type NOSPREAD}
{Text
Returns a list of its arguments, e.g.

{lispcode (LIST 'A 'B '(C D))  =>  (A B (C D))}
}}


{FnDef {FnName APPEND} {FnArgs X{SUB 1} X{SUB 2} {ellipsis} X{SUB N}}
{Type NOSPREAD}
{Text
Copies the top level of the list {arg X{sub 1}} and appends this to a {index copy}copy of the top level of the list {arg X{sub 2}} appended to {ellipsis} appended to {arg X{sub N}}, e.g.,

{lispcode (APPEND '(A B) '(C D E) '(F G))  =>  (A B C D E F G)}

Note that only the first {arg N}-1 lists are copied.  However {arg N}=1 is treated specially; {lisp (APPEND X)} copies the top level of a single list.  To copy a list to all levels, use {fn COPY}.

The following examples illustrate the treatment of non-lists:

{lispcode (APPEND '(A B C) 'D)  =>  (A B C . D)}

{lispcode (APPEND 'A '(B C D))  =>  (B C D)}

{lispcode (APPEND '(A B C . D) '(E F G))  =>  (A B C E F G)}

{lispcode (APPEND '(A B C . D))  =>  (A B C . D)}
}}


{FnDef {FnName NCONC} {FnArgs X{SUB 1} X{SUB 2} {ellipsis} X{SUB N}}
{Type NOSPREAD}
{Text
Returns the same value as {fn APPEND}, but actually modifies the list structure of {arg X{sub 1}} {ellipsis} {arg X{sub n-1}}.  

Note that {fn NCONC} cannot change {lisp NIL} to a list:

{lispcode
←(SETQ FOO NIL)
NIL
←(NCONC FOO '(A B C))
(A B C)
←FOO
NIL}

Although the value of the {fn NCONC} is {lisp (A B C)}, {lisp FOO} has {it not} been changed.  The "problem" is that while it is possible to alter list structure with {fn RPLACA} and {fn RPLACD}, there is no way to change the non-list {lisp NIL} to a list.
}}


{FnDef {FnName NCONC1} {FnArgs LST X}
{Text
{lisp (NCONC {arg LST} (LIST {arg X}))}
}}



{FnDef {FnName ATTACH} {FnArgs X L}
{Text
"Attaches" {arg X} to the front of {arg L} by doing a {fn RPLACA} and {fn RPLACD}.  The value is {lisp EQUAL} to {lisp (CONS {arg X} {arg L})}, but  {fn EQ} to {arg L}, which it physically changes (except if {arg L} is {lisp NIL}).  {lisp (ATTACH X NIL)} is the same as {lisp (CONS X NIL)}.  Otherwise, if {arg L} is not a list, an error is generated, {lisp ARG NOT LIST}.{index ARG NOT LIST Error}
}}


}{End SubSec Creating Lists}



{Begin SubSec Building Lists From Left to Right}
{Title Building Lists From Left to Right}
{Text



{FnDef {FnName TCONC} {FnArgs PTR X}
{Text
{fn TCONC} is similar to {fn NCONC1}; it is useful for building a list by adding elements one at a time at the end.  Unlike {fn NCONC1}, {fn TCONC} does not have to search to the end of the list each time it is called.  Instead, it keeps a pointer to the end of the list being assembled, and updates this pointer after each call.  This can be considerably faster for long lists.  The cost is an extra list cell, {arg PTR}.  {lisp (CAR {arg PTR})} is the list being assembled, {lisp (CDR {arg PTR})} is {lisp (LAST (CAR {arg PTR}))}.  {fn TCONC} returns {arg PTR}, with its {fn CAR} and {fn CDR} appropriately modified.


{arg PTR} can be initialized in two ways.  If {arg PTR} is {lisp NIL}, {fn TCONC} will create and return a {arg PTR}.  In this case, the program must set some variable to the value of the first call to {fn TCONC}.  After that, it is unnecessary to reset the variable, since {fn TCONC} physically changes its value.  Example:

{lispcode
←(SETQ FOO (TCONC NIL 1))
((1) 1)
←(for I from 2 to 5 do (TCONC FOO I))
NIL
←FOO
((1 2 3 4 5) 5)}

If {arg PTR} is initially {lisp (NIL)}, the value of {fn TCONC}
is the same as for {arg PTR}={lisp NIL}. but {fn TCONC} changes
{arg PTR}.  This method allows the program to initialize the {fn TCONC} variable before adding any elements to the list.  Example:

{lispcode
←(SETQ FOO (CONS))
(NIL)
←(for I from 1 to 5 do (TCONC FOO I))
NIL
←FOO
((1 2 3 4 5) 5)}
}}


{FnDef {FnName LCONC} {FnArgs PTR X}
{Text
Where {fn TCONC} is used to add {it elements} at the end of a list, {fn LCONC} is used for building a list by adding {it lists} at the end, i.e., it is similar to {index NCONC FN}{fn NCONC} instead of {fn NCONC1}.{index NCONC1 FN}  Example:

{lispcode
←(SETQ FOO (CONS))
(NIL)
←(LCONC FOO '(1 2))
((1 2) 2)
←(LCONC FOO '(3 4 5))
((1 2 3 4 5) 5)
←(LCONC FOO NIL)
((1 2 3 4 5) 5)}

{fn LCONC} uses the same pointer conventions as {fn TCONC} for eliminating searching to the end of the list, so that the same pointer can be given to {index TCONC FN}{fn TCONC} and {index LCONC FN}{fn LCONC} interchangeably.
Therefore, continuing from above,

{lispcode
←(TCONC FOO NIL)
((1 2 3 4 5 NIL) NIL)
←(TCONC FOO '(3 4 5))
((1 2 3 4 5 NIL (3 4 5)) (3 4 5))}
}}


The functions {fn DOCOLLECT} and {fn ENDCOLLECT} also permit building up lists from left-to-right like {fn TCONC}, but without the overhead of an extra list cell.  The list being maintained is kept as a circular list.  {fn DOCOLLECT} adds items; {fn ENDCOLLECT} replaces the tail with its second argument, and returns the full list.


{FnDef {FnName DOCOLLECT} {FnArgs ITEM LST}
{Text
"Adds" {arg ITEM} to the end of {arg LST}.  Returns the new circular list.  Note that {arg LST} is modified, but it is not {fn EQ} to the new list.  The new list should be stored and used as {arg LST} to the next call to {fn DOCOLLECT}.
}}


{FnDef {FnName ENDCOLLECT} {FnArgs LST TAIL}
{Text
Takes {arg LST}, a list returned by {fn DOCOLLECT}, and returns it as a non-circular list, adding {arg TAIL} as the terminating {fn CDR}.
}}


Here is an example using {fn DOCOLLECT} and {fn ENDCOLLECT}.  {fn HPRINT} is used to print the results because they are circular lists.  Notice that {lisp FOO} has to be set to the value of {fn DOCOLLECT} as each element is added.

{lispcode
←(SETQ FOO NIL]
NIL
←(HPRINT (SETQ FOO (DOCOLLECT 1 FOO]
↑(1 . {bracket 1})
←(HPRINT (SETQ FOO (DOCOLLECT 2 FOO]
↑(2 1 . {bracket 1})
←(HPRINT (SETQ FOO (DOCOLLECT 3 FOO]
↑(3 1 2 . {bracket 1})
←(HPRINT (SETQ FOO (DOCOLLECT 4 FOO]
↑(4 1 2 3 . {bracket 1})
←(SETQ FOO (ENDCOLLECT FOO 5]
(1 2 3 4 . 5)}

{note import common lisp fns?? --lmm}


}{End SubSec Building Lists From Left to Right}




{Begin SubSec Copying Lists}
{Title Copying Lists}
{Text

{FnDef {FnName COPY} {FnArgs X}
{Text
Creates and returns a copy of the list {arg X}.  All levels of {arg X} are copied down to non-lists, so that if {arg X} contains arrays and strings, the {index *PRIMARY* copy}copy of {arg X} will contain the same arrays and strings, not copies.  {fn COPY} is recursive in the {fn CAR} direction only, so very long lists can be copied.

Note: To copy just the {it top level} of {arg X}, do {lisp (APPEND {arg X})}.
}}


{FnDef {FnName COPYALL} {FnArgs X}
{Text
Like {fn COPY} except copies down to atoms.  Arrays, hash-arrays, strings, user data types, etc., are all copied.  Analagous to {fn EQUALALL} ({PageRef Fn EQUALALL}).  Note that this will not work if given a data structure with circular pointers; in this case, use {fn HCOPYALL}.

{note document?:  The variable DONTCOPYDATATYPES (initially NIL) is used as a list of data-type names which should NOT be copied by COPYALL.}
}}


{FnDef {FnName HCOPYALL} {FnArgs X}
{Text
Similar to {fn COPYALL}, except that it will work even if the data structure contains circular pointers.
}}


}{End SubSec Copying Lists}



{Begin SubSec Extracting Tails of Lists}
{Title Extracting Tails of Lists}
{Text


{FnDef {FnName TAILP} {FnArgs X Y}
{Text
Returns {arg X}, if {arg X} is a {it tail}{index tail of a list} of the list {arg Y}; otherwise {lisp NIL}.  {arg X} is a tail of {arg Y} if it is {lisp EQ} to 0 or more {fn CDR}s of {arg Y}.

Note:  If {arg X} is {lisp EQ} to 1 or more {fn CDR}s of {arg Y}, {arg X} is called a "proper tail."{index proper tail}
}}



{FnDef {FnName NTH} {FnArgs X N}
{Text
Returns the tail of {arg X} beginning with the {arg N}th element.  Returns {lisp NIL} if {arg X} has fewer than {arg N} elements.  Examples:

{lispcode (NTH '(A B C D) 1)  =>  (A B C D)}

{lispcode (NTH '(A B C D) 3)  =>  (C D)}

{lispcode (NTH '(A B C D) 9)  =>  NIL}

{lispcode (NTH '(A . B) 2)  =>  B}

For consistency, if {arg N}=0, {fn NTH} returns {lisp (CONS NIL {arg X})}:

{lispcode (NTH '(A B) 0)  =>  (NIL A B)}


{Note What happens if X is not a list? --> returns NIL.  doc?}
}}


{FnDef {FnName FNTH} {FnArgs X N}
{Text
Faster version of {fn NTH} that terminates on a null-check.{index null-check}

(Interlisp-10)  Interpreted, generates an error, {lisp BAD ARGUMENT - FNTH}, if {arg X} ends in other than {lisp NIL}.{index *PRIMARY* BAD ARGUMENT - FNTH Error}
}}



{FnDef {FnName LAST} {FnArgs X}
{Text
Returns the last list cell in the list {arg X}.  Returns {lisp NIL} if {arg X} is not a list.  Examples:

{lispcode (LAST '(A B C))  =>  (C)}

{lispcode (LAST '(A B . C))  =>  (B . C)}

{lispcode (LAST 'A)  =>  NIL}
}}


{FnDef {FnName FLAST} {FnArgs X}
{Text
Faster version of {fn LAST} that terminates on a null-check.{index null-check}

(Interlisp-10)  Interpreted, generates an error, {lisp BAD ARGUMENT - FLAST},{index BAD ARGUMENT - FLAST Error} if {arg X} ends in other than {lisp NIL}.
}}


{FnDef {FnName NLEFT} {FnArgs L N TAIL}
{Text
{fn NLEFT} returns the tail of {arg L} that contains {arg N} more elements than {arg TAIL}.  If {arg L} does not contain {arg N} more elements than {arg TAIL}, {fn NLEFT} returns {lisp NIL}.  If {arg TAIL} is {lisp NIL} or not a tail of {arg L}, {fn NLEFT} returns the last {arg N} list cells in {arg L}.  {fn NLEFT} can be used to work backwards through a list.  Example:

{lispcode
←(SETQ FOO '(A B C D E))
(A B C D E)
←(NLEFT FOO 2)
(D E)
←(NLEFT FOO 1 (CDDR FOO))
(B C D E)
←(NLEFT FOO 3 (CDDR FOO))
NIL}
}}


{FnDef {FnName LASTN} {FnArgs L N}
{Text
Returns {lisp (CONS X Y)}, where {lisp Y} is the last {arg N}
elements of {arg L}, and {lisp X} is the initial segment, e.g.,

{lispcode (LASTN '(A B C D E) 2)  =>  ((A B C) D E)}

{lispcode (LASTN '(A B) 2)  =>  (NIL A B)}

Returns {lisp NIL} if {arg L} is not a list containing at least
{arg N} elements.

{note what if L doesn't end with NIL ??}
}}


}{End SubSec Extracting Tails of Lists}



{Begin SubSec Counting List Cells}
{Title Counting List Cells}
{Text




{FnDef {FnName LENGTH} {FnArgs X}
{Text
Returns the length of the list {arg X}, where "length" is defined as the number of {fn CDR}s required to reach a non-list.  Examples:

{lispcode (LENGTH '(A B C))  =>  3}

{lispcode (LENGTH '(A B C . D))  =>  3}

{lispcode (LENGTH 'A)  =>  0}
}}


{FnDef {FnName FLENGTH} {FnArgs X}
{Text
Faster version of {fn LENGTH} that terminates on a null-check.{index null-check}

(Interlisp-10)  Interpreted, generates an error, {lisp BAD ARGUMENT - FLENGTH},{index BAD ARGUMENT - FLENGTH Error} if {arg X} ends in other than {lisp NIL}.
}}


{FnDef {FnName EQLENGTH} {FnArgs X N}
{Text
Equivalent to {lisp (EQUAL (LENGTH {arg X}) {arg N})}, but more efficient, because {fn EQLENGTH} stops as soon as it knows that {arg X} is longer than {arg N}.  Note that {fn EQLENGTH} is safe to use on (possibly) circular lists, since it is "bounded" by {arg N}.
}}



{FnDef {FnName COUNT} {FnArgs X}
{Text
Returns the number of list cells in the list {arg X}.  Thus, {fn COUNT} is like a {fn LENGTH} that goes to all levels.  {fn COUNT} of a non-list is 0.  Examples:

{lispcode (COUNT '(A))  =>  1}

{lispcode (COUNT '(A . B))  =>  1}

{lispcode (COUNT '(A (B) C))  =>  4}

In this last example, the value is 4 because the list {lisp (A {arg X} C)} uses 3 list cells for any object {arg X}, and {lisp (B)} uses another list cell.
}}


{FnDef {FnName COUNTDOWN} {FnArgs X N}
{Text
Counts the number of list cells in {arg X}, decrementing {arg N} for each one.
Stops and returns {arg N} when it finishes counting, or when {arg N} reaches 0.  {fn COUNTDOWN} can be used on circular structures since it is "bounded" by {arg N}.  Examples:

{lispcode (COUNTDOWN '(A) 100)  =>  99}

{lispcode (COUNTDOWN '(A . B) 100)  =>  99}

{lispcode (COUNTDOWN '(A (B) C) 100)  =>  96}

{lispcode (COUNTDOWN '(DOCOLLECT 1 NIL) 100)  =>  0}
}}


{FnDef {FnName EQUALN} {FnArgs X Y DEPTH}
{Text
Similar to {fn EQUAL}, for use with (possibly) circular structures.  Whenever the depth of {fn CAR} recursion plus the depth of {fn CDR} recursion exceeds {arg DEPTH}, {fn EQUALN} does not search further along that chain, and returns the litatom {atom ?}.{index ? Litatom}  If recursion never exceeds {arg DEPTH}, {fn EQUALN} returns {lisp T} if the expressions {arg X} and {arg Y} are {fn EQUAL}; otherwise {lisp NIL}.

{lispcode (EQUALN '(((A)) B) '(((Z)) B) 2)  =>  ?}

{lispcode (EQUALN '(((A)) B) '(((Z)) B) 3)  =>  NIL}

{lispcode (EQUALN '(((A)) B) '(((A)) B) 3)  =>  T}
}}


}{End SubSec Counting List Cells}




{Begin SubSec Logical Operations}
{Title Logical Operations}
{Text

{note change args to (LDIFF LST TAIL ADD) ??}

{FnDef {FnName LDIFF} {FnArgs X Y Z}
{Text
{arg Y} must be a tail of {arg X}, i.e., {lisp EQ} to the result of applying
some number of {fn CDR}s to {arg X}.  {lisp (LDIFF {arg X} {arg Y})} returns a list of all elements in {arg X} up to {arg Y}.

If {arg Z} is not {lisp NIL}, the value of {fn LDIFF} is effectively {lisp (NCONC {arg Z} (LDIFF {arg X} {arg Y}))}, i.e., the list difference is added at the end of {arg Z}.

If {arg Y} is not a tail of {arg X}, {fn LDIFF} generates an error, {lisp LDIFF: NOT A TAIL}.{index LDIFF: NOT A TAIL Error}  {fn LDIFF} terminates on a {index null-check}null-check, so it will go into an infinite loop if {arg X} is a circular list and {arg Y} is not a tail.

Example:

{lispcode
←(SETQ FOO '(A B C D E F))
(A B C D E F)
←(CDDR FOO)
(C D E F)
←(LDIFF FOO (CDDR FOO))
(A B)
←(LDIFF FOO (CDDR FOO) '(1 2))
(1 2 A B)
←(LDIFF FOO '(C D E F))
LDIFF: not a tail
(C D E F)}

Note that the value of {fn LDIFF} is always new list structure unless {arg Y}={lisp NIL}, in which case the value is {arg X} itself.
}}


{note LDIFFERENCE and INTERSECTION and UNION all call MEMBER for comparisons, so they all test top-level list elements, and use EQUAL for tests}

{note LDIFFERENCE, INTERSECTION, UNION should be nospread  ---lmm}


{FnDef {FnName LDIFFERENCE} {FnArgs X Y}
{Text
"List Difference."  Returns a list of those elements in {arg X} that are not members of {arg Y}.
}}


{FnDef {FnName INTERSECTION} {FnArgs X Y}
{Text
Returns a list whose elements are members of both lists {arg X} and {arg Y}.
Note that {lisp (INTERSECTION X X)} gives a list of all members of {lisp X} without any duplications.
}}


{FnDef {FnName UNION} {FnArgs X Y}
{Text
Returns a (new) list consisting of all elements included on either of the two original lists.  It is more efficient to make {arg X} be the shorter list.

The value of {fn UNION} is {arg Y} with all elements of {arg X} not in {arg Y} {lisp CONS}ed on the front of it.  Therefore, if an element appears twice in {arg Y}, it will appear twice in {lisp (UNION {arg X} {arg Y})}.  Since {lisp (UNION '(A) '(A A))} = {lisp (A A)}, while {lisp (UNION '(A A) '(A))} = {lisp (A)}, {fn UNION} is non-commutative.
}}


}{End SubSec Logical Operations}






{Begin SubSec Searching Lists}
{Title Searching Lists}
{Text


{FnDef {FnName MEMB} {FnArgs X Y}
{Text
Determines if {arg X} is a member of the list {arg Y}.  If there is an element of {arg Y} {lisp EQ} to {arg X}, returns the tail of {arg Y} starting with that element.  Otherwise, returns {lisp NIL}.  Examples:

{lispcode (MEMB 'A '(A (W) C D))  =>  (A (W) C D)}

{lispcode (MEMB 'C '(A (W) C D))  =>  (C D)}

{lispcode (MEMB 'W '(A (W) C D))  =>  NIL}

{lispcode (MEMB '(W) '(A (W) C D))  =>  NIL}
}}


{FnDef {FnName FMEMB} {FnArgs X Y}
{Text
Faster version of {fn MEMB} that terminates on a null-check.{index null-check}

(Interlisp-10)  Interpreted, {fn FMEMB} gives an error, {lisp BAD ARGUMENT - FMEMB},{index BAD ARGUMENT - FMEMB Error} if {arg Y} ends in a non-list other than {lisp NIL}.
}}


{FnDef {FnName MEMBER} {FnArgs X Y}
{Text
Identical to {lisp MEMB} except that it uses {lisp EQUAL} instead of {lisp EQ} to check membership of {arg X} in {arg Y}.  Examples:

{lispcode (MEMBER 'C '(A (W) C D))  =>  (C D)}

{lispcode (MEMBER 'W '(A (W) C D))  =>  NIL}

{lispcode (MEMBER '(W) '(A (W) C D))  =>  ((W) C D)}
}}


{FnDef {FnName EQMEMB} {FnArgs X Y}
{Text
Returns {lisp T} if either {arg X} is {lisp EQ} to {arg Y}, or else {arg Y} is a list and {arg X} is an {lisp FMEMB} of {arg Y}.
}}


}{End SubSec Searching Lists}



{Begin SubSec Substitution Functions}
{Title Substitution Functions}
{Text


{note all of the substitution functions could be explained a lot better.  More example!}


{FnDef {FnName SUBST} {FnArgs NEW OLD EXPR}
{Text
Returns the result of substituting {arg NEW} for all occurrences of {arg OLD} in the expression {arg EXPR}.  Substitution occurs whenever {arg OLD} is {fn EQUAL} to {fn CAR} of some subexpression of {arg EXPR}, or when {arg OLD} is atomic and {fn EQ} to a non-{lisp NIL} {fn CDR} of some subexpression of {arg EXPR}.  For example:

{lispcode (SUBST 'A 'B '(C B (X . B)))  =>  (C A (X . A))}

{lispcode (SUBST 'A '(B C) '((B C) D B C))
          =>  (A D B C)  {it not}  (A D . A)}

{fn SUBST} returns a {index copy}copy of {arg EXPR} with the appropriate changes.  Furthermore, if {arg NEW} is a list, it is copied at each substitution.
}}


{FnDef {FnName DSUBST} {FnArgs NEW OLD EXPR}
{Text
Similar to {lisp SUBST}, except it does not copy {arg EXPR}, but changes the list structure {arg EXPR} itself.{index destructive functions}  Like {lisp SUBST}, {fn DSUBST} substitutes with a copy of {arg NEW}.  More efficient than {lisp SUBST}.
}}


{FnDef {FnName LSUBST} {FnArgs NEW OLD EXPR}
{Text
Like {lisp SUBST} except {arg NEW} is substituted as a segment of the list {arg EXPR} rather than as an element.  For instance,

{lispcode (LSUBST '(A B) 'Y '(X Y Z))  =>  (X A B Z)}

Note that if {arg NEW} is not a list, {fn LSUBST} returns a {index copy}copy of
{arg EXPR} with all {arg OLD}'s deleted:

{lispcode (LSUBST NIL 'Y '(X Y Z))  =>  (X Z)}
}}



{FnDef {FnName SUBLIS} {FnArgs ALST EXPR FLG}
{Text
{arg ALST} is a list of pairs:

{lispcode (({arg OLD{sub 1}} . {arg NEW{sub 1}}) ({arg OLD{sub 2}} . {arg NEW{sub 2}}) {ellipsis} ({arg OLD{sub N}} . {arg NEW{sub N}}))}

Each {arg OLD{sub i}} is an atom.  {fn SUBLIS} returns the result of substituting each {arg NEW{sub i}} for the corresponding {arg OLD{sub i}} in {arg EXPR}, e.g.,

{lispcode (SUBLIS '((A . X) (C . Y)) '(A B C D))  =>  (X B Y D)}

If {arg FLG}={lisp NIL}, new structure is created only if needed, so if there are no substitutions, the value is {lisp EQ} to {arg EXPR}.  If {arg FLG}={lisp T}, the value is always a copy of {arg EXPR}.
}}


{FnDef {FnName DSUBLIS} {FnArgs ALST EXPR FLG}
{Text
Similar to {lisp SUBLIS}, except it changes the list structure {arg EXPR} itself instead of copying it.

{note is FLG ever used?   <-- yes! if FLG=T, the substituted structure is copied.}
}}


{FnDef {FnName SUBPAIR} {FnArgs OLD NEW EXPR FLG}
{Text
Similar to {lisp SUBLIS}, except that elements of {arg NEW} are substituted for corresponding atoms of {arg OLD} in {arg EXPR}, e.g.,

{lispcode (SUBPAIR '(A C) '(X Y) '(A B C D))  =>  (X B Y D)}

As with {lisp SUBLIS}, new structure is created only if needed, or if {arg FLG}={lisp T}, e.g., if {arg FLG}={lisp NIL} and there are no substitutions, the value is {fn EQ} to {arg EXPR}.

If {arg OLD} ends in an atom other than {lisp NIL}, the rest of the elements on {arg NEW} are substituted for that atom.
For example, if {arg OLD}={lisp (A B . C)} and {arg NEW}={lisp (U V X Y Z)},
{lisp U} is substituted for {lisp A}, {lisp V} for {lisp B}, and {lisp (X Y Z)} for {lisp C}.  Similarly, if {arg OLD} itself is an atom (other than {lisp NIL}), the entire list {arg NEW} is substituted for it.  Examples:

{lispcode (SUBPAIR '(A B . C) '(W X Y Z) '(C A B B Y))  =>  ((Y Z) W X X Y)}
}}


Note that {fn SUBST}, {fn DSUBST}, and {fn LSUBST} all substitute copies{index copy} of the appropriate expression, whereas {fn SUBLIS}, and {fn DSUBLIS}, and {fn SUBPAIR} substitute the identical structure (unless {arg FLG}={lisp T}).  For example:

{lispcode
← (SETQ FOO '(A B))
(A B)
← (SETQ BAR '(X Y Z))
(X Y Z)
← (DSUBLIS (LIST (CONS 'X FOO)) BAR)
((A B) Y Z)
← (DSUBLIS (LIST (CONS 'Y FOO)) BAR T)
((A B) (A B) Z)
← (EQ (CAR BAR) FOO)
T
← (EQ (CADR BAR) FOO)
NIL}


{note copying of EXPR and copying of substituted expression should be explained more clearly}

}{End SubSec Substitution Functions}




{Begin SubSec Association Lists and Property Lists}
{Title Association Lists and Property Lists}
{Text


{FnDef {FnName ASSOC} {FnArgs KEY ALST}
{Text
{arg ALST} is a list of lists.  {fn ASSOC} returns the first sublist of {arg ALST}
whose {lisp CAR} is {lisp EQ} to {arg KEY}.  If such a list is not found, {fn ASSOC} returns {lisp NIL}.  Example:

{lispcode (ASSOC 'B '((A . 1) (B . 2) (C . 3)))  =>  (B . 2)}
}}


{FnDef {FnName FASSOC} {FnArgs KEY ALST}
{Text
Faster version of {fn ASSOC} that terminates on a null-check.{index null-check}

(Interlisp-10)  Interpreted, {fn FASSOC} gives an error if {arg ALST} ends in a non-list other than {lisp NIL}, {lisp BAD ARGUMENT - FASSOC}.{index BAD ARGUMENT - FASSOC Error}
}}


{FnDef {FnName SASSOC} {FnArgs KEY ALST}
{Text
Same as {fn ASSOC} but uses {fn EQUAL} instead of {fn EQ} when searching for {arg KEY}.

{note there is no analogous PUTSASSOC fn, so you can't easily use lists as keys in assoc lists (unless you code it yourself)}
}}


{FnDef {FnName PUTASSOC} {FnArgs KEY VAL ALST}
{Text
Searches {arg ALST} for a sublist {lisp CAR} of which is {lisp EQ} to {arg KEY}.  If one is found, the {lisp CDR} is replaced (using {lisp RPLACD}) with {arg VAL}.  If no such sublist is found, {lisp (CONS {arg KEY} {arg VAL})} is added at the end of {arg ALST}.  Returns {arg VAL}.  If {arg ALST}
is not a list, generates an error, {lisp ARG NOT LIST}.{index ARG NOT LIST Error}
}}


{Begin Note}
Date: 22 JUN 1982 2058-PDT
From: ROACH
Subject: PUTASSOC

In my prejudiced opinion, PUTASSOC should be able to take NIL for its alst argument and should return the new alst as its value.  I have written a similar function in MACLISP and quite often I build an alist from scratch, i.e. NIL.  So long as PUTASSOC is used for effect, my semantics is upwards compatible with Interlisp's.  It isn't too late to fix this guy. 
----
to do this, would have to change PUTASSOC to return ALST instead of VAL, unless you want ALST=NIL to be a special case (lose, lose)
{End Note}


Note that the argument order for {lisp ASSOC}, {lisp PUTASSOC}, etc. is different from that of {lisp LISTGET}, {lisp LISTPUT}, etc.


{FnDef {FnName LISTGET} {FnArgs LST PROP}
{Text
Similar to {fn GETPROP} ({PageRef Fn GETPROP}) but works on lists using property list format.  Searches {arg LST} two elements at a time, by {fn CDDR}, looking for an element {fn EQ} to {arg PROP}.  If one is found, returns the next element of {arg LST}, otherwise {lisp NIL}.  Returns {lisp NIL} if {arg LST} is not a list.  Example:

{lispcode (LISTGET '(A 1 B 2 C 3) 'B)  =>  2}

{lispcode (LISTGET '(A 1 B 2 C 3) 'W)  =>  NIL}
}}


{FnDef {FnName LISTPUT} {FnArgs LST PROP VAL}
{Text
Similar to {fn PUTPROP}.  Searches {arg LST} two elements at a time, by {fn CDDR}, looking for an element {fn EQ} to {arg PROP}.  If {arg PROP} is found, replaces the next element of {arg LST} with {arg VAL}.  Otherwise, {arg PROP} and {arg VAL} are added to the end of {arg LST}.  If {arg LST} is a list with an odd number of elements, or ends in a non-list other than {lisp NIL}, {arg PROP} and {arg VAL} are added at its beginning.  Returns {arg VAL}.  If {arg LST} is not a list, generates an error, {lisp ARG NOT LIST}.{index ARG NOT LIST Error}
}}


{FnDef {FnName LISTGET1} {FnArgs LST PROP}
{Text
Like {fn LISTGET}, but searches {arg LST} one {fn CDR} at a time, i.e., looks at each element.  Returns the next element after {arg PROP}.  Examples:

{lispcode (LISTGET1 '(A 1 B 2 C 3) 'B)  =>  2}

{lispcode (LISTGET1 '(A 1 B 2 C 3) '1)  =>  B}

{lispcode (LISTGET1 '(A 1 B 2 C 3) 'W)  =>  NIL}

Note:  {fn LISTGET1} used to be called {lisp GET}.{index GET (old name for LISTGET1)}
}}


{FnDef {FnName LISTPUT1} {FnArgs LST PROP VAL}
{Text
Like {fn LISTPUT}, except searches {arg LST} one {fn CDR} at a time.  Returns the modified {arg LST}.  Example:

{lispcode
←(SETQ FOO '(A 1 B 2))
(A 1 B 2)
←(LISTPUT FOO 'B 3)
(A 1 B 3)
←(LISTPUT FOO 'C 4)
(A 1 B 3 C 4)
←(LISTPUT FOO 1 'W)
(A 1 W 3 C 4)
←FOO
(A 1 W 3 C 4)}

Note that if {arg LST} is not a list, no error is generated.  However, since a non-list cannot be changed into a list, {arg LST} is not modified.  In this case, the value of {fn LISTPUT1} should be saved.  Example:

{lispcode
←(SETQ FOO NIL)
NIL
←(LISTPUT FOO 'A 5)
(A 5)
←FOO
NIL}
}}

{note where are LISTGET1 and LISTPUT1 used??  To use them, I would think that you would need to insure that the sets of prop names and prop values are disjoint.  But in that case, why not just use LISTGET and LISTPUT  ??  I guess I am not seeing an important use for them.  Perhaps someone could give me an example where they are useful (??)   ---mjs}


}{End SubSec Association Lists and Property Lists}




{Begin SubSec Other List Functions}
{Title Other List Functions}
{Text


{FnDef {FnName REMOVE} {FnArgs X L}
{Text
Removes all top-level occurrences of {arg X} from list {arg L}, returning a copy of {arg L} with all elements {fn EQUAL} to {arg X} removed.  Example:

{lispcode (REMOVE 'A '(A B C (A) A))  =>  (B C (A))}

{lispcode (REMOVE '(A) '(A B C (A) A))  =>  (A B C A)}
}}


{FnDef {FnName DREMOVE} {FnArgs X L}
{Text
Similar to {lisp REMOVE}, but uses {lisp EQ} instead of {lisp EQUAL}, and actually modifies the list {arg L} when removing {arg X}, and thus does not use any additional storage.  More efficient than {fn REMOVE}.

Note that {fn DREMOVE} cannot {it change} a list to {lisp NIL}:

{lispcode
←(SETQ FOO '(A))
(A)
←(DREMOVE 'A FOO)
NIL
←FOO
(A)}

The {fn DREMOVE} above returns {lisp NIL}, and does not perform any {lisp CONS}es, but the value of {lisp FOO} is {it still} {lisp (A)}, because there is no way to change a list to a non-list.  See {fn NCONC}.

{Note Ouch!  Why this inconsistancy? (EQ instead of EQUAL) ---mjs}
}}




{FnDef {FnName REVERSE} {FnArgs L}
{Text
Reverses (and copies){index copy} the top level of a list, e.g.,

{lispcode (REVERSE '(A B (C D)))  =>  ((C D) B A)}

If {arg L} is not a list, {fn REVERSE} just returns {arg L}.
}}


{FnDef {FnName DREVERSE} {FnArgs L}
{Text
Value is the same as that of {lisp REVERSE}, but {fn DREVERSE} destroys the original list {arg L}{index destructive functions} and thus does not use any additional storage.  More efficient than {lisp REVERSE}.
}}



}{End SubSec Other List Functions}




{index *END* list functions}


}{End SubSec Lists}