{Begin Chapter 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}.
}}
{index *PRIMARY* LISTP Fn}
{FnDef {FnName LISTP} {FnArgs X}
{Text
Returns {arg X} if {arg X} is a {index List cells}list cell, e.g., something created by {fn CONS}; {lisp NIL} otherwise.
{lisp (LISTP NIL)} = {lisp NIL}.
}}
{index *PRIMARY* NLISTP Fn}
{FnDef {FnName NLISTP} {FnArgs X}
{Text
{lisp (NOT (LISTP X))}. Returns {lisp T} if {arg X} is not a list cell, {lisp NIL} otherwise.
{lisp (NLISTP NIL)} = {lisp T}.
}}
{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 returned is controlled by {var CAR/CDRERR} (below).
}}
{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} for other nonlists is controlled by {var CAR/CDRERR} (below).
}}
{VarDef {Name CAR/CDRERR}
{Text
The variable {var CAR/CDRERR} controls the behavior of {fn CAR} and {fn CDR} when they are passed non-lists (other than {lisp NIL}).
If {var CAR/CDRERR}={lisp NIL} (the current default), then {fn CAR} or {fn CDR} of a non-list (other than {lisp NIL}) return the string {lisp "{bracket car of non-list}"} or {lisp "{bracket cdr of non-list}"}. If {var CAR/CDRERR}={lisp T}, then {fn CAR} and {fn CDR} of a non-list (other than {lisp NIL}) causes an error.
If {var CAR/CDRERR}={lisp ONCE}, then {fn CAR} or {fn CDR} of a string causes an error, but {fn CAR} or {fn CDR} of anything else returns the string {lisp "{bracket car of non-list}"} or {lisp "{bracket cdr of non-list}"} as above. This catches loops which repeatedly take {fn CAR} or {fn CDR} of an object, but it allows one-time errors to pass undetected.
If {var CAR/CDRERR}={lisp CDR}, then {fn CAR} of a non-list returns {lisp "{bracket car of non-list}"} as above, but {fn CDR} of a non-list causes an error. This setting is based on the observation that nearly all infinite loops involving non-lists occur from taking {fn CDR}s, but a fair amount of careless code takes {fn CAR} of something it has not tested to be a list
{Begin Note}
From Harmony release notes:
According to the Interlisp Reference Manual, the value of applying the functions CAR and CDR to a non-list (other than NIL) is undefined. In Interlisp-D, the actual action depended on the data type: (CAR <atom>) returned NIL, (CDR <atom>) returned the atom's property list...
This has turned out to be a bad design. This design typically caused obscure bugs in programs which CDR down a list, and stop on NIL. If the tail of the list is not NIL, then the program loops endlessly, taking CDR of "{bracket cdr of non-list}". This problem also occurs with functions like (FMEMB A B), which loop endlessly if B is not a list.
Because of these problems, the Interlisp maintainers decided that CAR and CDR should cause an error on non-lists. Places in the system code which used the old conventions have been cleaned up. In future releases, the default will be changed so that CAR or CDR of non-NIL non-lists will cause errors. This will also effect system functions, such as FMEMB, which use CAR and CDR. User programs which depend on the old conventions will have to be modified.
{End Note}
}}
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}
{index CAAR Fn}
{index CADR Fn}
{index CDAR Fn}
{index CDDR Fn}
{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.
{Begin Comment Interlisp-10 specific}
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.
{End Comment Interlisp-10 specific}
}}
{index *PRIMARY* Empty list Term}
{index *PRIMARY* () Term}
{index Lists}
Usually, single list cells are not manipulated in isolation, but in structures known as "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}). 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 ()} 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]}.
{index *PRIMARY* . (in a list)}
{index *PRIMARY* Period in a list}
If there are two or more elements in a list, the final element can be preceded by a period 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 {lisp 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.{index EQUAL Fn} 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, described in the following sections.
{index 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 LIST*} {FnArgs X{SUB 1} X{SUB 2} {ellipsis} X{SUB N}}
{Type NOSPREAD}
{Text
Returns a list of its arguments, using the last argument for the tail of the list. This is like an iterated {fn CONS}: {lisp (LIST* A B C)} == {lisp (CONS A (CONS B C))}. For example,
{lispcode (LIST* 'A 'B 'C) => (A B . C)}
{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 Copying lists}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}
The following two functions are useful writing programs that wish to reuse a scratch list to collect together some result (Both of these compile open):
{FnDef {FnName SCRATCHLIST} {FnArgs LST X{SUB 1} X{SUB 2} {ellipsis} X{SUB N}}
{Type NLAMBDA NOSPREAD}
{Text
{fn SCRATCHLIST} sets up a context in which the value of {arg LST} is used as a "scratch" list. The expressions {arg X{sub 1}}, {arg X{sub 2}}, {ellipsis} {arg X{sub N}} are evaluated in turn. During the course of evaluation, any value passed to {fn ADDTOSCRATCHLIST} will be saved, reusing {fn CONS} cells from the value of {arg LST}. If the value of {arg LST} is not long enough, new {fn CONS} cells will be added onto its end. If the value of {arg LST} is {lisp NIL}, the entire value of {fn SCRATCHLIST} will be "new" (i.e. no {fn CONS} cells will be reused).
}}
{FnDef {FnName ADDTOSCRATCHLIST} {FnArgs VALUE}
{Text
For use under calls to {fn SCRATCHLIST}. {arg VALUE} is added on to the end of the value being collected by {fn SCRATCHLIST}. When {fn SCRATCHLIST} returns, its value is a list containing all of the things that {fn ADDTOSCRATCHLIST} has added.
}}
}{End SubSec Building Lists From Left to Right}
{Begin SubSec Copying Lists}
{Title Copying Lists}
{Text
{index *PRIMARY* Copying lists}
{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 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 *PRIMARY* 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 *PRIMARY* 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.
{Begin Comment Interlisp-10 specific}
(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}
{End Comment Interlisp-10 specific}
}}
{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.
{Begin Comment Interlisp-10 Specific}
(Interlisp-10) Interpreted, generates an error, {lisp BAD ARGUMENT - FLAST},{index BAD ARGUMENT - FLAST Error} if {arg X} ends in other than {lisp NIL}.
{End Comment Interlisp-10 Specific}
}}
{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.
{Begin Comment Interlisp-10 Specific}
(Interlisp-10) Interpreted, generates an error, {lisp BAD ARGUMENT - FLENGTH},{index BAD ARGUMENT - FLENGTH Error} if {arg X} ends in other than {lisp NIL}.
{End Comment Interlisp-10 Specific}
}}
{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 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} (using {fn EQUAL} to compare elements).
Note: If {arg X} and {arg Y} share no elements, {fn LDIFFERENCE} returns a copy of {arg X}.
}}
{FnDef {FnName INTERSECTION} {FnArgs X Y}
{Text
Returns a list whose elements are members of both lists {arg X} and {arg Y} (using {fn EQUAL} to compare elements).
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 (using {fn EQUAL} to compare elements). 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.
}}
{FnDef {FnName LDIFF} {FnArgs LST TAIL ADD}
{Text
{arg TAIL} must be a tail of {arg LST}, i.e., {lisp EQ} to the result of applying some number of {fn CDR}s to {arg LST}. {lisp (LDIFF {arg LST} {arg TAIL})} returns a list of all elements in {arg LST} up to {arg TAIL}.
If {arg ADD} is not {lisp NIL}, the value of {fn LDIFF} is effectively {lisp (NCONC {arg ADD} (LDIFF {arg LST} {arg TAIL}))}, i.e., the list difference is added at the end of {arg ADD}.
If {arg TAIL} is not a tail of {arg LST}, {fn LDIFF} generates an error, {lisp LDIFF: NOT A TAIL}.{index LDIFF: NOT A TAIL Error} {fn LDIFF} terminates on a null-check, so it will go into an infinite loop if {arg LST} is a circular list and {arg TAIL} 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 TAIL}={lisp NIL}, in which case the value is {arg LST} itself.
}}
}{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.
{Begin Comment Interlisp-10 Specific}
(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}.
{End Comment Interlisp-10 Specific}
}}
{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 Copying lists}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 Copying lists}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 Copying lists} 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
{index *PRIMARY* Association lists}
{index *PRIMARY* Property lists}
{index *PRIMARY* Property names}
{index *PRIMARY* Property values}
A commonly-used data structure is one that associates an arbitrary set of property names ({arg NAME1}, {arg NAME2}, etc.), with a set of property values ({arg VALUE1}, {arg VALUE2}, etc.). Two list structures commonly used to store such associations are called "property lists" and "association lists." A list in "association list" format is a list where each element is a dotted pair whose {fn CAR} is a property name, and whose {fn CDR} is the value:
{lispcode
( ({arg NAME1} . {arg VALUE1}) ({arg NAME2} . {arg VALUE2}) {ellipsis})}
A list in "property list" format is a list where the first, third, etc. elements are the property names, and the second, forth, etc. elements are the associated values:
{lispcode
( {arg NAME1} {arg VALUE1} {arg NAME2} {arg VALUE2} {ellipsis})}
The functions below provide facilities for searching and changing lists in property list or association list format.
Note: Property lists are contained within many Interlisp-D system datatypes. There are special functions that can be used to set and retrieve values from the property lists of litatoms (see {PageRef Term Properties of litatoms}), from properties of windows (see {PageRef Term Window Properties}), etc.
Note: Another data structure that offers some of the advantages of association lists and property lists is the hash array data type (see {PageRef Term hash arrays}).
{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.
{Begin comment Interlisp-10 specific}
(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}
{End comment Interlisp-10 specific}
}}
{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, {index ARG NOT LIST Error}{lisp ARG NOT LIST}.
}}
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
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
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, {index ARG NOT LIST Error}{lisp ARG NOT LIST}.
}}
{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)
←(LISTPUT1 FOO 'B 3)
(A 1 B 3)
←(LISTPUT1 FOO 'C 4)
(A 1 B 3 C 4)
←(LISTPUT1 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
←(LISTPUT1 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 Sorting Lists}
{Title Sorting Lists}
{Text
{note {fn SORT} was written by L. P. Deutsch.}
{FnDef {FnName SORT} {FnArgs DATA COMPAREFN}
{Text
{arg DATA} is a list of items to be sorted using {arg COMPAREFN}, a predicate function of two arguments which can compare any two items on {arg DATA} and return {lisp T}{Note T or non-NIL?} if the first one belongs before the second. If {arg COMPAREFN} is {lisp NIL}, {fn ALPHORDER} is used; thus {lisp (SORT {arg DATA})} will alphabetize a list. If {arg COMPAREFN} is {lisp T}, {fn CAR}'s of items that are lists are given to {fn ALPHORDER}, otherwise the items themselves; thus {lisp (SORT A-LIST T)} will alphabetize an assoc list by the {fn CAR} of each item. {lisp (SORT X 'ILESSP)} will sort a list of integers.
The value of {fn SORT} is the sorted list. The sort is destructive and uses no extra storage. The value returned is {fn EQ} to {arg DATA} but elements have been switched around. Interrupting with control D, E, or B may cause loss of data, but control H may be used
at any time, and {fn SORT} will break at a clean state from which ↑ or control characters are safe. The algorithm used by {fn SORT} is such that the maximum number of compares is {arg N}*log{sub 2}{arg N}, where {arg N} is {lisp (LENGTH {arg DATA})}.
Note: if {lisp ({arg COMPAREFN} A B)} = {lisp ({arg COMPAREFN} B A)}, then the ordering of {lisp A} and {lisp B} may or may not be preserved.
For example, if {lisp (FOO . FIE)} appears before {lisp (FOO . FUM)} in {lisp X}, {lisp (SORT X T)} may or may not reverse the order of these two elements. Of course, the user can always specify a more precise {arg COMPAREFN}.
}}
{FnDef {FnName MERGE} {FnArgs A B COMPAREFN}
{Text
{arg A} and {arg B} are lists which have previously been sorted using
{fn SORT} and {arg COMPAREFN}.
Value is a destructive merging of the two lists.
It does not matter which list is longer. After merging both {arg A} and {arg B} are equal to the merged list.
(In fact, {lisp (CDR {arg A})} is {fn EQ} to {lisp (CDR {arg B})}).
{fn MERGE} may be aborted after control-H.
}}
{FnDef {FnName ALPHORDER} {FnArgs A B CASEARRAY}
{Text
A predicate function of two arguments, for alphabetizing. Returns a non-{lisp NIL} value if its arguments are in lexicographic order, i.e., if {arg B} does not belong before {arg A}. Numbers come before literal atoms, and are ordered by magnitude (using {fn GREATERP}). Literal atoms and strings are ordered by comparing the character codes in their print names. Thus {lisp (ALPHORDER 23 123)} is {lisp T}, whereas {lisp (ALPHORDER 'A23 'A123)} is {lisp NIL}, because the character code for the digit 2 is greater than the code for 1.
Atoms and strings are ordered before all other data types. If neither {arg A} nor {arg B} are atoms or strings, the value of {fn ALPHORDER} is {lisp T}, i.e., in order.
If {arg CASEARRAY} is non-{lisp NIL}, it is a casearray ({PageRef Fn CASEARRAY} that the characters of {arg A} and {arg B} are translated through before being compared. Note that numbers are not passed through {arg CASEARRAY}.
Note: If either {arg A} or {arg B} is a number, the value returned in the "true" case is {lisp T}. Otherwise, {fn ALPHORDER} returns either {lisp EQUAL} or {lisp LESSP} to discriminate the cases of {arg A} and {arg B} being equal or unequal strings/atoms.
{note ALPHORDER should be changed to return LESSP and EQUAL for numbers, too --mjs}
Note: {fn ALPHORDER} does no {fn UNPACK}s, {fn CHCON}s, {fn CONS}es or {fn NTHCHAR}s. It is several times faster for alphabetizing than anything that can be written using these other functions.
}}
{FnDef {Name UALPHORDER} {Args A B}
{Text
Defined as {lisp (ALPHORDER {arg A} {arg B} UPPERCASEARRAY)}. {var UPPERCASEARRAY} ({PageRef Var UPPERCASEARRAY}) is a casearray that maps every lowercase character into the corresponding uppercase character.
}}
{FnDef {FnName MERGEINSERT} {FnArgs NEW LST ONEFLG}
{Text
{arg LST} is {lisp NIL} or a list of partially sorted items.
{fn MERGEINSERT} tries to find the "best" place to
(destructively) insert {arg NEW}, e.g.,
{lispcode
(MERGEINSERT 'FIE2 '(FOO FOO1 FIE FUM))
=> (FOO FOO1 FIE FIE2 FUM)}
Returns {arg LST}. {fn MERGEINSERT} is undoable.
If {arg ONEFLG}={lisp T} and {arg NEW} is already a member of {arg LST}, {fn MERGEINSERT} does nothing and returns {arg LST}.
}}
{fn MERGEINSERT} is used by {fn ADDTOFILE} ({PageRef Fn ADDTOFILE}) to insert the name of a new function into a list of functions. The algorithm is essentially to look for the item with the longest common leading sequence of characters with respect to {arg NEW}, and then merge {arg NEW} in starting at that point.
}{End SubSec Sorting 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 Copying lists} 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}.
}}
{FnDef {FnName COMPARELISTS} {FnArgs X Y}
{Text
{index *PRIMARY* Comparing lists}Compares the list structures {arg X} and {arg Y} and prints a description of any differences to the terminal. If {arg X} and {arg Y} are {fn EQUAL} lists, {fn COMPARELISTS} simply prints out {lisp SAME}. Returns {lisp NIL}.
{fn COMPARELISTS} prints a terse description of the differences between the two list structures, highlighting the items that have changed. This printout is not a complete and perfect comparison. If {arg X} and {arg Y} are radically different list structures, the printout will not be very useful. {fn COMPARELISTS} is meant to be used as a tool to help users isolate differences between similar structures.
When a single element has been changed for another, {fn COMPARELISTS} prints out items such as {lisp ({arg A} -> {arg B})}, for example:
{lispcode
←(COMPARELISTS '(A B C D) '(X B E D))
(A -> X) (C -> E)
NIL}
When there are more complex differences between the two lists, {fn COMPARELISTS} prints {arg X} and {arg Y}, highlighting differences and abbreviating similar elements as much as possible. "{lisp &}" is used to signal a single element that is present in the same place in the two lists; "{lisp --}" signals an arbitrary number of elements in one list but not in the other; "{lisp -2-}," "{lisp -3-}," etc signal a sequence of two, three, etc. elements that are the same in both lists. Examples:
{lispcode
(COMPARELISTS '(A B C D) '(A D))
(A B C --)
(A D)}
{lispcode
←(COMPARELISTS '(A B C D E F G H) '(A B C D X))
(A -3- E F --)
(A -3- X)}
{lispcode
←(COMPARELISTS '(A B C (D E F (G) H) I) '(A B (G) C (D E F H) I))
(A & & (D -2- (G) &) &)
(A & (G) & (D -2- &) &)}
}}
{FnDef {FnName NEGATE} {FnArgs X}
{Text
For a form {arg X}, returns a form which computes the negation of {arg X} . For example:
{lispcode (NEGATE '(MEMBER X Y)) => (NOT (MEMBER X Y))}
{lispcode (NEGATE '(EQ X Y)) => (NEQ X Y)}
{lispcode (NEGATE '(AND X (NLISTP X))) => (OR (NULL X) (LISTP X))}
{lispcode (NEGATE NIL) => T}
}}
}{End SubSec Other List Functions}
}{End Chapter Lists}