SECTION 6
LIST MANIPULATION AND CONCATENATION
list[x1;x2;...;xn] lambda-nospread function. Its value is a list
of the values of its arguments.
append[x1;x2;...;xn] Copies the top level of the list x1 and appends
this to a copy of top level list x2 appended to
... appended to xn, e.g.,
append[(A B) (C D E) (F G)] = (A B C D E F G).
Note that only the first n-1 lists are copied.
However n=1 is treated specially; i.e.,
append[x] can be used to copy the top level of a
1
single list.
The following examples illustrate the treatment
of non-lists.
append[(A B C);D] = (A B C . D)
append[A;(B C D)] = (B C D)
append[(A B C . D);(E F G)] = (A B C E F G)
append[(A B C . D)] = (A B C . D).
nconc[x1;x2;...;xn] Returns same value as append but actually
modifies the list structure of x1 ... xn-1.
Note that nconc cannot change NIL to a list. In other words, if the
value of foo is NIL, then the value of (NCONC FOO (QUOTE (A B C))) is
(A B C), but foo will not have been changed. The "problem" is that
nconc simply has a collection of pointers to work with, and does not
know where they originally came from, i.e., does not know that this NIL
is the value of foo, and while it is possible to alter list structure
using rplaca, there is no way to change a non-list to a list.
nconc1[lst;x] Performs nconc[lst;list[x]]. The cons will be
on the same page as lst.
------------------------------------------------------------------------
1
To copy a list to all levels, use copy.
6.1
tconc[ptr;x] tconc is useful for building a list by adding
elements one at a time at the end, i.e., its
role is similar to that of nconc1. However,
unlike nconc1,-1, tconc does not have to search
to the end of the list each time it is called.
It does this by keeping a pointer to the end of
the list being assembled, and updating this
pointer after each call. The savings can be
considerable for long lists. The cost is the
extra word required for storing both the list
being assembled, and the end of the list. ptr
is that word: car[ptr] is the list being
assembled, cdr[ptr] is last [car[ptr]]. The
value of tconc is ptr, with the appropriate
modifications to car and cdr. Example:
_(RPTQ 5 (SETQ FOO (TCONC FOO RPTN)))
((5 4 3 2 1) 1).
tconc can be initialized in two ways. If ptr is
NIL, tconc will make up a ptr. In this case,
the program must set some variable to the value
of the first call to tconc. After that, it is
unnecessary to reset ptr since tconc physically
changes it. Thus:
_(SET FOO (TCONC NIL 1))
((1) 1)
_(RPTQ 4 (TCONC FOO RPTN))
((1 4 3 2 1) 1).
If ptr is initially (NIL), the value of tconc is
the same as for ptr=NIL, but tconc changes ptr,
e.g.,
_(SETQ FOO (CONS))
(NIL)
_(RPTQ 5 (TCONC FOO RPTN))
((5 4 3 2 1) 1).
The latter method allows the program to
initialize, and then call tconc without having
to perform setq on its value.
lconc[ptr;x] Where tconc is used to add elements at the end
of a list, lconc is used for building a list by
adding lists at the end, i.e., it is similar to
nconc instead of nconc1, e.g.,
_(SETQ FOO (CONS))
(NIL)
_(LCONC FOO (LIST 1 2))
((1 2) 2)
_(LCONC FOO (LIST 3 4 5))
((1 2 3 4 5) 5)
_(LCONC FOO NIL)
((1 2 3 4 5) 5)
6.2
Note that
_(TCONC) FOO NIL)
((1 2 3 4 5 NIL) NIL)
_(TCONC FOO (LIST 3 4 5))
((1 2 3 4 5 NIL (3 4 5)) (3 4 5))
lconc uses the same pointer conventions as tconc
for eliminating searching to the end of the
list, so that the same pointer can be given to
tconc and lconc interchangeably.
attach[x;y] Value is equal to cons[x;y], but attaches x to
the front of y by doing an rplaca and rplacd,
i.e., the value of attach is eq to y, which it
physically changes. y must be a list, or an
error is generated, ARG NOT LIST.
remove[x;l] Removes all occurrences of x from list l, giving
a copy of l with all elements equal to x
removed.
Convention: Naming a function by prefixing an existing function with d
frequently indicates the new function is a destructive version of the
old one, i.e., it does not make any new structure but cannibalizes its
argument(s).
dremove[x;l] Similar to remove, but uses eq instead of equal,
and actually modifies the list l when removing
x, and thus does not use any additional storage.
More efficient than remove.
Note that dremove cannot change a list to NIL. For example, if the
value of foo is (A), then (DREMOVE (QUOTE A) FOO) will return NIL, and
not perform any conses, but the value of foo will still be (A) because
there is not way to change a list to a non-list. See discussion
following description of nconc on page 6.2.
copy[x] Makes a copy of the list x. The value of copy
is the copied list. All levels of x are
2
copied, down to non-lists, so that if x
contains arrays and strings, the copy of x will
contain the same arrays and strings, not copies.
Copy is recursive in the car direction only, so
that very long lists can be copied.
------------------------------------------------------------------------
2
To copy just the top level of x, do append[x].
6.3
copyall[x] Like copy except copies down to atoms, i.e.,
arrays, hash-arrays, strings, user data types,
etc., are all copied.
reverse[l] Reverses (and copies) the top level of a list,
e.g., reverse[(A B (C D))] = ((C D) B A). If x
is not a list, value is x.
dreverse[l] Value is same as that of reverse, but dreverse
destroys the original list l and thus does not
use any additional storage. More efficient than
reverse.
subst[x;y;z] Value is the result of substituting the S-
expression x for all occurrences of the S-
expression y in the S-expression z.
Substitution occurs whenever y is equal to car
of some subexpression of z, or when y is both
atomic and not NIL and eq to cdr of some
subexpression of z. For example:
subst[A;B;(C B (X . B))] = (C A (X . A))
subst[A;(B C);((B C) D B C)] = (A D B C),
not (A D . A).
The value of subst is a copy of z with the
appropriate changes. Furthermore, if x is a
list, it is copied at each substitution.
dsubst[x;y;z] Similar to subst, but does not copy z, but
changes the list structure z itself. Like subst,
dsubst substitutes with a copy of x. More
efficient than subst.
lsubst[x;y;z] Like subst except x is substituted as a segment,
e.g., lsubst[(A B);Y;(X Y Z)] is (X A B Z).
Note that if x is NIL, produces a copy of z with
all y's deleted.
esubst[x;y;z;flg] Similar to dsubst, but first checks to see if y
actually appears in z. If not, calls error!
where flg=T means print a message of the form x
? This function is actually an implementation of
the editor's R command (see Section 9), so that
y can use &, --, or alt-modes as with the R
command.
6.4
sublis[alst;expr;flg] alst is a list of pairs:
((u1 . v1) (u2 . v2) ... (un . vn)) with each ui
atomic.
The value of sublis[alst;expr;flg] is the result
of substituting each v for the corresponding u
3
in expr, e.g.,
sublis[((A . X) (C . Y));(A B C D)] = (X B Y D).
New structure is created only if needed, or if
flg=T, e.g., if flg=NIL and there are no
substitutions, value is eq to expr.
subpair[old;new;expr;flg]
Similar to sublis, except that elements of new
are substituted for corresponding atoms of old
in expr, e.g.,
subpair[(A C);(X Y);(A B C D)] = (X B Y D)
As with sublis, new structure is created only if
needed, or if flg=T, e.g., if flg=NIL and there
are no substitutions, the value is eq to expr.
If old ends in an atom other than NIL, the rest
of the elements on new are substituted for that
atom. For example, if old=(A B . C) and
new=(U V X Y Z), U is substituted for A, V for
B, and (X Y Z) for C. Similarly, if old itself
is an atom (other than NIL), the entire list new
is substituted for it.
Note that subst, dsubst, lsubst, and esubst all substitute copies of the
appropriate expression, whereas subpair and sublis substitute the
identical structure (unless flg=T).
last[x] Value is a pointer to the last node in the list
x, e.g., if x=(A B C) then last[x] = (C). If
x=(A B . C) last[x] = (B . C). Value is NIL if
x is not a list.
flast[x] Fast version of last that compiles open as a 5
instruction loop, terminating on a null-check.
Interpreted, generates an error, BAD ARGUMENT -
FLAST, if x ends in other than NIL.
nleft[l;n;tail] Tail is a tail of l or NIL. The value of nleft
is the tail of l that contains n more elements
------------------------------------------------------------------------
3
To remember the order on alst, think of it as old to new, i.e., ui -
> vi.
6.5
4
than tail, e.g., if
x=(A B C D E), nleft[x;2]=(D E),
nleft[x;1;cddr[x]]=(B C D E). Thus nleft can be
used to work backwards through a list. Value is
NIL if l does not contain n more elements than
tail.
lastn[l;n] Value is cons[x;y], where y is the last n
elements of l, and x is the initial segment,
e.g.,
lastn[(A B C D E);2]=((A B C) D E)
lastn[(A B);2]=(NIL A B).
Value is NIL, if l is not a list containing at
least n elements.
nth[x;n] Value is the tail of x beginning with the nt-
1th-1h element, e.g., if n=2, value is cdr[x],
if n=3, cddr[x], etc. If n=1, value is x, if
n=0, for consistency, value is cons[NIL;x]. If
x has fewer than n elements, value is NIL, e.g.,
nth[(A B);3]=NIL, as is nth[(A . B);3] Note that
nth[(A . B);2]=B.
fnth[x;n] Fast version of nth that compiles open as a 3
instruction loop, terminating on a null-check.
Interpreted, generates an error, BAD ARGUMENT -
FNTH, if x ends in other than NIL.
length[x] Value is the length of the list x where length
is defined as the number of cdrs required to
reach a non-list, e.g.,
length[(A B C)] = 3
length[(A B C . D)] = 3
length[A] = 0
flength[x] Fast version of length that compiles open as a 4
instruction loop, terminating on a null-check.
Interpreted, generates an error, BAD ARGUMENT -
FLENGTH, if x ends in other than NIL.
count[x] Value is the number of list words in the
structure x. Thus, count is like a length that
goes to all levels. Count of a non-list is 0.
------------------------------------------------------------------------
4
If tail is not NIL, but not a tail of l, the result is the same as
if tail were NIL, i.e., nleft operates by scanning l looking for
tail, not by computing the lengths of l and tail.
6.6
ldiff[x;y;z] y must be a tail of x, i.e., eq to the result of
applying some number of cdrs to x. ldiff[x;y]
gives a list of all elements in x up to y, i.e.,
the list difference of x and y. Thus
ldiff[x;member[FOO;x]] gives all elements in x
up to the first FOO.
Note that the value of ldiff is always new list structure unless y=NIL,
in which case the value is x itself.
If z is not NIL, the value of ldiff is
effectively nconc[z;ldiff[x;y]], i.e., the list
difference is added at the end of z.
If y is not a tail of x, generates an error,
LDIFF: NOT A TAIL. ldiff terminates on a
null-check.
intersection[x;y] Value is a list whose elements are members of
both lists x and y. Note that intersection[x;x]
gives a list of all members of x without any
duplications.
union[x;y] Value is a (new) list consisting of all elements
included on either of the two original lists.
It is more efficient to make x be the shorter
5
list.
6
sort[data;comparefn] data is a list of items to be sorted using
comparefn, a predicate function of two arguments
which can compare any two items on data and
return T if the first one belongs before the
second. If comparefn is NIL, alphorder is used;
thus sort[data] will alphabetize a list. If
comparefn is T, car's of items are given to
alphorder; thus sort[a-list;T] will alphabetize
by the car of each item. sort[x;ILESSP] will
sort a list of integers.
------------------------------------------------------------------------
5
The value of union is y with all elements of x not in y consed on
the front of it. Therefore, if an element appears twice in y, it
will appear twice in union[x;y]. Also, since
union[(A);(A A)] = (A A), while union[(A A);(A)] = (A), union is
non-commutative.
6
Sort, merge, and alphorder were written by J. W. Goodwin.
6.7
The value of sort is the sorted list. The sort
is destructive and uses no extra storage. The
value returned is eq to 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 sort will break at
a clean state from which ^ or control characters
are safe. The algorithm used by sort is such
that the maximum number of compares is n*log2 n,
where n is length[data].
Note: if comparefn[a;b] = comparefn[b;a], then the ordering of a and b
may or may not be preserved.
For example, if (FOO . FIE) appears before (FOO . FUM) in x, sort[x;T]
may or may not reverse the order of these two elements. Of course, the
user can always specify a more precise comparefn.
merge[a;b;comparefn] a and b are lists which have previously been
sorted using sort and comparefn. Value is a
destructive merging of the two lists. It does
not matter which list is longer. After merging
both a and b are equal to the merged list In
fact, cdr[a] is eq to cdr[b]). merge may be
aborted after control-H.
alphorder[a;b] A predicate function of two arguments, for
alphabetizing. Returns T if its arguments are
in order, i.e., if b does not belong before a.
Numbers come before literal atoms, and are
ordered by magnitude (using greaterp). Literal
atoms and strings are ordered by comparing the
(ASCII) character codes in their pnames. Thus
alphorder[23;123] is T, whereas
alphorder[A23;A123] is 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 a nor b are atoms or
strings, the value of alphorder is T, i.e., in
order.
Note: alphorder does no unpacks, chcons, conses or nthchars. It is
several times faster for alphabetizing than anything that can be written
using these other functions.
mergeinsert[new;lst] lst is NIL or a list of partially sorted items.
mergeinsert tries to find the "best" place to
(destructively) insert new, e.g.,
mergeinsert[FIE2; (FOO FOO1 FIE FUM)]=
(FOO FOO1 FIE FIE2 FUM). Value is lst.
mergeinsert is undoable.
6.8
mergeinsert is used by addtofile (Section 14) 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 new, and then merge new in starting at that point.
cplists[x;y] compares x and y and prints their differences,
i.e., cplists is essentially a SRCCOM for list
structures.
6.9