1 This is ../info/cl.info, produced by makeinfo version 4.0 from cl.texi.
3 INFO-DIR-SECTION XEmacs Editor
5 * Common Lisp: (cl). GNU Emacs Common Lisp emulation package.
8 This file documents the GNU Emacs Common Lisp emulation package.
10 Copyright (C) 1993 Free Software Foundation, Inc.
12 Permission is granted to make and distribute verbatim copies of this
13 manual provided the copyright notice and this permission notice are
14 preserved on all copies.
16 Permission is granted to copy and distribute modified versions of
17 this manual under the conditions for verbatim copying, provided also
18 that the section entitled "GNU General Public License" is included
19 exactly as in the original, and provided that the entire resulting
20 derived work is distributed under the terms of a permission notice
21 identical to this one.
23 Permission is granted to copy and distribute translations of this
24 manual into another language, under the above conditions for modified
25 versions, except that the section entitled "GNU General Public License"
26 may be included in a translation approved by the author instead of in
30 File: cl.info, Node: Implementation Parameters, Prev: Random Numbers, Up: Numbers
32 Implementation Parameters
33 =========================
35 This package defines several useful constants having to with numbers.
37 - Variable: most-positive-fixnum
38 This constant equals the largest value a Lisp integer can hold.
39 It is typically `2^23-1' or `2^25-1'.
41 - Variable: most-negative-fixnum
42 This constant equals the smallest (most negative) value a Lisp
45 The following parameters have to do with floating-point numbers.
46 This package determines their values by exercising the computer's
47 floating-point arithmetic in various ways. Because this operation
48 might be slow, the code for initializing them is kept in a separate
49 function that must be called before the parameters can be used.
51 - Function: cl-float-limits
52 This function makes sure that the Common Lisp floating-point
53 parameters like `most-positive-float' have been initialized.
54 Until it is called, these parameters will be `nil'. If this
55 version of Emacs does not support floats (e.g., most versions of
56 Emacs 18), the parameters will remain `nil'. If the parameters
57 have already been initialized, the function returns immediately.
59 The algorithm makes assumptions that will be valid for most modern
60 machines, but will fail if the machine's arithmetic is extremely
61 unusual, e.g., decimal.
63 Since true Common Lisp supports up to four different floating-point
64 precisions, it has families of constants like
65 `most-positive-single-float', `most-positive-double-float',
66 `most-positive-long-float', and so on. Emacs has only one
67 floating-point precision, so this package omits the precision word from
70 - Variable: most-positive-float
71 This constant equals the largest value a Lisp float can hold. For
72 those systems whose arithmetic supports infinities, this is the
73 largest _finite_ value. For IEEE machines, the value is
74 approximately `1.79e+308'.
76 - Variable: most-negative-float
77 This constant equals the most-negative value a Lisp float can hold.
78 (It is assumed to be equal to `(- most-positive-float)'.)
80 - Variable: least-positive-float
81 This constant equals the smallest Lisp float value greater than
82 zero. For IEEE machines, it is about `4.94e-324' if denormals are
83 supported or `2.22e-308' if not.
85 - Variable: least-positive-normalized-float
86 This constant equals the smallest _normalized_ Lisp float greater
87 than zero, i.e., the smallest value for which IEEE denormalization
88 will not result in a loss of precision. For IEEE machines, this
89 value is about `2.22e-308'. For machines that do not support the
90 concept of denormalization and gradual underflow, this constant
91 will always equal `least-positive-float'.
93 - Variable: least-negative-float
94 This constant is the negative counterpart of
95 `least-positive-float'.
97 - Variable: least-negative-normalized-float
98 This constant is the negative counterpart of
99 `least-positive-normalized-float'.
101 - Variable: float-epsilon
102 This constant is the smallest positive Lisp float that can be added
103 to 1.0 to produce a distinct value. Adding a smaller number to 1.0
104 will yield 1.0 again due to roundoff. For IEEE machines, epsilon
107 - Variable: float-negative-epsilon
108 This is the smallest positive value that can be subtracted from
109 1.0 to produce a distinct value. For IEEE machines, it is about
113 File: cl.info, Node: Sequences, Next: Lists, Prev: Numbers, Up: Top
118 Common Lisp defines a number of functions that operate on "sequences",
119 which are either lists, strings, or vectors. Emacs Lisp includes a few
120 of these, notably `elt' and `length'; this package defines most of the
125 * Sequence Basics:: Arguments shared by all sequence functions
126 * Mapping over Sequences:: `mapcar*', `mapcan', `map', `every', etc.
127 * Sequence Functions:: `subseq', `remove*', `substitute', etc.
128 * Searching Sequences:: `find', `position', `count', `search', etc.
129 * Sorting Sequences:: `sort*', `stable-sort', `merge'
132 File: cl.info, Node: Sequence Basics, Next: Mapping over Sequences, Prev: Sequences, Up: Sequences
137 Many of the sequence functions take keyword arguments; *note Argument
138 Lists::. All keyword arguments are optional and, if specified, may
141 The `:key' argument should be passed either `nil', or a function of
142 one argument. This key function is used as a filter through which the
143 elements of the sequence are seen; for example, `(find x y :key 'car)'
144 is similar to `(assoc* x y)': It searches for an element of the list
145 whose `car' equals `x', rather than for an element which equals `x'
146 itself. If `:key' is omitted or `nil', the filter is effectively the
149 The `:test' and `:test-not' arguments should be either `nil', or
150 functions of two arguments. The test function is used to compare two
151 sequence elements, or to compare a search value with sequence elements.
152 (The two values are passed to the test function in the same order as
153 the original sequence function arguments from which they are derived,
154 or, if they both come from the same sequence, in the same order as they
155 appear in that sequence.) The `:test' argument specifies a function
156 which must return true (non-`nil') to indicate a match; instead, you
157 may use `:test-not' to give a function which returns _false_ to
158 indicate a match. The default test function is `:test 'eql'.
160 Many functions which take ITEM and `:test' or `:test-not' arguments
161 also come in `-if' and `-if-not' varieties, where a PREDICATE function
162 is passed instead of ITEM, and sequence elements match if the predicate
163 returns true on them (or false in the case of `-if-not'). For example:
165 (remove* 0 seq :test '=) == (remove-if 'zerop seq)
167 to remove all zeros from sequence `seq'.
169 Some operations can work on a subsequence of the argument sequence;
170 these function take `:start' and `:end' arguments which default to zero
171 and the length of the sequence, respectively. Only elements between
172 START (inclusive) and END (exclusive) are affected by the operation.
173 The END argument may be passed `nil' to signify the length of the
174 sequence; otherwise, both START and END must be integers, with `0 <=
175 START <= END <= (length SEQ)'. If the function takes two sequence
176 arguments, the limits are defined by keywords `:start1' and `:end1' for
177 the first, and `:start2' and `:end2' for the second.
179 A few functions accept a `:from-end' argument, which, if non-`nil',
180 causes the operation to go from right-to-left through the sequence
181 instead of left-to-right, and a `:count' argument, which specifies an
182 integer maximum number of elements to be removed or otherwise processed.
184 The sequence functions make no guarantees about the order in which
185 the `:test', `:test-not', and `:key' functions are called on various
186 elements. Therefore, it is a bad idea to depend on side effects of
187 these functions. For example, `:from-end' may cause the sequence to be
188 scanned actually in reverse, or it may be scanned forwards but
189 computing a result "as if" it were scanned backwards. (Some functions,
190 like `mapcar*' and `every', _do_ specify exactly the order in which the
191 function is called so side effects are perfectly acceptable in those
194 Strings in GNU Emacs 19 may contain "text properties" as well as
195 character data. Except as noted, it is undefined whether or not text
196 properties are preserved by sequence functions. For example, `(remove*
197 ?A STR)' may or may not preserve the properties of the characters
198 copied from STR into the result.
201 File: cl.info, Node: Mapping over Sequences, Next: Sequence Functions, Prev: Sequence Basics, Up: Sequences
203 Mapping over Sequences
204 ======================
206 These functions "map" the function you specify over the elements of
207 lists or arrays. They are all variations on the theme of the built-in
210 - Function: mapcar* function seq &rest more-seqs
211 This function calls FUNCTION on successive parallel sets of
212 elements from its argument sequences. Given a single SEQ argument
213 it is equivalent to `mapcar'; given N sequences, it calls the
214 function with the first elements of each of the sequences as the N
215 arguments to yield the first element of the result list, then with
216 the second elements, and so on. The mapping stops as soon as the
217 shortest sequence runs out. The argument sequences may be any
218 mixture of lists, strings, and vectors; the return sequence is
221 Common Lisp's `mapcar' accepts multiple arguments but works only
222 on lists; Emacs Lisp's `mapcar' accepts a single sequence
223 argument. This package's `mapcar*' works as a compatible superset
226 - Function: map result-type function seq &rest more-seqs
227 This function maps FUNCTION over the argument sequences, just like
228 `mapcar*', but it returns a sequence of type RESULT-TYPE rather
229 than a list. RESULT-TYPE must be one of the following symbols:
230 `vector', `string', `list' (in which case the effect is the same
231 as for `mapcar*'), or `nil' (in which case the results are thrown
232 away and `map' returns `nil').
234 - Function: maplist function list &rest more-lists
235 This function calls FUNCTION on each of its argument lists, then
236 on the `cdr's of those lists, and so on, until the shortest list
237 runs out. The results are returned in the form of a list. Thus,
238 `maplist' is like `mapcar*' except that it passes in the list
239 pointers themselves rather than the `car's of the advancing
242 - Function: mapc function seq &rest more-seqs
243 This function is like `mapcar*', except that the values returned
244 by FUNCTION are ignored and thrown away rather than being
245 collected into a list. The return value of `mapc' is SEQ, the
248 - Function: mapl function list &rest more-lists
249 This function is like `maplist', except that it throws away the
250 values returned by FUNCTION.
252 - Function: mapcan function seq &rest more-seqs
253 This function is like `mapcar*', except that it concatenates the
254 return values (which must be lists) using `nconc', rather than
255 simply collecting them into a list.
257 - Function: mapcon function list &rest more-lists
258 This function is like `maplist', except that it concatenates the
259 return values using `nconc'.
261 - Function: some predicate seq &rest more-seqs
262 This function calls PREDICATE on each element of SEQ in turn; if
263 PREDICATE returns a non-`nil' value, `some' returns that value,
264 otherwise it returns `nil'. Given several sequence arguments, it
265 steps through the sequences in parallel until the shortest one
266 runs out, just as in `mapcar*'. You can rely on the left-to-right
267 order in which the elements are visited, and on the fact that
268 mapping stops immediately as soon as PREDICATE returns non-`nil'.
270 - Function: every predicate seq &rest more-seqs
271 This function calls PREDICATE on each element of the sequence(s)
272 in turn; it returns `nil' as soon as PREDICATE returns `nil' for
273 any element, or `t' if the predicate was true for all elements.
275 - Function: notany predicate seq &rest more-seqs
276 This function calls PREDICATE on each element of the sequence(s)
277 in turn; it returns `nil' as soon as PREDICATE returns a non-`nil'
278 value for any element, or `t' if the predicate was `nil' for all
281 - Function: notevery predicate seq &rest more-seqs
282 This function calls PREDICATE on each element of the sequence(s)
283 in turn; it returns a non-`nil' value as soon as PREDICATE returns
284 `nil' for any element, or `t' if the predicate was true for all
287 - Function: reduce function seq &key :from-end :start :end
289 This function combines the elements of SEQ using an associative
290 binary operation. Suppose FUNCTION is `*' and SEQ is the list `(2
291 3 4 5)'. The first two elements of the list are combined with `(*
292 2 3) = 6'; this is combined with the next element, `(* 6 4) = 24',
293 and that is combined with the final element: `(* 24 5) = 120'.
294 Note that the `*' function happens to be self-reducing, so that
295 `(* 2 3 4 5)' has the same effect as an explicit call to `reduce'.
297 If `:from-end' is true, the reduction is right-associative instead
300 (reduce '- '(1 2 3 4))
301 == (- (- (- 1 2) 3) 4) => -8
302 (reduce '- '(1 2 3 4) :from-end t)
303 == (- 1 (- 2 (- 3 4))) => -2
305 If `:key' is specified, it is a function of one argument which is
306 called on each of the sequence elements in turn.
308 If `:initial-value' is specified, it is effectively added to the
309 front (or rear in the case of `:from-end') of the sequence. The
310 `:key' function is _not_ applied to the initial value.
312 If the sequence, including the initial value, has exactly one
313 element then that element is returned without ever calling
314 FUNCTION. If the sequence is empty (and there is no initial
315 value), then FUNCTION is called with no arguments to obtain the
318 All of these mapping operations can be expressed conveniently in
319 terms of the `loop' macro. In compiled code, `loop' will be faster
320 since it generates the loop as in-line code with no function calls.
323 File: cl.info, Node: Sequence Functions, Next: Searching Sequences, Prev: Mapping over Sequences, Up: Sequences
328 This section describes a number of Common Lisp functions for operating
331 - Function: subseq sequence start &optional end
332 This function returns a given subsequence of the argument
333 SEQUENCE, which may be a list, string, or vector. The indices
334 START and END must be in range, and START must be no greater than
335 END. If END is omitted, it defaults to the length of the
336 sequence. The return value is always a copy; it does not share
337 structure with SEQUENCE.
339 As an extension to Common Lisp, START and/or END may be negative,
340 in which case they represent a distance back from the end of the
341 sequence. This is for compatibility with Emacs' `substring'
342 function. Note that `subseq' is the _only_ sequence function that
343 allows negative START and END.
345 You can use `setf' on a `subseq' form to replace a specified range
346 of elements with elements from another sequence. The replacement
347 is done as if by `replace', described below.
349 - Function: concatenate result-type &rest seqs
350 This function concatenates the argument sequences together to form
351 a result sequence of type RESULT-TYPE, one of the symbols
352 `vector', `string', or `list'. The arguments are always copied,
353 even in cases such as `(concatenate 'list '(1 2 3))' where the
354 result is identical to an argument.
356 - Function: fill seq item &key :start :end
357 This function fills the elements of the sequence (or the specified
358 part of the sequence) with the value ITEM.
360 - Function: replace seq1 seq2 &key :start1 :end1 :start2 :end2
361 This function copies part of SEQ2 into part of SEQ1. The sequence
362 SEQ1 is not stretched or resized; the amount of data copied is
363 simply the shorter of the source and destination (sub)sequences.
364 The function returns SEQ1.
366 If SEQ1 and SEQ2 are `eq', then the replacement will work
367 correctly even if the regions indicated by the start and end
368 arguments overlap. However, if SEQ1 and SEQ2 are lists which
369 share storage but are not `eq', and the start and end arguments
370 specify overlapping regions, the effect is undefined.
372 - Function: remove* item seq &key :test :test-not :key :count :start
374 This returns a copy of SEQ with all elements matching ITEM
375 removed. The result may share storage with or be `eq' to SEQ in
376 some circumstances, but the original SEQ will not be modified.
377 The `:test', `:test-not', and `:key' arguments define the matching
378 test that is used; by default, elements `eql' to ITEM are removed.
379 The `:count' argument specifies the maximum number of matching
380 elements that can be removed (only the leftmost COUNT matches are
381 removed). The `:start' and `:end' arguments specify a region in
382 SEQ in which elements will be removed; elements outside that
383 region are not matched or removed. The `:from-end' argument, if
384 true, says that elements should be deleted from the end of the
385 sequence rather than the beginning (this matters only if COUNT was
388 - Function: delete* item seq &key :test :test-not :key :count :start
390 This deletes all elements of SEQ which match ITEM. It is a
391 destructive operation. Since Emacs Lisp does not support
392 stretchable strings or vectors, this is the same as `remove*' for
393 those sequence types. On lists, `remove*' will copy the list if
394 necessary to preserve the original list, whereas `delete*' will
395 splice out parts of the argument list. Compare `append' and
396 `nconc', which are analogous non-destructive and destructive list
397 operations in Emacs Lisp.
399 The predicate-oriented functions `remove-if', `remove-if-not',
400 `delete-if', and `delete-if-not' are defined similarly.
402 - Function: delete item list
403 This MacLisp-compatible function deletes from LIST all elements
404 which are `equal' to ITEM. The `delete' function is built-in to
405 Emacs 19; this package defines it equivalently in Emacs 18.
407 - Function: remove item list
408 This function removes from LIST all elements which are `equal' to
409 ITEM. This package defines it for symmetry with `delete', even
410 though `remove' is not built-in to Emacs 19.
412 - Function: remq item list
413 This function removes from LIST all elements which are `eq' to
414 ITEM. This package defines it for symmetry with `delq', even
415 though `remq' is not built-in to Emacs 19.
417 - Function: remove-duplicates seq &key :test :test-not :key :start
419 This function returns a copy of SEQ with duplicate elements
420 removed. Specifically, if two elements from the sequence match
421 according to the `:test', `:test-not', and `:key' arguments, only
422 the rightmost one is retained. If `:from-end' is true, the
423 leftmost one is retained instead. If `:start' or `:end' is
424 specified, only elements within that subsequence are examined or
427 - Function: delete-duplicates seq &key :test :test-not :key :start
429 This function deletes duplicate elements from SEQ. It is a
430 destructive version of `remove-duplicates'.
432 - Function: substitute new old seq &key :test :test-not :key :count
433 :start :end :from-end
434 This function returns a copy of SEQ, with all elements matching
435 OLD replaced with NEW. The `:count', `:start', `:end', and
436 `:from-end' arguments may be used to limit the number of
439 - Function: nsubstitute new old seq &key :test :test-not :key :count
440 :start :end :from-end
441 This is a destructive version of `substitute'; it performs the
442 substitution using `setcar' or `aset' rather than by returning a
443 changed copy of the sequence.
445 The `substitute-if', `substitute-if-not', `nsubstitute-if', and
446 `nsubstitute-if-not' functions are defined similarly. For these, a
447 PREDICATE is given in place of the OLD argument.
450 File: cl.info, Node: Searching Sequences, Next: Sorting Sequences, Prev: Sequence Functions, Up: Sequences
455 These functions search for elements or subsequences in a sequence.
456 (See also `member*' and `assoc*'; *note Lists::.)
458 - Function: find item seq &key :test :test-not :key :start :end
460 This function searches SEQ for an element matching ITEM. If it
461 finds a match, it returns the matching element. Otherwise, it
462 returns `nil'. It returns the leftmost match, unless `:from-end'
463 is true, in which case it returns the rightmost match. The
464 `:start' and `:end' arguments may be used to limit the range of
465 elements that are searched.
467 - Function: position item seq &key :test :test-not :key :start :end
469 This function is like `find', except that it returns the integer
470 position in the sequence of the matching item rather than the item
471 itself. The position is relative to the start of the sequence as
472 a whole, even if `:start' is non-zero. The function returns `nil'
473 if no matching element was found.
475 - Function: count item seq &key :test :test-not :key :start :end
476 This function returns the number of elements of SEQ which match
477 ITEM. The result is always a nonnegative integer.
479 The `find-if', `find-if-not', `position-if', `position-if-not',
480 `count-if', and `count-if-not' functions are defined similarly.
482 - Function: mismatch seq1 seq2 &key :test :test-not :key :start1 :end1
483 :start2 :end2 :from-end
484 This function compares the specified parts of SEQ1 and SEQ2. If
485 they are the same length and the corresponding elements match
486 (according to `:test', `:test-not', and `:key'), the function
487 returns `nil'. If there is a mismatch, the function returns the
488 index (relative to SEQ1) of the first mismatching element. This
489 will be the leftmost pair of elements which do not match, or the
490 position at which the shorter of the two otherwise-matching
493 If `:from-end' is true, then the elements are compared from right
494 to left starting at `(1- END1)' and `(1- END2)'. If the sequences
495 differ, then one plus the index of the rightmost difference
496 (relative to SEQ1) is returned.
498 An interesting example is `(mismatch str1 str2 :key 'upcase)',
499 which compares two strings case-insensitively.
501 - Function: search seq1 seq2 &key :test :test-not :key :from-end
502 :start1 :end1 :start2 :end2
503 This function searches SEQ2 for a subsequence that matches SEQ1
504 (or part of it specified by `:start1' and `:end1'.) Only matches
505 which fall entirely within the region defined by `:start2' and
506 `:end2' will be considered. The return value is the index of the
507 leftmost element of the leftmost match, relative to the start of
508 SEQ2, or `nil' if no matches were found. If `:from-end' is true,
509 the function finds the _rightmost_ matching subsequence.
512 File: cl.info, Node: Sorting Sequences, Prev: Searching Sequences, Up: Sequences
517 - Function: sort* seq predicate &key :key
518 This function sorts SEQ into increasing order as determined by
519 using PREDICATE to compare pairs of elements. PREDICATE should
520 return true (non-`nil') if and only if its first argument is less
521 than (not equal to) its second argument. For example, `<' and
522 `string-lessp' are suitable predicate functions for sorting
523 numbers and strings, respectively; `>' would sort numbers into
524 decreasing rather than increasing order.
526 This function differs from Emacs' built-in `sort' in that it can
527 operate on any type of sequence, not just lists. Also, it accepts
528 a `:key' argument which is used to preprocess data fed to the
529 PREDICATE function. For example,
531 (setq data (sort data 'string-lessp :key 'downcase))
533 sorts DATA, a sequence of strings, into increasing alphabetical
534 order without regard to case. A `:key' function of `car' would be
535 useful for sorting association lists.
537 The `sort*' function is destructive; it sorts lists by actually
538 rearranging the `cdr' pointers in suitable fashion.
540 - Function: stable-sort seq predicate &key :key
541 This function sorts SEQ "stably", meaning two elements which are
542 equal in terms of PREDICATE are guaranteed not to be rearranged
543 out of their original order by the sort.
545 In practice, `sort*' and `stable-sort' are equivalent in Emacs
546 Lisp because the underlying `sort' function is stable by default.
547 However, this package reserves the right to use non-stable methods
548 for `sort*' in the future.
550 - Function: merge type seq1 seq2 predicate &key :key
551 This function merges two sequences SEQ1 and SEQ2 by interleaving
552 their elements. The result sequence, of type TYPE (in the sense
553 of `concatenate'), has length equal to the sum of the lengths of
554 the two input sequences. The sequences may be modified
555 destructively. Order of elements within SEQ1 and SEQ2 is
556 preserved in the interleaving; elements of the two sequences are
557 compared by PREDICATE (in the sense of `sort') and the lesser
558 element goes first in the result. When elements are equal, those
559 from SEQ1 precede those from SEQ2 in the result. Thus, if SEQ1
560 and SEQ2 are both sorted according to PREDICATE, then the result
561 will be a merged sequence which is (stably) sorted according to
565 File: cl.info, Node: Lists, Next: Hash Tables, Prev: Sequences, Up: Top
570 The functions described here operate on lists.
574 * List Functions:: `caddr', `first', `last', `list*', etc.
575 * Substitution of Expressions:: `subst', `sublis', etc.
576 * Lists as Sets:: `member*', `adjoin', `union', etc.
577 * Association Lists:: `assoc*', `rassoc*', `acons', `pairlis'
580 File: cl.info, Node: List Functions, Next: Substitution of Expressions, Prev: Lists, Up: Lists
585 This section describes a number of simple operations on lists, i.e.,
586 chains of cons cells.
589 This function is equivalent to `(car (cdr (cdr X)))'. Likewise,
590 this package defines all 28 `cXXXr' functions where XXX is up to
591 four `a's and/or `d's. All of these functions are `setf'-able,
592 and calls to them are expanded inline by the byte-compiler for
596 This function is a synonym for `(car X)'. Likewise, the functions
597 `second', `third', ..., through `tenth' return the given element
601 This function is a synonym for `(cdr X)'.
604 Common Lisp defines this function to act like `null', but
605 signalling an error if `x' is neither a `nil' nor a cons cell.
606 This package simply defines `endp' as a synonym for `null'.
608 - Function: list-length x
609 This function returns the length of list X, exactly like `(length
610 X)', except that if X is a circular list (where the cdr-chain
611 forms a loop rather than terminating with `nil'), this function
612 returns `nil'. (The regular `length' function would get stuck if
613 given a circular list.)
615 - Function: last x &optional n
616 This function returns the last cons, or the Nth-to-last cons, of
617 the list X. If N is omitted it defaults to 1. The "last cons"
618 means the first cons cell of the list whose `cdr' is not another
619 cons cell. (For normal lists, the `cdr' of the last cons will be
620 `nil'.) This function returns `nil' if X is `nil' or shorter than
621 N. Note that the last _element_ of the list is `(car (last X))'.
623 - Function: butlast x &optional n
624 This function returns the list X with the last element, or the
625 last N elements, removed. If N is greater than zero it makes a
626 copy of the list so as not to damage the original list. In
627 general, `(append (butlast X N) (last X N))' will return a list
630 - Function: nbutlast x &optional n
631 This is a version of `butlast' that works by destructively
632 modifying the `cdr' of the appropriate element, rather than making
635 - Function: list* arg &rest others
636 This function constructs a list of its arguments. The final
637 argument becomes the `cdr' of the last cell constructed. Thus,
638 `(list* A B C)' is equivalent to `(cons A (cons B C))', and
639 `(list* A B nil)' is equivalent to `(list A B)'.
641 (Note that this function really is called `list*' in Common Lisp;
642 it is not a name invented for this package like `member*' or
645 - Function: ldiff list sublist
646 If SUBLIST is a sublist of LIST, i.e., is `eq' to one of the cons
647 cells of LIST, then this function returns a copy of the part of
648 LIST up to but not including SUBLIST. For example, `(ldiff x
649 (cddr x))' returns the first two elements of the list `x'. The
650 result is a copy; the original LIST is not modified. If SUBLIST
651 is not a sublist of LIST, a copy of the entire LIST is returned.
653 - Function: copy-list list
654 This function returns a copy of the list LIST. It copies dotted
655 lists like `(1 2 . 3)' correctly.
657 - Function: copy-tree x &optional vecp
658 This function returns a copy of the tree of cons cells X. Unlike
659 `copy-sequence' (and its alias `copy-list'), which copies only
660 along the `cdr' direction, this function copies (recursively)
661 along both the `car' and the `cdr' directions. If X is not a cons
662 cell, the function simply returns X unchanged. If the optional
663 VECP argument is true, this function copies vectors (recursively)
664 as well as cons cells.
666 - Function: tree-equal x y &key :test :test-not :key
667 This function compares two trees of cons cells. If X and Y are
668 both cons cells, their `car's and `cdr's are compared recursively.
669 If neither X nor Y is a cons cell, they are compared by `eql', or
670 according to the specified test. The `:key' function, if
671 specified, is applied to the elements of both trees. *Note
675 File: cl.info, Node: Substitution of Expressions, Next: Lists as Sets, Prev: List Functions, Up: Lists
677 Substitution of Expressions
678 ===========================
680 These functions substitute elements throughout a tree of cons cells.
681 (*Note Sequence Functions::, for the `substitute' function, which works
682 on just the top-level elements of a list.)
684 - Function: subst new old tree &key :test :test-not :key
685 This function substitutes occurrences of OLD with NEW in TREE, a
686 tree of cons cells. It returns a substituted tree, which will be
687 a copy except that it may share storage with the argument TREE in
688 parts where no substitutions occurred. The original TREE is not
689 modified. This function recurses on, and compares against OLD,
690 both `car's and `cdr's of the component cons cells. If OLD is
691 itself a cons cell, then matching cells in the tree are
692 substituted as usual without recursively substituting in that
693 cell. Comparisons with OLD are done according to the specified
694 test (`eql' by default). The `:key' function is applied to the
695 elements of the tree but not to OLD.
697 - Function: nsubst new old tree &key :test :test-not :key
698 This function is like `subst', except that it works by destructive
699 modification (by `setcar' or `setcdr') rather than copying.
701 The `subst-if', `subst-if-not', `nsubst-if', and `nsubst-if-not'
702 functions are defined similarly.
704 - Function: sublis alist tree &key :test :test-not :key
705 This function is like `subst', except that it takes an association
706 list ALIST of OLD-NEW pairs. Each element of the tree (after
707 applying the `:key' function, if any), is compared with the `car's
708 of ALIST; if it matches, it is replaced by the corresponding `cdr'.
710 - Function: nsublis alist tree &key :test :test-not :key
711 This is a destructive version of `sublis'.
714 File: cl.info, Node: Lists as Sets, Next: Association Lists, Prev: Substitution of Expressions, Up: Lists
719 These functions perform operations on lists which represent sets of
722 - Function: member item list
723 This MacLisp-compatible function searches LIST for an element
724 which is `equal' to ITEM. The `member' function is built-in to
725 Emacs 19; this package defines it equivalently in Emacs 18. See
726 the following function for a Common-Lisp compatible version.
728 - Function: member* item list &key :test :test-not :key
729 This function searches LIST for an element matching ITEM. If a
730 match is found, it returns the cons cell whose `car' was the
731 matching element. Otherwise, it returns `nil'. Elements are
732 compared by `eql' by default; you can use the `:test',
733 `:test-not', and `:key' arguments to modify this behavior. *Note
736 Note that this function's name is suffixed by `*' to avoid the
737 incompatible `member' function defined in Emacs 19. (That
738 function uses `equal' for comparisons; it is equivalent to
739 `(member* ITEM LIST :test 'equal)'.)
741 The `member-if' and `member-if-not' functions analogously search for
742 elements which satisfy a given predicate.
744 - Function: tailp sublist list
745 This function returns `t' if SUBLIST is a sublist of LIST, i.e.,
746 if SUBLIST is `eql' to LIST or to any of its `cdr's.
748 - Function: adjoin item list &key :test :test-not :key
749 This function conses ITEM onto the front of LIST, like `(cons ITEM
750 LIST)', but only if ITEM is not already present on the list (as
751 determined by `member*'). If a `:key' argument is specified, it
752 is applied to ITEM as well as to the elements of LIST during the
753 search, on the reasoning that ITEM is "about" to become part of
756 - Function: union list1 list2 &key :test :test-not :key
757 This function combines two lists which represent sets of items,
758 returning a list that represents the union of those two sets. The
759 result list will contain all items which appear in LIST1 or LIST2,
760 and no others. If an item appears in both LIST1 and LIST2 it will
761 be copied only once. If an item is duplicated in LIST1 or LIST2,
762 it is undefined whether or not that duplication will survive in the
763 result list. The order of elements in the result list is also
766 - Function: nunion list1 list2 &key :test :test-not :key
767 This is a destructive version of `union'; rather than copying, it
768 tries to reuse the storage of the argument lists if possible.
770 - Function: intersection list1 list2 &key :test :test-not :key
771 This function computes the intersection of the sets represented by
772 LIST1 and LIST2. It returns the list of items which appear in
773 both LIST1 and LIST2.
775 - Function: nintersection list1 list2 &key :test :test-not :key
776 This is a destructive version of `intersection'. It tries to
777 reuse storage of LIST1 rather than copying. It does _not_ reuse
778 the storage of LIST2.
780 - Function: set-difference list1 list2 &key :test :test-not :key
781 This function computes the "set difference" of LIST1 and LIST2,
782 i.e., the set of elements that appear in LIST1 but _not_ in LIST2.
784 - Function: nset-difference list1 list2 &key :test :test-not :key
785 This is a destructive `set-difference', which will try to reuse
788 - Function: set-exclusive-or list1 list2 &key :test :test-not :key
789 This function computes the "set exclusive or" of LIST1 and LIST2,
790 i.e., the set of elements that appear in exactly one of LIST1 and
793 - Function: nset-exclusive-or list1 list2 &key :test :test-not :key
794 This is a destructive `set-exclusive-or', which will try to reuse
795 LIST1 and LIST2 if possible.
797 - Function: subsetp list1 list2 &key :test :test-not :key
798 This function checks whether LIST1 represents a subset of LIST2,
799 i.e., whether every element of LIST1 also appears in LIST2.
802 File: cl.info, Node: Association Lists, Prev: Lists as Sets, Up: Lists
807 An "association list" is a list representing a mapping from one set of
808 values to another; any list whose elements are cons cells is an
811 - Function: assoc* item a-list &key :test :test-not :key
812 This function searches the association list A-LIST for an element
813 whose `car' matches (in the sense of `:test', `:test-not', and
814 `:key', or by comparison with `eql') a given ITEM. It returns the
815 matching element, if any, otherwise `nil'. It ignores elements of
816 A-LIST which are not cons cells. (This corresponds to the
817 behavior of `assq' and `assoc' in Emacs Lisp; Common Lisp's
818 `assoc' ignores `nil's but considers any other non-cons elements
819 of A-LIST to be an error.)
821 - Function: rassoc* item a-list &key :test :test-not :key
822 This function searches for an element whose `cdr' matches ITEM.
823 If A-LIST represents a mapping, this applies the inverse of the
826 - Function: rassoc item a-list
827 This function searches like `rassoc*' with a `:test' argument of
828 `equal'. It is analogous to Emacs Lisp's standard `assoc'
829 function, which derives from the MacLisp rather than the Common
832 The `assoc-if', `assoc-if-not', `rassoc-if', and `rassoc-if-not'
833 functions are defined similarly.
835 Two simple functions for constructing association lists are:
837 - Function: acons key value alist
838 This is equivalent to `(cons (cons KEY VALUE) ALIST)'.
840 - Function: pairlis keys values &optional alist
841 This is equivalent to `(nconc (mapcar* 'cons KEYS VALUES) ALIST)'.
844 File: cl.info, Node: Hash Tables, Next: Structures, Prev: Lists, Up: Top
849 Hash tables are now implemented directly in the C code and documented in
850 *Note Hash Tables: (lispref)Hash Tables.