1 This is Info file ../info/cl.info, produced by Makeinfo version 1.68
2 from the input file cl.texi.
4 INFO-DIR-SECTION XEmacs Editor
6 * Common Lisp: (cl). GNU Emacs Common Lisp emulation package.
9 This file documents the GNU Emacs Common Lisp emulation package.
11 Copyright (C) 1993 Free Software Foundation, Inc.
13 Permission is granted to make and distribute verbatim copies of this
14 manual provided the copyright notice and this permission notice are
15 preserved on all copies.
17 Permission is granted to copy and distribute modified versions of
18 this manual under the conditions for verbatim copying, provided also
19 that the section entitled "GNU General Public License" is included
20 exactly as in the original, and provided that the entire resulting
21 derived work is distributed under the terms of a permission notice
22 identical to this one.
24 Permission is granted to copy and distribute translations of this
25 manual into another language, under the above conditions for modified
26 versions, except that the section entitled "GNU General Public License"
27 may be included in a translation approved by the author instead of in
31 File: cl.info, Node: Implementation Parameters, Prev: Random Numbers, Up: Numbers
33 Implementation Parameters
34 =========================
36 This package defines several useful constants having to with numbers.
38 - Variable: most-positive-fixnum
39 This constant equals the largest value a Lisp integer can hold.
40 It is typically `2^23-1' or `2^25-1'.
42 - Variable: most-negative-fixnum
43 This constant equals the smallest (most negative) value a Lisp
46 The following parameters have to do with floating-point numbers.
47 This package determines their values by exercising the computer's
48 floating-point arithmetic in various ways. Because this operation
49 might be slow, the code for initializing them is kept in a separate
50 function that must be called before the parameters can be used.
52 - Function: cl-float-limits
53 This function makes sure that the Common Lisp floating-point
54 parameters like `most-positive-float' have been initialized.
55 Until it is called, these parameters will be `nil'. If this
56 version of Emacs does not support floats (e.g., most versions of
57 Emacs 18), the parameters will remain `nil'. If the parameters
58 have already been initialized, the function returns immediately.
60 The algorithm makes assumptions that will be valid for most modern
61 machines, but will fail if the machine's arithmetic is extremely
62 unusual, e.g., decimal.
64 Since true Common Lisp supports up to four different floating-point
65 precisions, it has families of constants like
66 `most-positive-single-float', `most-positive-double-float',
67 `most-positive-long-float', and so on. Emacs has only one
68 floating-point precision, so this package omits the precision word from
71 - Variable: most-positive-float
72 This constant equals the largest value a Lisp float can hold. For
73 those systems whose arithmetic supports infinities, this is the
74 largest *finite* value. For IEEE machines, the value is
75 approximately `1.79e+308'.
77 - Variable: most-negative-float
78 This constant equals the most-negative value a Lisp float can hold.
79 (It is assumed to be equal to `(- most-positive-float)'.)
81 - Variable: least-positive-float
82 This constant equals the smallest Lisp float value greater than
83 zero. For IEEE machines, it is about `4.94e-324' if denormals are
84 supported or `2.22e-308' if not.
86 - Variable: least-positive-normalized-float
87 This constant equals the smallest *normalized* Lisp float greater
88 than zero, i.e., the smallest value for which IEEE denormalization
89 will not result in a loss of precision. For IEEE machines, this
90 value is about `2.22e-308'. For machines that do not support the
91 concept of denormalization and gradual underflow, this constant
92 will always equal `least-positive-float'.
94 - Variable: least-negative-float
95 This constant is the negative counterpart of
96 `least-positive-float'.
98 - Variable: least-negative-normalized-float
99 This constant is the negative counterpart of
100 `least-positive-normalized-float'.
102 - Variable: float-epsilon
103 This constant is the smallest positive Lisp float that can be added
104 to 1.0 to produce a distinct value. Adding a smaller number to 1.0
105 will yield 1.0 again due to roundoff. For IEEE machines, epsilon
108 - Variable: float-negative-epsilon
109 This is the smallest positive value that can be subtracted from
110 1.0 to produce a distinct value. For IEEE machines, it is about
114 File: cl.info, Node: Sequences, Next: Lists, Prev: Numbers, Up: Top
119 Common Lisp defines a number of functions that operate on "sequences",
120 which are either lists, strings, or vectors. Emacs Lisp includes a few
121 of these, notably `elt' and `length'; this package defines most of the
126 * Sequence Basics:: Arguments shared by all sequence functions
127 * Mapping over Sequences:: `mapcar*', `mapcan', `map', `every', etc.
128 * Sequence Functions:: `subseq', `remove*', `substitute', etc.
129 * Searching Sequences:: `find', `position', `count', `search', etc.
130 * Sorting Sequences:: `sort*', `stable-sort', `merge'
133 File: cl.info, Node: Sequence Basics, Next: Mapping over Sequences, Prev: Sequences, Up: Sequences
138 Many of the sequence functions take keyword arguments; *note Argument
139 Lists::.. All keyword arguments are optional and, if specified, may
142 The `:key' argument should be passed either `nil', or a function of
143 one argument. This key function is used as a filter through which the
144 elements of the sequence are seen; for example, `(find x y :key 'car)'
145 is similar to `(assoc* x y)': It searches for an element of the list
146 whose `car' equals `x', rather than for an element which equals `x'
147 itself. If `:key' is omitted or `nil', the filter is effectively the
150 The `:test' and `:test-not' arguments should be either `nil', or
151 functions of two arguments. The test function is used to compare two
152 sequence elements, or to compare a search value with sequence elements.
153 (The two values are passed to the test function in the same order as
154 the original sequence function arguments from which they are derived,
155 or, if they both come from the same sequence, in the same order as they
156 appear in that sequence.) The `:test' argument specifies a function
157 which must return true (non-`nil') to indicate a match; instead, you
158 may use `:test-not' to give a function which returns *false* to
159 indicate a match. The default test function is `:test 'eql'.
161 Many functions which take ITEM and `:test' or `:test-not' arguments
162 also come in `-if' and `-if-not' varieties, where a PREDICATE function
163 is passed instead of ITEM, and sequence elements match if the predicate
164 returns true on them (or false in the case of `-if-not'). For example:
166 (remove* 0 seq :test '=) == (remove-if 'zerop seq)
168 to remove all zeros from sequence `seq'.
170 Some operations can work on a subsequence of the argument sequence;
171 these function take `:start' and `:end' arguments which default to zero
172 and the length of the sequence, respectively. Only elements between
173 START (inclusive) and END (exclusive) are affected by the operation.
174 The END argument may be passed `nil' to signify the length of the
175 sequence; otherwise, both START and END must be integers, with `0 <=
176 START <= END <= (length SEQ)'. If the function takes two sequence
177 arguments, the limits are defined by keywords `:start1' and `:end1' for
178 the first, and `:start2' and `:end2' for the second.
180 A few functions accept a `:from-end' argument, which, if non-`nil',
181 causes the operation to go from right-to-left through the sequence
182 instead of left-to-right, and a `:count' argument, which specifies an
183 integer maximum number of elements to be removed or otherwise processed.
185 The sequence functions make no guarantees about the order in which
186 the `:test', `:test-not', and `:key' functions are called on various
187 elements. Therefore, it is a bad idea to depend on side effects of
188 these functions. For example, `:from-end' may cause the sequence to be
189 scanned actually in reverse, or it may be scanned forwards but
190 computing a result "as if" it were scanned backwards. (Some functions,
191 like `mapcar*' and `every', *do* specify exactly the order in which the
192 function is called so side effects are perfectly acceptable in those
195 Strings in GNU Emacs 19 may contain "text properties" as well as
196 character data. Except as noted, it is undefined whether or not text
197 properties are preserved by sequence functions. For example, `(remove*
198 ?A STR)' may or may not preserve the properties of the characters
199 copied from STR into the result.
202 File: cl.info, Node: Mapping over Sequences, Next: Sequence Functions, Prev: Sequence Basics, Up: Sequences
204 Mapping over Sequences
205 ======================
207 These functions "map" the function you specify over the elements of
208 lists or arrays. They are all variations on the theme of the built-in
211 - Function: mapcar* FUNCTION SEQ &rest MORE-SEQS
212 This function calls FUNCTION on successive parallel sets of
213 elements from its argument sequences. Given a single SEQ argument
214 it is equivalent to `mapcar'; given N sequences, it calls the
215 function with the first elements of each of the sequences as the N
216 arguments to yield the first element of the result list, then with
217 the second elements, and so on. The mapping stops as soon as the
218 shortest sequence runs out. The argument sequences may be any
219 mixture of lists, strings, and vectors; the return sequence is
222 Common Lisp's `mapcar' accepts multiple arguments but works only
223 on lists; Emacs Lisp's `mapcar' accepts a single sequence
224 argument. This package's `mapcar*' works as a compatible superset
227 - Function: map RESULT-TYPE FUNCTION SEQ &rest MORE-SEQS
228 This function maps FUNCTION over the argument sequences, just like
229 `mapcar*', but it returns a sequence of type RESULT-TYPE rather
230 than a list. RESULT-TYPE must be one of the following symbols:
231 `vector', `string', `list' (in which case the effect is the same
232 as for `mapcar*'), or `nil' (in which case the results are thrown
233 away and `map' returns `nil').
235 - Function: maplist FUNCTION LIST &rest MORE-LISTS
236 This function calls FUNCTION on each of its argument lists, then
237 on the `cdr's of those lists, and so on, until the shortest list
238 runs out. The results are returned in the form of a list. Thus,
239 `maplist' is like `mapcar*' except that it passes in the list
240 pointers themselves rather than the `car's of the advancing
243 - Function: mapc FUNCTION SEQ &rest MORE-SEQS
244 This function is like `mapcar*', except that the values returned
245 by FUNCTION are ignored and thrown away rather than being
246 collected into a list. The return value of `mapc' is SEQ, the
249 - Function: mapl FUNCTION LIST &rest MORE-LISTS
250 This function is like `maplist', except that it throws away the
251 values returned by FUNCTION.
253 - Function: mapcan FUNCTION SEQ &rest MORE-SEQS
254 This function is like `mapcar*', except that it concatenates the
255 return values (which must be lists) using `nconc', rather than
256 simply collecting them into a list.
258 - Function: mapcon FUNCTION LIST &rest MORE-LISTS
259 This function is like `maplist', except that it concatenates the
260 return values using `nconc'.
262 - Function: some PREDICATE SEQ &rest MORE-SEQS
263 This function calls PREDICATE on each element of SEQ in turn; if
264 PREDICATE returns a non-`nil' value, `some' returns that value,
265 otherwise it returns `nil'. Given several sequence arguments, it
266 steps through the sequences in parallel until the shortest one
267 runs out, just as in `mapcar*'. You can rely on the left-to-right
268 order in which the elements are visited, and on the fact that
269 mapping stops immediately as soon as PREDICATE returns non-`nil'.
271 - Function: every PREDICATE SEQ &rest MORE-SEQS
272 This function calls PREDICATE on each element of the sequence(s)
273 in turn; it returns `nil' as soon as PREDICATE returns `nil' for
274 any element, or `t' if the predicate was true for all elements.
276 - Function: notany PREDICATE SEQ &rest MORE-SEQS
277 This function calls PREDICATE on each element of the sequence(s)
278 in turn; it returns `nil' as soon as PREDICATE returns a non-`nil'
279 value for any element, or `t' if the predicate was `nil' for all
282 - Function: notevery PREDICATE SEQ &rest MORE-SEQS
283 This function calls PREDICATE on each element of the sequence(s)
284 in turn; it returns a non-`nil' value as soon as PREDICATE returns
285 `nil' for any element, or `t' if the predicate was true for all
288 - Function: reduce FUNCTION SEQ &key :from-end :start :end
290 This function combines the elements of SEQ using an associative
291 binary operation. Suppose FUNCTION is `*' and SEQ is the list `(2
292 3 4 5)'. The first two elements of the list are combined with `(*
293 2 3) = 6'; this is combined with the next element, `(* 6 4) = 24',
294 and that is combined with the final element: `(* 24 5) = 120'.
295 Note that the `*' function happens to be self-reducing, so that
296 `(* 2 3 4 5)' has the same effect as an explicit call to `reduce'.
298 If `:from-end' is true, the reduction is right-associative instead
301 (reduce '- '(1 2 3 4))
302 == (- (- (- 1 2) 3) 4) => -8
303 (reduce '- '(1 2 3 4) :from-end t)
304 == (- 1 (- 2 (- 3 4))) => -2
306 If `:key' is specified, it is a function of one argument which is
307 called on each of the sequence elements in turn.
309 If `:initial-value' is specified, it is effectively added to the
310 front (or rear in the case of `:from-end') of the sequence. The
311 `:key' function is *not* applied to the initial value.
313 If the sequence, including the initial value, has exactly one
314 element then that element is returned without ever calling
315 FUNCTION. If the sequence is empty (and there is no initial
316 value), then FUNCTION is called with no arguments to obtain the
319 All of these mapping operations can be expressed conveniently in
320 terms of the `loop' macro. In compiled code, `loop' will be faster
321 since it generates the loop as in-line code with no function calls.
324 File: cl.info, Node: Sequence Functions, Next: Searching Sequences, Prev: Mapping over Sequences, Up: Sequences
329 This section describes a number of Common Lisp functions for operating
332 - Function: subseq SEQUENCE START &optional END
333 This function returns a given subsequence of the argument
334 SEQUENCE, which may be a list, string, or vector. The indices
335 START and END must be in range, and START must be no greater than
336 END. If END is omitted, it defaults to the length of the
337 sequence. The return value is always a copy; it does not share
338 structure with SEQUENCE.
340 As an extension to Common Lisp, START and/or END may be negative,
341 in which case they represent a distance back from the end of the
342 sequence. This is for compatibility with Emacs' `substring'
343 function. Note that `subseq' is the *only* sequence function that
344 allows negative START and END.
346 You can use `setf' on a `subseq' form to replace a specified range
347 of elements with elements from another sequence. The replacement
348 is done as if by `replace', described below.
350 - Function: concatenate RESULT-TYPE &rest SEQS
351 This function concatenates the argument sequences together to form
352 a result sequence of type RESULT-TYPE, one of the symbols
353 `vector', `string', or `list'. The arguments are always copied,
354 even in cases such as `(concatenate 'list '(1 2 3))' where the
355 result is identical to an argument.
357 - Function: fill SEQ ITEM &key :start :end
358 This function fills the elements of the sequence (or the specified
359 part of the sequence) with the value ITEM.
361 - Function: replace SEQ1 SEQ2 &key :start1 :end1 :start2 :end2
362 This function copies part of SEQ2 into part of SEQ1. The sequence
363 SEQ1 is not stretched or resized; the amount of data copied is
364 simply the shorter of the source and destination (sub)sequences.
365 The function returns SEQ1.
367 If SEQ1 and SEQ2 are `eq', then the replacement will work
368 correctly even if the regions indicated by the start and end
369 arguments overlap. However, if SEQ1 and SEQ2 are lists which
370 share storage but are not `eq', and the start and end arguments
371 specify overlapping regions, the effect is undefined.
373 - Function: remove* ITEM SEQ &key :test :test-not :key :count :start
375 This returns a copy of SEQ with all elements matching ITEM
376 removed. The result may share storage with or be `eq' to SEQ in
377 some circumstances, but the original SEQ will not be modified.
378 The `:test', `:test-not', and `:key' arguments define the matching
379 test that is used; by default, elements `eql' to ITEM are removed.
380 The `:count' argument specifies the maximum number of matching
381 elements that can be removed (only the leftmost COUNT matches are
382 removed). The `:start' and `:end' arguments specify a region in
383 SEQ in which elements will be removed; elements outside that
384 region are not matched or removed. The `:from-end' argument, if
385 true, says that elements should be deleted from the end of the
386 sequence rather than the beginning (this matters only if COUNT was
389 - Function: delete* ITEM SEQ &key :test :test-not :key :count :start
391 This deletes all elements of SEQ which match ITEM. It is a
392 destructive operation. Since Emacs Lisp does not support
393 stretchable strings or vectors, this is the same as `remove*' for
394 those sequence types. On lists, `remove*' will copy the list if
395 necessary to preserve the original list, whereas `delete*' will
396 splice out parts of the argument list. Compare `append' and
397 `nconc', which are analogous non-destructive and destructive list
398 operations in Emacs Lisp.
400 The predicate-oriented functions `remove-if', `remove-if-not',
401 `delete-if', and `delete-if-not' are defined similarly.
403 - Function: delete ITEM LIST
404 This MacLisp-compatible function deletes from LIST all elements
405 which are `equal' to ITEM. The `delete' function is built-in to
406 Emacs 19; this package defines it equivalently in Emacs 18.
408 - Function: remove ITEM LIST
409 This function removes from LIST all elements which are `equal' to
410 ITEM. This package defines it for symmetry with `delete', even
411 though `remove' is not built-in to Emacs 19.
413 - Function: remq ITEM LIST
414 This function removes from LIST all elements which are `eq' to
415 ITEM. This package defines it for symmetry with `delq', even
416 though `remq' is not built-in to Emacs 19.
418 - Function: remove-duplicates SEQ &key :test :test-not :key :start
420 This function returns a copy of SEQ with duplicate elements
421 removed. Specifically, if two elements from the sequence match
422 according to the `:test', `:test-not', and `:key' arguments, only
423 the rightmost one is retained. If `:from-end' is true, the
424 leftmost one is retained instead. If `:start' or `:end' is
425 specified, only elements within that subsequence are examined or
428 - Function: delete-duplicates SEQ &key :test :test-not :key :start
430 This function deletes duplicate elements from SEQ. It is a
431 destructive version of `remove-duplicates'.
433 - Function: substitute NEW OLD SEQ &key :test :test-not :key :count
434 :start :end :from-end
435 This function returns a copy of SEQ, with all elements matching
436 OLD replaced with NEW. The `:count', `:start', `:end', and
437 `:from-end' arguments may be used to limit the number of
440 - Function: nsubstitute NEW OLD SEQ &key :test :test-not :key :count
441 :start :end :from-end
442 This is a destructive version of `substitute'; it performs the
443 substitution using `setcar' or `aset' rather than by returning a
444 changed copy of the sequence.
446 The `substitute-if', `substitute-if-not', `nsubstitute-if', and
447 `nsubstitute-if-not' functions are defined similarly. For these, a
448 PREDICATE is given in place of the OLD argument.
451 File: cl.info, Node: Searching Sequences, Next: Sorting Sequences, Prev: Sequence Functions, Up: Sequences
456 These functions search for elements or subsequences in a sequence.
457 (See also `member*' and `assoc*'; *note Lists::..)
459 - Function: find ITEM SEQ &key :test :test-not :key :start :end
461 This function searches SEQ for an element matching ITEM. If it
462 finds a match, it returns the matching element. Otherwise, it
463 returns `nil'. It returns the leftmost match, unless `:from-end'
464 is true, in which case it returns the rightmost match. The
465 `:start' and `:end' arguments may be used to limit the range of
466 elements that are searched.
468 - Function: position ITEM SEQ &key :test :test-not :key :start :end
470 This function is like `find', except that it returns the integer
471 position in the sequence of the matching item rather than the item
472 itself. The position is relative to the start of the sequence as
473 a whole, even if `:start' is non-zero. The function returns `nil'
474 if no matching element was found.
476 - Function: count ITEM SEQ &key :test :test-not :key :start :end
477 This function returns the number of elements of SEQ which match
478 ITEM. The result is always a nonnegative integer.
480 The `find-if', `find-if-not', `position-if', `position-if-not',
481 `count-if', and `count-if-not' functions are defined similarly.
483 - Function: mismatch SEQ1 SEQ2 &key :test :test-not :key :start1 :end1
484 :start2 :end2 :from-end
485 This function compares the specified parts of SEQ1 and SEQ2. If
486 they are the same length and the corresponding elements match
487 (according to `:test', `:test-not', and `:key'), the function
488 returns `nil'. If there is a mismatch, the function returns the
489 index (relative to SEQ1) of the first mismatching element. This
490 will be the leftmost pair of elements which do not match, or the
491 position at which the shorter of the two otherwise-matching
494 If `:from-end' is true, then the elements are compared from right
495 to left starting at `(1- END1)' and `(1- END2)'. If the sequences
496 differ, then one plus the index of the rightmost difference
497 (relative to SEQ1) is returned.
499 An interesting example is `(mismatch str1 str2 :key 'upcase)',
500 which compares two strings case-insensitively.
502 - Function: search SEQ1 SEQ2 &key :test :test-not :key :from-end
503 :start1 :end1 :start2 :end2
504 This function searches SEQ2 for a subsequence that matches SEQ1
505 (or part of it specified by `:start1' and `:end1'.) Only matches
506 which fall entirely within the region defined by `:start2' and
507 `:end2' will be considered. The return value is the index of the
508 leftmost element of the leftmost match, relative to the start of
509 SEQ2, or `nil' if no matches were found. If `:from-end' is true,
510 the function finds the *rightmost* matching subsequence.
513 File: cl.info, Node: Sorting Sequences, Prev: Searching Sequences, Up: Sequences
518 - Function: sort* SEQ PREDICATE &key :key
519 This function sorts SEQ into increasing order as determined by
520 using PREDICATE to compare pairs of elements. PREDICATE should
521 return true (non-`nil') if and only if its first argument is less
522 than (not equal to) its second argument. For example, `<' and
523 `string-lessp' are suitable predicate functions for sorting
524 numbers and strings, respectively; `>' would sort numbers into
525 decreasing rather than increasing order.
527 This function differs from Emacs' built-in `sort' in that it can
528 operate on any type of sequence, not just lists. Also, it accepts
529 a `:key' argument which is used to preprocess data fed to the
530 PREDICATE function. For example,
532 (setq data (sort data 'string-lessp :key 'downcase))
534 sorts DATA, a sequence of strings, into increasing alphabetical
535 order without regard to case. A `:key' function of `car' would be
536 useful for sorting association lists.
538 The `sort*' function is destructive; it sorts lists by actually
539 rearranging the `cdr' pointers in suitable fashion.
541 - Function: stable-sort SEQ PREDICATE &key :key
542 This function sorts SEQ "stably", meaning two elements which are
543 equal in terms of PREDICATE are guaranteed not to be rearranged
544 out of their original order by the sort.
546 In practice, `sort*' and `stable-sort' are equivalent in Emacs
547 Lisp because the underlying `sort' function is stable by default.
548 However, this package reserves the right to use non-stable methods
549 for `sort*' in the future.
551 - Function: merge TYPE SEQ1 SEQ2 PREDICATE &key :key
552 This function merges two sequences SEQ1 and SEQ2 by interleaving
553 their elements. The result sequence, of type TYPE (in the sense
554 of `concatenate'), has length equal to the sum of the lengths of
555 the two input sequences. The sequences may be modified
556 destructively. Order of elements within SEQ1 and SEQ2 is
557 preserved in the interleaving; elements of the two sequences are
558 compared by PREDICATE (in the sense of `sort') and the lesser
559 element goes first in the result. When elements are equal, those
560 from SEQ1 precede those from SEQ2 in the result. Thus, if SEQ1
561 and SEQ2 are both sorted according to PREDICATE, then the result
562 will be a merged sequence which is (stably) sorted according to
566 File: cl.info, Node: Lists, Next: Hash Tables, Prev: Sequences, Up: Top
571 The functions described here operate on lists.
575 * List Functions:: `caddr', `first', `last', `list*', etc.
576 * Substitution of Expressions:: `subst', `sublis', etc.
577 * Lists as Sets:: `member*', `adjoin', `union', etc.
578 * Association Lists:: `assoc*', `rassoc*', `acons', `pairlis'
581 File: cl.info, Node: List Functions, Next: Substitution of Expressions, Prev: Lists, Up: Lists
586 This section describes a number of simple operations on lists, i.e.,
587 chains of cons cells.
590 This function is equivalent to `(car (cdr (cdr X)))'. Likewise,
591 this package defines all 28 `cXXXr' functions where XXX is up to
592 four `a's and/or `d's. All of these functions are `setf'-able,
593 and calls to them are expanded inline by the byte-compiler for
597 This function is a synonym for `(car X)'. Likewise, the functions
598 `second', `third', ..., through `tenth' return the given element
602 This function is a synonym for `(cdr X)'.
605 Common Lisp defines this function to act like `null', but
606 signalling an error if `x' is neither a `nil' nor a cons cell.
607 This package simply defines `endp' as a synonym for `null'.
609 - Function: list-length X
610 This function returns the length of list X, exactly like `(length
611 X)', except that if X is a circular list (where the cdr-chain
612 forms a loop rather than terminating with `nil'), this function
613 returns `nil'. (The regular `length' function would get stuck if
614 given a circular list.)
616 - Function: last X &optional N
617 This function returns the last cons, or the Nth-to-last cons, of
618 the list X. If N is omitted it defaults to 1. The "last cons"
619 means the first cons cell of the list whose `cdr' is not another
620 cons cell. (For normal lists, the `cdr' of the last cons will be
621 `nil'.) This function returns `nil' if X is `nil' or shorter than
622 N. Note that the last *element* of the list is `(car (last X))'.
624 - Function: butlast X &optional N
625 This function returns the list X with the last element, or the
626 last N elements, removed. If N is greater than zero it makes a
627 copy of the list so as not to damage the original list. In
628 general, `(append (butlast X N) (last X N))' will return a list
631 - Function: nbutlast X &optional N
632 This is a version of `butlast' that works by destructively
633 modifying the `cdr' of the appropriate element, rather than making
636 - Function: list* ARG &rest OTHERS
637 This function constructs a list of its arguments. The final
638 argument becomes the `cdr' of the last cell constructed. Thus,
639 `(list* A B C)' is equivalent to `(cons A (cons B C))', and
640 `(list* A B nil)' is equivalent to `(list A B)'.
642 (Note that this function really is called `list*' in Common Lisp;
643 it is not a name invented for this package like `member*' or
646 - Function: ldiff LIST SUBLIST
647 If SUBLIST is a sublist of LIST, i.e., is `eq' to one of the cons
648 cells of LIST, then this function returns a copy of the part of
649 LIST up to but not including SUBLIST. For example, `(ldiff x
650 (cddr x))' returns the first two elements of the list `x'. The
651 result is a copy; the original LIST is not modified. If SUBLIST
652 is not a sublist of LIST, a copy of the entire LIST is returned.
654 - Function: copy-list LIST
655 This function returns a copy of the list LIST. It copies dotted
656 lists like `(1 2 . 3)' correctly.
658 - Function: copy-tree X &optional VECP
659 This function returns a copy of the tree of cons cells X. Unlike
660 `copy-sequence' (and its alias `copy-list'), which copies only
661 along the `cdr' direction, this function copies (recursively)
662 along both the `car' and the `cdr' directions. If X is not a cons
663 cell, the function simply returns X unchanged. If the optional
664 VECP argument is true, this function copies vectors (recursively)
665 as well as cons cells.
667 - Function: tree-equal X Y &key :test :test-not :key
668 This function compares two trees of cons cells. If X and Y are
669 both cons cells, their `car's and `cdr's are compared recursively.
670 If neither X nor Y is a cons cell, they are compared by `eql', or
671 according to the specified test. The `:key' function, if
672 specified, is applied to the elements of both trees. *Note
676 File: cl.info, Node: Substitution of Expressions, Next: Lists as Sets, Prev: List Functions, Up: Lists
678 Substitution of Expressions
679 ===========================
681 These functions substitute elements throughout a tree of cons cells.
682 (*Note Sequence Functions::, for the `substitute' function, which works
683 on just the top-level elements of a list.)
685 - Function: subst NEW OLD TREE &key :test :test-not :key
686 This function substitutes occurrences of OLD with NEW in TREE, a
687 tree of cons cells. It returns a substituted tree, which will be
688 a copy except that it may share storage with the argument TREE in
689 parts where no substitutions occurred. The original TREE is not
690 modified. This function recurses on, and compares against OLD,
691 both `car's and `cdr's of the component cons cells. If OLD is
692 itself a cons cell, then matching cells in the tree are
693 substituted as usual without recursively substituting in that
694 cell. Comparisons with OLD are done according to the specified
695 test (`eql' by default). The `:key' function is applied to the
696 elements of the tree but not to OLD.
698 - Function: nsubst NEW OLD TREE &key :test :test-not :key
699 This function is like `subst', except that it works by destructive
700 modification (by `setcar' or `setcdr') rather than copying.
702 The `subst-if', `subst-if-not', `nsubst-if', and `nsubst-if-not'
703 functions are defined similarly.
705 - Function: sublis ALIST TREE &key :test :test-not :key
706 This function is like `subst', except that it takes an association
707 list ALIST of OLD-NEW pairs. Each element of the tree (after
708 applying the `:key' function, if any), is compared with the `car's
709 of ALIST; if it matches, it is replaced by the corresponding `cdr'.
711 - Function: nsublis ALIST TREE &key :test :test-not :key
712 This is a destructive version of `sublis'.
715 File: cl.info, Node: Lists as Sets, Next: Association Lists, Prev: Substitution of Expressions, Up: Lists
720 These functions perform operations on lists which represent sets of
723 - Function: member ITEM LIST
724 This MacLisp-compatible function searches LIST for an element
725 which is `equal' to ITEM. The `member' function is built-in to
726 Emacs 19; this package defines it equivalently in Emacs 18. See
727 the following function for a Common-Lisp compatible version.
729 - Function: member* ITEM LIST &key :test :test-not :key
730 This function searches LIST for an element matching ITEM. If a
731 match is found, it returns the cons cell whose `car' was the
732 matching element. Otherwise, it returns `nil'. Elements are
733 compared by `eql' by default; you can use the `:test',
734 `:test-not', and `:key' arguments to modify this behavior. *Note
737 Note that this function's name is suffixed by `*' to avoid the
738 incompatible `member' function defined in Emacs 19. (That
739 function uses `equal' for comparisons; it is equivalent to
740 `(member* ITEM LIST :test 'equal)'.)
742 The `member-if' and `member-if-not' functions analogously search for
743 elements which satisfy a given predicate.
745 - Function: tailp SUBLIST LIST
746 This function returns `t' if SUBLIST is a sublist of LIST, i.e.,
747 if SUBLIST is `eql' to LIST or to any of its `cdr's.
749 - Function: adjoin ITEM LIST &key :test :test-not :key
750 This function conses ITEM onto the front of LIST, like `(cons ITEM
751 LIST)', but only if ITEM is not already present on the list (as
752 determined by `member*'). If a `:key' argument is specified, it
753 is applied to ITEM as well as to the elements of LIST during the
754 search, on the reasoning that ITEM is "about" to become part of
757 - Function: union LIST1 LIST2 &key :test :test-not :key
758 This function combines two lists which represent sets of items,
759 returning a list that represents the union of those two sets. The
760 result list will contain all items which appear in LIST1 or LIST2,
761 and no others. If an item appears in both LIST1 and LIST2 it will
762 be copied only once. If an item is duplicated in LIST1 or LIST2,
763 it is undefined whether or not that duplication will survive in the
764 result list. The order of elements in the result list is also
767 - Function: nunion LIST1 LIST2 &key :test :test-not :key
768 This is a destructive version of `union'; rather than copying, it
769 tries to reuse the storage of the argument lists if possible.
771 - Function: intersection LIST1 LIST2 &key :test :test-not :key
772 This function computes the intersection of the sets represented by
773 LIST1 and LIST2. It returns the list of items which appear in
774 both LIST1 and LIST2.
776 - Function: nintersection LIST1 LIST2 &key :test :test-not :key
777 This is a destructive version of `intersection'. It tries to
778 reuse storage of LIST1 rather than copying. It does *not* reuse
779 the storage of LIST2.
781 - Function: set-difference LIST1 LIST2 &key :test :test-not :key
782 This function computes the "set difference" of LIST1 and LIST2,
783 i.e., the set of elements that appear in LIST1 but *not* in LIST2.
785 - Function: nset-difference LIST1 LIST2 &key :test :test-not :key
786 This is a destructive `set-difference', which will try to reuse
789 - Function: set-exclusive-or LIST1 LIST2 &key :test :test-not :key
790 This function computes the "set exclusive or" of LIST1 and LIST2,
791 i.e., the set of elements that appear in exactly one of LIST1 and
794 - Function: nset-exclusive-or LIST1 LIST2 &key :test :test-not :key
795 This is a destructive `set-exclusive-or', which will try to reuse
796 LIST1 and LIST2 if possible.
798 - Function: subsetp LIST1 LIST2 &key :test :test-not :key
799 This function checks whether LIST1 represents a subset of LIST2,
800 i.e., whether every element of LIST1 also appears in LIST2.
803 File: cl.info, Node: Association Lists, Prev: Lists as Sets, Up: Lists
808 An "association list" is a list representing a mapping from one set of
809 values to another; any list whose elements are cons cells is an
812 - Function: assoc* ITEM A-LIST &key :test :test-not :key
813 This function searches the association list A-LIST for an element
814 whose `car' matches (in the sense of `:test', `:test-not', and
815 `:key', or by comparison with `eql') a given ITEM. It returns the
816 matching element, if any, otherwise `nil'. It ignores elements of
817 A-LIST which are not cons cells. (This corresponds to the
818 behavior of `assq' and `assoc' in Emacs Lisp; Common Lisp's
819 `assoc' ignores `nil's but considers any other non-cons elements
820 of A-LIST to be an error.)
822 - Function: rassoc* ITEM A-LIST &key :test :test-not :key
823 This function searches for an element whose `cdr' matches ITEM.
824 If A-LIST represents a mapping, this applies the inverse of the
827 - Function: rassoc ITEM A-LIST
828 This function searches like `rassoc*' with a `:test' argument of
829 `equal'. It is analogous to Emacs Lisp's standard `assoc'
830 function, which derives from the MacLisp rather than the Common
833 The `assoc-if', `assoc-if-not', `rassoc-if', and `rassoc-if-not'
834 functions are defined similarly.
836 Two simple functions for constructing association lists are:
838 - Function: acons KEY VALUE ALIST
839 This is equivalent to `(cons (cons KEY VALUE) ALIST)'.
841 - Function: pairlis KEYS VALUES &optional ALIST
842 This is equivalent to `(nconc (mapcar* 'cons KEYS VALUES) ALIST)'.
845 File: cl.info, Node: Hash Tables, Next: Structures, Prev: Lists, Up: Top
850 Hash tables are now implemented directly in the C code and documented in
851 *Note Hash Tables: (lispref)Hash Tables.