4. Manipulating List Structure
4.1 Conses
car x
Returns the
car of
x.
Example:
(car '(a b c)) => a
cdr x
Returns the
cdr of
x.
Example:
(cdr '(a b c)) => (b c)
Officially car and cdr are only applicable to conses and locatives.
However, as a matter of convenience, a degree of control is provided
over the action taken when there is an attempt to apply one of them to
a symbol or a number. There are four mode-switches known as the
car-number mode, cdr-number mode, car-symbol mode, and
cdr-symbol mode. Here are the meanings of the values of these
mode switches:
.table 1 0 1200
.item car-number = 0
car of a number is an error. This is the default.
.item car-number = 1
car of a number is nil.
.item cdr-number = 0
cdr of a number is an error. This is the default.
.item cdr-number = 1
cdr of a number is nil.
.item car-symbol = 0
car of a symbol is an error.
.item car-symbol = 1
car of nil is nil, but the car of any other
symbol is an error. This is the default.
.item car-symbol = 2
car of any symbol is nil.
.item car-symbol = 3
car of a symbol is its print-name.
.item cdr-symbol = 0
cdr of a symbol is an error.
.item cdr-symbol = 1
cdr of nil is nil, but the cdr of any other
symbol is an error. This is the default.
.item cdr-symbol = 2
cdr of any symbol is nil.
.item cdr-symbol = 3
cdr of nil is nil, cdr of
any other symbol is its property list.
.end_table
The values of the mode switches can be altered with the function set-error-mode
(see (set-error-mode-fun)).
'findex "set-error-mode"
They are stored as byte fields in the special variable %m-flags.
'vindex "%m-flags"
The reason that the two symbol modes default in that fashion is
to allow programs to car and cdr off the ends of lists without
having to check, which is sometimes useful. A few system functions depend
on car and cdr of nil being nil, although they
hadn't ought to, so things may break if you change these modes.
The value of 3 for the symbol modes
exists for compatibility with ancient versions of Maclisp, and should not be used for
any other reasons. (The appropriate functions are get-pname
(see (get-pname-fun)) and plist (see (plist-fun)).)
'findex "get-pname"
'findex "plist"
Note: unlike Maclisp, the values of the symbols car and cdr are not
used; the various mode switches above serve their purpose.
'vindex "car"
'vindex "cdr"
Also unlike Maclisp, this error checking is always done, even in compiled code,
regardless of the value of *rset.
'vindex "*rset"
c...r x
.findex caaaar
.findex caaadr
.findex caaar
.findex caadar
.findex caaddr
.findex caadr
.findex caar
.findex cadaar
.findex cadadr
.findex cadar
.findex caddar
.findex cadddr
.findex caddr
.findex cadr
.findex cdaaar
.findex cdaadr
.findex cdaar
.findex cdadar
.findex cdaddr
.findex cdadr
.findex cdar
.findex cddaar
.findex cddadr
.findex cddar
.findex cdddar
.findex cddddr
.findex cdddr
.findex cddr
All of the compositions of up to four
car's and
cdr's are defined as
functions in their own right. The names of these functions begin with "
c" and end
with "
r", and in between is a sequence of "
a"'s and "
d"'s corresponding to
the composition performed by the function.
Example:
(cddadr x) is the same as (cdr (cdr (car (cdr x))))
The error checking for these functions is exactly the same as for
car and
cdr
above.
cons x y
cons is the primitive function to create a new
cons, whose
car is
x and whose
cdr is
y.
Examples:
(cons 'a 'b) => (a . b)
(cons 'a (cons 'b (cons 'c nil))) => (a b c)
(cons 'a '(b c d)) => (a b c d)
ncons x
(ncons x) is the same as (cons x nil).
The name of the function is from "nil-cons".
xcons x y
xcons ("exchanged cons") is like
cons except that the order of
the arguments is reversed.
Example:
(xcons 'a 'b) => (b . a)
There are two reasons this exists: one is that you might want the arguments
to
cons evaluated in the other order, and the other is that the compiler
might convert calls to
cons into calls to
xcons for efficiency. In fact,
it doesn't.
cons-in-area x y area-number
This function creates a cons in a specific area. (Areas
are an advanced feature of storage management; if you aren't interested in them,
you can safely skip all this stuff). The first two arguments are the same as the
two arguments to cons, and the third is the number of the area in which
to create the cons.
Example:
(cons-in-area 'a 'b my-area) => (a . b)
ncons-in-area x area-number
(ncons-in-area x area-number) = (cons-in-area x nil area-number)
xcons-in-area x y area-number
(xcons-in-area x y area-number) = (cons-in-area y x area-number)
The backquote reader macro facility is also generally useful
for creating list structure, especially mostly-constant list structure,
or forms constructed by plugging variables into a template.
It is documented in the chapter on Macros, see (macro).
car-location cons
car-location returns a locative pointer to the cell containing
the car of cons.
Note: there is no cdr-location function; it is difficult
because of the cdr-coding scheme.
4.2 Lists
The following section explains some of the basic functions
provided for dealing with lists. There has been some confusion
about the term list ever since the beginnings of the language: for
the purposes of the following descriptions, a list is the symbol
nil, or a cons whose cdr is a list. Note well that although we
consider nil to be a list (the list of zero elements), it is a
symbol and not a cons, and the listp predicate is not true of it
(but perhaps listp will be changed in the future).
last list
last returns the last cons of
list. If
list is
nil,
it returns
nil.
Example:
(setq x '(a b c d))
(last x) => (d)
(rplacd (last x) '(e f))
x => '(a b c d e f)
last could have been defined by:
(defun last (x)
(cond ((atom x) x)
((atom (cdr x)) x)
((last (cdr x))) ))
length list
length returns the length of
list. The length of a list
is the number of top-level conses in it.
Examples:
(length nil) => 0
(length '(a b c d)) => 4
(length '(a (b c) d)) => 3
length could have been defined by:
(defun length (x)
(cond ((atom x) 0)
((1+ (length (cdr x)))) ))
or by:
(defun length (x)
(do ((n 0 (1+ n))
(y x (cdr y)))
((atom y) n) ))
first Macro
second Macro
third Macro
fourth Macro
fifth Macro
sixth Macro
seventh Macro
(first x) ==> (car x)
(second x) ==> (cadr x)
(third x) ==> (caddr x)
(fourth x) ==> (cadddr x)
etc.
rest1 Macro
rest2 Macro
rest3 Macro
rest4 Macro
(rest1 x) ==> (cdr x)
(rest2 x) ==> (cddr x)
(rest3 x) ==> (cdddr x)
(rest4 x) ==> (cddddr x)
nth n list
(nth n list) returns the
n'th element of
list, where
the zeroth element is the
car of the list.
Examples:
(nth 1 '(foo bar gack)) => bar
(nth 3 '(foo bar gack)) => nil
Note: this is not the same as the InterLisp function called
nth,
which is similar to but not exactly the same as the Lisp Machine function
nthcdr.
Also, some people have used macros and functions called
nth of their own in
their Maclisp programs, which may not work the same way; be careful.
nth could have been defined by:
(defun nth (n list)
(do ((i n (1- i))
(l list (cdr l)))
((zerop i) (car l))))
nthcdr n list
(nthcdr n list) cdrs
list n times,
and returns the result.
Examples:
(nthcdr 0 '(a b c)) => (a b c)
(nthcdr 2 '(a b c)) => (c)
In other words, it returns the
n'th
cdr of the list.
This is the similar to InterLisp's function
nth, except that the
InterLisp function is one-based instead of zero-based; see the
InterLisp manual for details.
nthcdr is defined by:
(defun nthcdr (n list)
(do ((i 0 (1+ i))
(list list (cdr list)))
((= i n) list)))
list &rest args
list constructs and returns a list of its arguments.
Example:
(list 3 4 'a (car '(b . c)) (+ 6 -2)) => (3 4 a b 4)
list could have been defined by:
(defun list (&rest args)
(let ((list (make-list default-cons-area (length args))))
(do ((l list (cdr l))
(a args (cdr a)))
((null a) list)
(rplaca l (car a)))))
list* &rest args
list* is like
list except that the last
cons
of the constructed list is "dotted". It must be given at least
two arguments.
Example:
(list* 'a 'b 'c 'd) => (a b c . d)
This is like
(cons 'a (cons 'b (cons 'c 'd)))
list-in-area area-number &rest args
list-in-area is exactly the same as list except that it takes
an extra argument, an area number, and creates the list in that area.
make-list area size
This creates and returns a list containing
size elements, each
of which is
nil.
size should be a fixnum. The list
is allocated in the area specified; if you are not using areas in any special
way, just use the value of the symbol
default-cons-area.
Example:
(make-list default-cons-area 3) => (nil nil nil)
Of course, this function is not usually used when the value of the second argument
is a constant; if you want a list of three
nils, it is easy enough
to type
(nil nil nil).
make-list is used when the number
of elements is to be computed while the program is being run.
make-list and
cons are the two primitive list-creation functions
which all the other functions call. The difference is that
make-list
creates a
cdr-coded list (see
this link).
circular-list &rest args
circular-list constructs a circular list whose elements are
args, repeated
infinitely.
circular-list is the same as
list except that the list itself
is used as the last cdr, instead of
nil.
circular-list is especially useful with
mapcar, as in the expression
(mapcar (function +) foo (circular-list 5))
which adds each element of
foo to 5.
append &rest lists
The arguments to
append are lists. The result is a list which is the
concatenation of the arguments.
The arguments are not changed (cf.
nconc).
Example:
(append '(a b c) '(d e f) nil '(g)) => (a b c d e f g)
Note that
append copies the top-level list structure of each of its
arguments except the last. Thus, to copy
a list but not its elements, use
(append x nil).
The
copylist function is equivalent.
A version of
append which only accepts two arguments could have been defined by:
(defun append2 (x y)
(cond ((null x) y)
((cons (car x) (append2 (cdr x) y)) )))
The generalization to any number of arguments could then be made:
(defun append (&rest args)
(and args (append2 (car args)
(apply (function append) (cdr args)))))
These definitions do not express the full functionality of
append; the
real definition minimizes storage utilization by cdr-coding the list it produces,
using
cdr-next except at the end where a full node is used to link to
the last argument, unless the last argument was
nil in which case
cdr-nil is used.
copylist list &optional area
Returns a list which is equal to list, but not eq.
Only the top level of list-structure is copied, i.e. copylist
copies in the cdr direction but not in the car direction.
The returned list is fully cdr-coded to minimize storage.
If the list is "dotted", that is, (cdr (last list))
is a non-nil atom, this will be true of the returned list also.
You may optionally specify the area in which to create the new copy.
copylist* list &optional area
This is the same as copylist except that the last cons of the
resulting list is never cdr-coded. This makes for increased efficiency
if you nconc something onto the list later.
copyalist list &optional area
copyalist is for copying association lists. The top level of
list structure of list is copied, just as copylist does.
In addition, each element of list which is a cons is replaced
in the copy by a new cons with the same car and cdr.
You may optionally specify the area in which to create the new copy.
reverse list
reverse creates a new list whose elements
are the elements of
list taken in reverse order.
reverse does not modify its argument, unlike
nreverse which is faster
but does modify its argument.
Example:
(reverse '(a b (c d) e)) => (e (c d) b a)
reverse could have been defined by:
(defun reverse (x)
(do ((l x (cdr l)) ; scan down argument,
(r nil ; putting each element
(cons (car l) r))) ; into list, until
((null l) r))) ; no more elements.
nconc &rest lists
nconc takes lists as arguments. It returns a list which is the arguments
concatenated together. The arguments are changed, rather than copied.
(cf.
append, (append-fun))
Example:
(setq x '(a b c))
(setq y '(d e f))
(nconc x y) => (a b c d e f)
x => (a b c d e f)
Note that the value of x is now different, since its last cons has been
rplacd'd to
the value of
y.
If the nconc form is evaluated again, it would yield a piece of "circular" list
structure, whose printed representation would be
(a b c d e f d e f d e f ...), repeating forever.
nconc could have been defined by:
(defun nconc (x y) ;for simplicity, this definition
(cond ((null x) y) ;only works for 2 arguments.
(t (rplacd (last x) y) ;hook y onto x
x))) ;and return the modified x.
nreverse list
nreverse reverses its argument, which should be a list. The argument
is destroyed by
rplacd's all through the list (cf.
reverse).
Example:
(nreverse '(a b c)) => (c b a)
nreverse could have been defined by:
(defun nreverse (x)
(cond ((null x) nil)
((nreverse1 x nil))))
(defun nreverse1 (x y) ;auxiliary function
(cond ((null (cdr x)) (rplacd x y))
((nreverse1 (cdr x) (rplacd x y)))))
;; this last call depends on order of argument evaluation.
Currently,
nreverse does something inefficient with
cdr-coded
lists, however this will be changed. In the meantime
reverse might
be preferable in some cases.
nreconc x y
(nreconc x y) is exactly the same as
(nconc (nreverse x) y) except that it is more
efficient. Both
x and
y should be lists.
nreconc could have been defined by:
(defun nreconc (x y)
(cond ((null x) y)
((nreverse1 x y)) ))
using the same
nreverse1 as above.
push Macro
The form is
(push item place), where
item is an
arbitrary object and
place is a reference to a cell containing
a list. Usually
place is the name of a variable.
item
is consed onto the front of the list.
The form
(push (hairy-function x y z) variable)
replaces the commonly-used construct
(setq variable (cons (hairy-function x y z) variable))
and is intended to be more explicit and esthetic.
In general,
(push item place) expands into
(setf place (cons item place)).
(See (setf-fun) for an explanation of
setf.)
pop Macro
The form is
(pop place). The result is
the
car of the contents of
place, and as a side-effect
the
cdr of the contents is stored back into
place.
Example:
(setq x '(a b c))
(pop x) => a
x => (b c)
In general,
(pop place) expands into
(prog1 (car place) (setf place (cdr place))).
(See (setf-fun) for an explanation of
setf.)
butlast list
This creates and returns a list with the same elements as
list,
excepting the last element.
Examples:
(butlast '(a b c d)) => (a b c)
(butlast '((a b) (c d)) => ((a b))
(butlast '(a)) => nil
(butlast nil) => nil
The name is from the phrase "all elements but the last".
nbutlast list
This is the destructive version of
butlast; it changes the cdr of
the second-to-last cons of the list to nil. If there is no
second-to-last cons (that is, if the list has fewer than two elements)
it returns
nil.
Examples:
(setq foo '(a b c d))
(nbutlast foo) => (a b c)
foo => (a b c)
(nbutlast '(a)) => nil
firstn n list
firstn returns a list of length
n, whose elements are the
first
n elements of
list. If
list is fewer than
n elements long, the remaining elements of the returned list
will be
nil.
Example:
(firstn 2 '(a b c d)) => (a b)
(firstn 0 '(a b c d)) => nil
(firstn 6 '(a b c d)) => (a b c d nil nil)
ldiff list sublist
list should be a list, and
sublist should be a sublist
of
list, i.e. one of the conses that make up
list.
ldiff (meaning List Difference) will return a new list,
whose elements are those elements of
list that appear before
sublist.
Examples:
(setq x '(a b c d e))
(setq y (cdddr x)) => (d e)
(ldiff x y) => (a b c)
but
(ldiff '(a b c d) '(c d)) => (a b c d)
since the sublist was not eq to any part of the list.
4.3 Alteration of List Structure
The functions rplaca and rplacd
are used to make alterations in already-existing
list structure; that is, to change the cars and cdrs of existing conses.
The structure is not copied but is physically altered;
hence caution should be exercised when using these functions, as
strange side-effects can occur if portions of list structure become
shared unbeknownst to the programmer.
The nconc, nreverse, nreconc, and nbutlast functions already
described, and the delq family described later,
have the same property. However, they are normally not
used for this side-effect; rather, the list-structure modification
is purely for efficiency and compatible non-modifying functions
are provided.
rplaca x y
(rplaca x y) changes the car of
x to
y and returns
(the modified)
x.
x should be a cons, but
y may be any Lisp object.
Example:
(setq g '(a b c))
(rplaca (cdr g) 'd) => (d c)
Now g => (a d c)
rplacd x y
(rplacd x y) changes the cdr of
x to
y and returns
(the modified)
x.
x should be a cons, but
y may be any Lisp object.
Example:
(setq x '(a b c))
(rplacd x 'd) => (a . d)
Now x => (a . d)
Note to Maclisp users:
rplacd should not be used to set the property
list of a symbol, although there is a compatibility mode in which it will work.
See
car ((car-fun)). The right way to set a property list is with
setplist (see (setplist-fun)).
'findex "setplist"
subst new old s-exp
(subst new old s-exp) substitutes
new for all occurrences of
old
in
s-exp, and returns the modified copy of
s-exp. The original
s-exp
is unchanged, as
subst recursively copies all of
s-exp replacing
elements
equal to
old as it goes. If
new and
old are
nil,
s-exp is just copied, which is a convenient way to copy arbitrary list
structure.
Example:
(subst 'Tempest 'Hurricane
'(Shakespeare wrote (The Hurricane)))
=> (Shakespeare wrote (The Tempest))
subst could have been defined by:
(defun subst (new old s-exp)
(cond ((equal s-exp old) new) ;if item eq to old, replace.
((atom s-exp) s-exp) ;if no substructure, return arg.
((cons (subst new old (car s-exp)) ;otherwise recurse.
(subst new old (cdr s-exp))))))
Note that this function is not "destructive"; that is, it does not change
the
car or
cdr of any already-existing list structure.
nsubst new old s-exp
nsubst is a destructive version of
subst. The list structure of
s-exp is altered by replacing each occurrence of
old with
new.
nsubst could have been defined as
(defun nsubst (new old s-exp)
(cond ((eq s-exp old) new) ;If item eq to old, replace.
((atom s-exp) s-exp) ;If no substructure, return arg.
(t ;; Otherwise, recurse.
(rplaca s-exp (nsubst new old (car s-exp)))
(rplacd s-exp (nsubst new old (cdr s-exp)))
s-exp)))
sublis alist S-expression
sublis makes substitutions for symbols in an S-expression
(a structure of nested lists).
The first argument to
sublis is an association list (see the next
section). The second argument is the S-expression in which
substitutions are to be made.
sublis looks at all symbols
in the S-expression; if a symbol appears in the association
list occurrences of it are replaced by the object it is associated
with. The argument is not modified; new conses are created where
necessary and only where necessary, so the newly created structure
shares as much of its substructure as possible with the old. For
example, if no substitutions are made, the result is
eq to the old
S-expression.
Example:
(sublis '((x . 100) (z . zprime))
'(plus x (minus g z x p) 4))
=> (plus 100 (minus g zprime 100 p) 4)
nsublis alist S-expression
nsublis is like sublis but changes the original list structure
instead of creating new.
4.4 Cdr-Coding
There is an issue which those who must be concerned with
efficiency will need to think about. In the Lisp Machine there are
actually two kinds of lists; normal lists and cdr-coded lists. Normal
lists take two words for each cons, while cdr-coded lists require
only one word for each cons. The saving is achieved by taking
advantage of the usual structure of lists to avoid storing the redundant cdrs
which link together the conses which make up the list. Ordinarily,
rplacd'ing such a list would be impossible, since there is no explicit
representation of the cdr to be modified. However, in the Lisp machine system
it is merely somewhat expensive; a 2-word ordinary
cons must be allocated and linked into the list by an invisible pointer.
This is slower than an ordinary rplacd,
uses extra space, and slows down future accessing of the list.
One should try to use normal lists for those data structures that will
be subject to rplacding operations, including nconc and
nreverse, and cdr-coded lists for other structures.
The functions cons, xcons, ncons, and their area variants make normal lists.
The functions list, list*, list-in-area, make-list,
and append make cdr-coded lists. The other list-creating functions,
including read,
currently make normal lists, but this should not be relied upon.
Some functions, such as sort, take special care to operate
efficiently on cdr-coded lists (sort treats them as arrays).
nreverse is rather slow on cdr-coded lists, currently, since it
simple-mindedly uses rplacd, however this will be changed.
It is currently not planned that the garbage collector
compact ordinary lists into cdr-coded lists. (append x nil)
is a suitable way to copy a list, converting it into cdr-coded form.
4.5 Tables
Lisp Machine Lisp includes several functions which simplify the maintenance
of tabular data structures of several varieties. The simplest is
a plain list of items, which models (approximately) the concept of a set.
There are functions to add (cons), remove (delete, delq,
del, del-if, del-if-not, remove, remq, rem,
rem-if, rem-if-not),
and search for (member, memq, mem) items in a list.
Set union, intersection, and difference functions are easily written using these.
Association lists are very commonly used. An association list
is a list of conses. The car of each cons is a "key" and the cdr
is a "datum", or a list of associated data. The functions
assoc, assq, ass, memass, and rassoc
may be used to retrieve the data, given the key.
Structured records can be stored as association lists or as
stereotyped cons-structures where each element of the structure has a certain
car-cdr path associated with it. However, these are better implemented
using structure macros (see this link).
Simple list-structure is very convenient, but may not be efficient enough
for large data bases because it takes a long time to search a long list.
Lisp Machine lisp includes a hashing function (sxhash) which
aids in the construction of more efficient, hairier structures.
memq item list
(memq item list) returns
nil if
item is not one of the elements of
list. Otherwise, it returns the portion of
list beginning
with the first occurrence of
item. The comparison is made by
eq.
list is searched on the top level only.
Because
memq returns
nil if it doesn't find anything,
and something non-
nil if it finds something, it is often used as a predicate.
Examples:
(memq 'a '(1 2 3 4)) => nil
(memq 'a '(g (x y) c a d e a f)) => (a d e a f)
Note that the value returned by
memq is
eq to the portion of the list
beginning with
a.
Thus
rplaca on the result of
memq may be used,
if you first check to make sure
memq did not return
nil.
Example:
(*catch 'lose
(rplaca (or (memq x z)
(*throw 'lose nil))
y)
)
memq could have been defined by:
(defun memq (item list)
(cond ((atom list) nil)
((eq item (car list)) list)
((memq item (cdr list))) ))
memq is hand-coded in microcode and therefore especially fast.
member item list
member is like
memq, except
equal is used for the comparison,
instead of
eq.
member could have been defined by:
(defun member (item list)
(cond ((null list) nil)
((equal item (car list)) list)
((member item (cdr list))) ))
mem predicate item list
mem is the same as memq except that it takes an extra argument
which should be a predicate of two arguments, which is used for the
comparison instead of eq. (mem 'eq a b) is the same as
(memq a b). (mem 'equal a b) is the same as (member a b).
mem is usually used with equality predicates other than
eq and equal, such
as =, char-equal or string-equal.
tailp tail list
A tail of a list is anything that can be obtained by taking cdr of it zero
or more times. tailp is used to ask whether tail is a tail of
list. That is, it cdr's down list checking at each step
whether what it has got is eq to tail. If so, the value is t.
delq item list &optional n
(delq item list) returns the
list with all top-level
occurrences of
item removed.
eq is used for the comparison.
The argument
list is actually modified (
rplacd'ed) when instances
of
item are spliced out.
delq should be used for value, not
for effect. That is, use
(setq a (delq 'b a))
rather than
(delq 'b a)
The latter is
not equivalent when the first element
of the value of
a is
b.
(delq item list n) is like
(delq item list) except only the first
n instances of
item are deleted.
n is allowed to be zero.
If
n is greater than the number of occurrences of
item in the
list, all occurrences of
item in the list will be deleted.
Example:
(delq 'a '(b a c (a b) d a e)) => (b c (a b) d e)
delq could have been defined by:
(defun delq (item list &optional (n 7777777)) ;7777777 as infinity.
(cond ((or (atom list) (zerop n)) list)
((eq item (car list))
(delq item (cdr list) (1- n)))
((rplacd list (delq item (cdr list) n)))))
delete item list &optional n
delete is the same as delq except that equal is used for the comparison
instead of eq.
del predicate item list &optional n
del is the same as delq except that it takes an extra argument
which should be a predicate of two arguments, which is used for the
comparison instead of eq. (del 'eq a b) is the same as
(delq a b). (c.f. mem, (mem-fun))
remq item list &optional n
remq is similar to
delq, except that the list is not altered;
rather, a new list is returned.
Examples:
(setq x '(a b c d e f))
(remq 'b x) => (a c d e f)
x => (a b c d e f)
(remq 'b '(a b c b a b) 2) => (a c a b)
remove item list &optional n
remove is the same as remq except that equal is used for the
comparison instead of eq.
rem predicate item list &optional n
rem is the same as remq except that it takes an extra argument
which should be a predicate of two arguments, which is used for the
comparison instead of eq. (rem 'eq a b) is the same as
(remq a b). (c.f. mem (mem-fun))
rem-if predicate list
predicate should be a function of one argument.
rem-if makes a new list by applying predicate to
all of the elements of list and removing the ones for which the predicate
returns non-nil. The function's name
means "remove if this condition is true".
rem-if-not predicate list
predicate should be a function of one argument.
rem-if-not makes a new list by applying predicate to
all of the elements of list and removing the ones for which the predicate
returns nil. The function's name
means "remove if this condition is not true"; i.e. it keeps the elements
for which predicate is true.
del-if predicate list
del-if is just like rem-if except that it modifies list
rather than creating a new list. See rem-if.
del-if-not predicate list
del-if-not is just like rem-if-not except that it modifies list
rather than creating a new list. See rem-if-not.
every list predicate &optional step-function
every returns t if predicate returns
non-nil when applied to every element of list,
or nil if predicate returns nil for some element.
If step-function is present, it replaces cdr
as the function used to get to the next element of the list.
some list predicate &optional step-function
some returns a tail of list such that the car
of the tail is the first element that the predicate returns
non-nil when applied to,
or nil if predicate returns nil for every element.
If step-function is present, it replaces cdr
as the function used to get to the next element of the list.
tailp sublist list
Returns t if sublist is a sublist of list (i.e.
one of the conses that makes up list). Otherwise returns nil.
sxhash S-expression
sxhash computes a hash code of an S-expression, and returns it as
a fixnum, which may be positive or negative. A property of sxhash
is that (equal x y) implies (= (sxhash x) (sxhash y)). The
number returned by sxhash is some possibly large number in the
range allowed by fixnums. It is guaranteed that:
.break
1) sxhash for a symbol will always be positive.
.break
2) sxhash of any particular expression will be constant
in a particular implementation for all time, probably.
.break
3) sxhash of any object of type random will be zero.
.break
4) sxhash of a fixnum will = that fixnum.
Here is an example of how to use sxhash in maintaining
hash tables of S-expressions:
(defun knownp (x) ;look up x in the table
(prog (i bkt)
(setq i (plus 76 (remainder (sxhash x) 77)))
;The remainder should be reasonably randomized between
;-76 and 76, thus table size must be > 175 octal.
(setq bkt (aref table i))
;bkt is thus a list of all those expressions that hash
;into the same number as does x.
(return (memq x bkt))))
To write an "intern" for S-expressions, one could
(defun sintern (x)
(prog (bkt i tem)
(setq bkt (aref table
(setq i (+ 2n-2 (\ (sxhash x) 2n-1)))))
;2n-1 and 2n-2 stand for a power of 2 minus one and
;minus two respectively. This is a good choice to
;randomize the result of the remainder operation.
(return (cond ((setq tem (memq x bkt))
(car tem))
(t (aset (cons x bkt) table i)
x)))))
assq item alist
(assq item alist) looks up item in the association list
(list of conses) alist. The value is the first cons whose car
is eq to x, or nil if there is none such.
Examples:
(assq 'r '((a . b) (c . d) (r . x) (s . y) (r . z)))
=> (r . x)
(assq 'fooo '((foo . bar) (zoo . goo))) => nil
(assq 'b '((a b c) (b c d) (x y z))) => (b c d)
It is okay to
rplacd the result of
assq as long as it is not
nil,
if your intention is to "update" the "table" that was
assq's second argument.
Example:
(setq values '((x . 100) (y . 200) (z . 50)))
(assq 'y values) => (y . 200)
(rplacd (assq 'y values) 201)
(assq 'y values) => (y . 201) now
A typical trick is to say
(cdr (assq x y)).
Assuming the cdr of
nil is guaranteed to be
nil,
this yields
nil if no pair is found (or if a pair is
found whose cdr is
nil.)
assq could have been defined by:
(defun assq (item list)
(cond ((null list) nil)
((eq item (caar list)) (car list))
((assq item (cdr list))) ))
assoc item alist
assoc is like
assq except that the comparison uses
equal instead of
eq.
Example:
(assoc '(a b) '((x . y) ((a b) . 7) ((c . d) .e)))
=> ((a b) . 7)
assoc could have been defined by:
(defun assoc (item list)
(cond ((null list) nil)
((equal item (caar list)) (car list))
((assoc item (cdr list))) ))
ass predicate item alist
ass is the same as assq except that it takes an extra argument
which should be a predicate of two arguments, which is used for the
comparison instead of eq. (ass 'eq a b) is the same as
(assq a b). (c.f. mem (mem-fun))
memass predicate item alist
memass searches alist just like ass, but returns
the portion of the list beginning with the pair containing item,
rather than the pair itself. (car (memass x y z)) =
(ass x y z).
rassoc item alist
rassoc means
reverse assoc. It is like
assoc, but
it tries to find an element of
alist whose
cdr (not car)
is
equal to
item.
rassoc is defined by:
(defun rassoc (item in-list)
(do l in-list (cdr l) (null l)
(and (equal item (cdar l))
(return (car l)))))
sassq item alist fcn
(sassq item alist fcn) is like
(assq item alist) except
that if
item is not found in
alist, instead of returning
nil,
sassq calls the function
fcn with no arguments.
sassq could
have been defined by:
(defun sassq (item alist fcn)
(or (assq item alist)
(apply fcn nil)))
sassq and
sassoc (see below) are of limited use.
These are primarily leftovers from Lisp 1.5.
sassoc item alist fcn
(sassoc item alist fcn) is like
(assoc item alist) except that if
item is not found in
alist, instead of returning
nil,
sassoc calls
the function
fcn with no arguments.
sassoc could have been
defined by:
(defun sassoc (item alist fcn)
(or (assoc item alist)
(apply fcn nil)))
pairlis cars cdrs
pairlis takes two lists and makes an association list which associates
elements of the first list with corresponding elements of the second
list.
Example:
(pairlis '(beef clams kitty) '(roast fried yu-shiang))
=> ((beef . roast) (clams . fried) (kitty . yu-shiang))
find-position-in-list item list
find-position-in-list looks down
list for an element which
is
eq to
item, like
memq. However, it returns the numeric index
in the list at which it found the first occurence of
item, or
nil if it did not find it at all.
Examples:
(find-position-in-list 'a '(a b c)) => 0
(find-position-in-list 'c '(a b c)) => 2
(find-position-in-list 'e '(a b c)) => nil
find-position-in-list-equal item list
find-position-in-list-equal is exactly the same as
find-position-in-list, except that the comparison is done
with equal instead of eq.
4.6 Tables
[The stuff in FD.SYM will get moved here, leaving a pointer behind, and
will be generalized for disembodied property lists and made to clarify
the distinction between a plist and a paired list.]
4.7 Tables
A hash table is a Lisp object that works something like a property list.
Each hash table has a set of entries, each of which associates a
particular key with a particular value. The basic functions
that deal with hash tables can create entries, delete entries, and find
the value that is associated with a given key. Finding the value is
very fast even if there are many entries, because hashing is used; this
is an important advantage of hash tables over property lists.
A given hash table can only associate one value with a given
key; if you try to add a second value it will replace the
first.
Hash tables are created with the function make-hash-table, which
takes various options. New entries are added to hash tables with the
puthash function. To look up a key and find the associated value,
the gethash function is used. To remove an entry, use remhash.
Here is a simple example.
(setq a (make-hash-table))
(puthash 'color 'brown a)
(puthash 'name 'fred a)
(gethash 'color a) => brown
(gethash 'name a) => fred
In this example, the symbols color and name are being used as
keys, and the symbols brown and fred are being used as the
associated values. The hash table has two items in it, one of which
associates from color to brown, and the other of which
associates from name to fred.
Keys do not have to be symbols; they can be any Lisp object. Likewise
values can be any Lisp object. The Lisp function eq is used to
compare keys, rather than equal. This means that keys are really
objects, but it means that it is not reasonable to use numbers other
than fixnums as keys. Hash tables are properly interfaced to the
relocating garbage collector so that garbage collection will have no
perceptible effect on the functionality of hash tables.
When a hash table is first created, it has a size, which is the
maximum number of entries it can hold. Usually the actual capacity of
the table is somewhat less, since the hashing is not perfectly
collision-free. With the maximum possible bad luck, the capacity could
be very much less, but this rarely happens. If so many entries are
added that the capacity is exceeded, the hash table will automatically
grow, and the entries will be rehashed (new hash values will be
recomputed, and everything will be rearranged so that the fast hash
lookup still works). This is transparent to the caller; it all happens
automatically.
If the calling program is using multiprocessing, it must be careful to
make sure that there are never two processes both referencing the hash
table at the same time. There is no locking built into hash tables; if
you have two processes that both want to reference the same hash table,
you must arrange mutual exclusion yourself by using a lock or some other
means. Don't worry about this if you don't use multiprocessing; but if
you do use multiprocessing, you will have a lot of trouble if you don't
understand this.
make-hash-table &rest options
This creates a new hash table. Valid option keywords are:
.table 3
.item :size
Set the initial size of the hash table, in entries, as a fixnum. The
default is 100 (octal). The actual size is rounded up from the size
you specify to the next "good" size.
You won't necessarily be able to store this many entries into the table
before it overflows and becomes bigger; but except in the case of extreme
bad luck you will be able to store almost this many.
.item :area
Specify the area in which the hash table should be created. This is
just like the first argument to make-array (see (make-array-fun)).
Defaults to nil (i.e. default-cons-area).
.item :rehash-function
Specify the function to be used for rehashing when the table becomes
full. Defaults to the internal rehashing function that does the usual
thing. If you want to write your own rehashing function, you will
have to understand all the internals of how hash tables work. These
internals are not documented here, as the best way to learn them is
to read the source code.
.item :rehash-size
Specifies how much to increase the size of the hash table when it becomes
full. This can be a fixnum which is the number of entries to add, or
it can be a flonum which is the ratio of the new size to the old size.
The default is 1.3, which causes the table to be made 30% bigger
each time it has to grow.
.end_table
gethash key hash-table
Find the entry in hash-table whose key is key, and return the
associated value. If there is no such entry, return nil.
Returns a second value, which is t if an entry was found or nil if there
is no entry for key in this table.
puthash key value hash-table
Create an entry associating key to value; if there is already an
entry for key, then replace the value of that entry with value.
Returns value.
remhash key hash-table
Remove any entry for key in hash-table. Returns t if there was an
entry or nil if there was not.
maphash function hash-table
For each entry in hash-table, call function on two arguments:
the key of the entry and the value of the entry.
clrhash hash-table
Remove all the entries from hash-table. Returns the hash table itself.
The describe function (see (describe-fun)) prints a variety of
useful information when applied to a hash table.
This hash table facility is similar to the hasharray facility of Interlisp,
and some of the function names are the same. However, it is not compatible.
The exact details and the order of arguments are designed to be consistent
with the rest of the Lisp machine rather than with Interlisp. For instance,
the order of arguments to maphash is different, we do not have the Interlisp
"system hash table", and we do not have the
Interlisp restriction that keys and values may not be nil.
4.8 Sorting
Several functions are provided for sorting arrays and lists. These
functions use algorithms which always terminate no matter what sorting
predicate is used, provided only that the predicate always terminates.
The array sort is not necessarily stable; that is, equal items may
not stay in their original order. However the list sort is
stable.
After sorting, the argument (be it list or array) is rearranged
internally so as to be completely ordered. In the case of an array
argument, this is accomplished by permuting the elements of the array,
while in the list case, the list is reordered by rplacd's in the
same manner as nreverse. Thus if the argument should not be
clobbered, the user must sort a copy of the argument, obtainable by
fillarray or append, as appropriate.
Should the comparison predicate cause an error, such as a wrong type
argument error, the state of the list or array being sorted is
undefined. However, if the error is corrected the sort will, of
course, proceed correctly.
The sorting package is smart about cdr-coded lists.
sort table predicate
The first argument to
sort is an array or a list. The second
is a predicate, which must be applicable to
all the objects in the array or list. The predicate should take two
arguments, and return non-
nil if and only if the first argument is
strictly less than the second (in some appropriate sense).
The
sort function proceeds to sort the contents of the array or
list under the ordering imposed by the predicate, and returns the
array or list modified into sorted order, i.e. its modified first
argument. Note that since sorting requires many comparisons, and thus
many calls to the predicate, sorting will be much faster if the
predicate is a compiled function rather than interpreted.
Example:
(defun mostcar (x)
(cond ((symbolp x) x)
((mostcar (car x)))))
(sort 'fooarray
(function (lambda (x y)
(alphalessp (mostcar x) (mostcar y)))))
If
fooarray contained these items before the sort:
(Tokens (The lion sleeps tonight))
(Carpenters (Close to you))
((Rolling Stones) (Brown sugar))
((Beach Boys) (I get around))
(Beatles (I want to hold your hand))
then after the sort
fooarray would contain:
((Beach Boys) (I get around))
(Beatles (I want to hold your hand))
(Carpenters (Close to you))
((Rolling Stones) (Brown sugar))
(Tokens (The lion sleeps tonight))
sortcar x predicate
sortcar is exactly like sort, but the items in the array or
list being sorted should all be conses. sortcar takes the
car of each item before handing two items to the predicate. Thus
sortcar is to sort as mapcar is to maplist.
The spelling of the names of the next two functions will be corrected at some point.
sort-grouped-array array group-size predicate
sort-grouped-array considers its array argument to
be composed of records of group-size elements each.
These records are considered as units, and are sorted with respect
to one another. The predicate is applied to the first element
of each record; so the first elements act as the keys on which
the records are sorted.
sort-grouped-array-group-key array group-size predicate
This is like sort-grouped-array except that the
predicate is applied to four arguments: an array,
an index into that array, a second array, and an index into
the second array. predicate should consider each index
as a subscript of the first element of a record in the corresponding
array, and compare the two records. This is more general
than sort-grouped-array since the function can get at
all of the elements of the relevant records, instead of only the first element.
.eof