Mercurial > hg > xemacs-beta
annotate man/lispref/lists.texi @ 5353:38e24b8be4ea
Improve the lexical scoping in #'block, #'return-from.
lisp/ChangeLog addition:
2011-02-07 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el:
* bytecomp.el (byte-compile-initial-macro-environment):
Shadow `block', `return-from' here, we implement them differently
when byte-compiling.
* bytecomp.el (byte-compile-active-blocks): New.
* bytecomp.el (byte-compile-block-1): New.
* bytecomp.el (byte-compile-return-from-1): New.
* bytecomp.el (return-from-1): New.
* bytecomp.el (block-1): New.
These are two aliases that exist to have their own associated
byte-compile functions, which functions implement `block' and
`return-from'.
* cl-extra.el (cl-macroexpand-all):
Fix a bug here when macros in the environment have been compiled.
* cl-macs.el (block):
* cl-macs.el (return):
* cl-macs.el (return-from):
Be more careful about lexical scope in these macros.
* cl.el:
* cl.el ('cl-block-wrapper): Removed.
* cl.el ('cl-block-throw): Removed.
These aren't needed in code generated by this XEmacs. They
shouldn't be needed in code generated by XEmacs 21.4, but if it
turns out the packages do need them, we can put them back.
2011-01-30 Mike Sperber <mike@xemacs.org>
* font-lock.el (font-lock-fontify-pending-extents): Don't fail if
`font-lock-mode' is unset, which can happen in the middle of
`revert-buffer'.
2011-01-23 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (delete):
* cl-macs.el (delq):
* cl-macs.el (remove):
* cl-macs.el (remq):
Don't use the compiler macro if these functions were given the
wrong number of arguments, as happens in lisp-tests.el.
* cl-seq.el (remove, remq): Removed.
I added these to subr.el, and forgot to remove them from here.
2011-01-22 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-setq, byte-compile-set):
Remove kludge allowing keywords' values to be set, all the code
that does that is gone.
* cl-compat.el (elt-satisfies-test-p):
* faces.el (set-face-parent):
* faces.el (face-doc-string):
* gtk-font-menu.el:
* gtk-font-menu.el (gtk-reset-device-font-menus):
* msw-font-menu.el:
* msw-font-menu.el (mswindows-reset-device-font-menus):
* package-get.el (package-get-installedp):
* select.el (select-convert-from-image-data):
* sound.el:
* sound.el (load-sound-file):
* x-font-menu.el (x-reset-device-font-menus-core):
Don't quote keywords, they're self-quoting, and the
win from backward-compatibility is sufficiently small now that the
style problem overrides it.
2011-01-22 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (block, return-from): Require that NAME be a symbol
in these macros, as always documented in the #'block docstring and
as required by Common Lisp.
* descr-text.el (unidata-initialize-unihan-database):
Correct the use of non-symbols in #'block and #'return-from in
this function.
2011-01-15 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (concatenate): Accept more complicated TYPEs in this
function, handing the sequences over to #'coerce if we don't
understand them here.
* cl-macs.el (inline): Don't proclaim #'concatenate as inline, its
compiler macro is more useful than doing that.
2011-01-11 Aidan Kehoe <kehoea@parhasard.net>
* subr.el (delete, delq, remove, remq): Move #'remove, #'remq
here, they don't belong in cl-seq.el; move #'delete, #'delq here
from fns.c, implement them in terms of #'delete*, allowing support
for sequences generally.
* update-elc.el (do-autoload-commands): Use #'delete*, not #'delq
here, now the latter's no longer dumped.
* cl-macs.el (delete, delq): Add compiler macros transforming
#'delete and #'delq to #'delete* calls.
2011-01-10 Aidan Kehoe <kehoea@parhasard.net>
* dialog.el (make-dialog-box): Correct a misplaced parenthesis
here, thank you Mats Lidell in 87zkr9gqrh.fsf@mail.contactor.se !
2011-01-02 Aidan Kehoe <kehoea@parhasard.net>
* dialog.el (make-dialog-box):
* list-mode.el (display-completion-list):
These functions used to use cl-parsing-keywords; change them to
use defun* instead, fixing the build. (Not sure what led to me
not including this change in d1b17a33450b!)
2011-01-02 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (define-star-compiler-macros):
Make sure the form has ITEM and LIST specified before attempting
to change to calls with explicit tests; necessary for some tests
in lisp-tests.el to compile correctly.
(stable-union, stable-intersection): Add compiler macros for these
functions, in the same way we do for most of the other functions
in cl-seq.el.
2011-01-01 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (dolist, dotimes, do-symbols, macrolet)
(symbol-macrolet):
Define these macros with defmacro* instead of parsing the argument
list by hand, for the sake of style and readability; use backquote
where appropriate, instead of calling #'list and and friends, for
the same reason.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* x-misc.el (device-x-display):
Provide this function, documented in the Lispref for years, but
not existing previously. Thank you Julian Bradfield, thank you
Jeff Mincy.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* cl-seq.el:
Move the heavy lifting from this file to C. Dump the
cl-parsing-keywords macro, but don't use defun* for the functions
we define that do take keywords, dynamic scope lossage makes that
not practical.
* subr.el (sort, fillarray): Move these aliases here.
(map-plist): #'nsublis is now built-in, but at this point #'eql
isn't necessarily available as a test; use #'eq.
* obsolete.el (cl-delete-duplicates): Make this available for old
compiler macros and old code.
(memql): Document that this is equivalent to #'member*, and worse.
* cl.el (adjoin, subst): Removed. These are in C.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* simple.el (assoc-ignore-case): Remove a duplicate definition of
this function (it's already in subr.el).
* iso8859-1.el (char-width):
On non-Mule, make this function equivalent to that produced by
(constantly 1), but preserve its docstring.
* subr.el (subst-char-in-string): Define this in terms of
#'substitute, #'nsubstitute.
(string-width): Define this using #'reduce and #'char-width.
(char-width): Give this a simpler definition, it makes far more
sense to check for mule at load time and redefine, as we do in
iso8859-1.el.
(store-substring): Implement this in terms of #'replace, now
#'replace is cheap.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* update-elc.el (lisp-files-needed-for-byte-compilation)
(lisp-files-needing-early-byte-compilation):
cl-macs belongs in the former, not the latter, it is as
fundamental as bytecomp.el.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* cl.el:
Provde the Common Lisp program-error, type-error as error
symbols. This doesn't nearly go far enough for anyone using the
Common Lisp errors.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (delete-duplicates):
If the form has an incorrect number of arguments, don't attempt a
compiler macroexpansion.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (cl-safe-expr-p):
Forms that start with the symbol lambda are also safe.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (= < > <= >=):
For these functions' compiler macros, the optimisation is safe
even if the first and the last arguments have side effects, since
they're only used the once.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (inline-side-effect-free-compiler-macros):
Unroll a loop here at macro-expansion time, so these compiler
macros are compiled. Use #'eql instead of #'eq in a couple of
places for better style.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (notany, notevery): Avoid some dynamic scope
stupidity with local variable names in these functions, when they
weren't prefixed with cl-; go into some more detail in the doc
strings.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (side-effect-free-fns): #'remove, #'remq are
free of side-effects.
(side-effect-and-error-free-fns):
Drop dot, dot-marker from the list.
2010-11-17 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (coerce):
In the argument list, name the first argument OBJECT, not X; the
former name was always used in the doc string and is clearer.
Handle vector type specifications which include the length of the
target sequence, error if there's a mismatch.
* cl-macs.el (cl-make-type-test): Handle type specifications
starting with the symbol 'eql.
2010-11-14 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (eql): Don't remove the byte-compile property of this
symbol. That was necessary to override a bug in bytecomp.el where
#'eql was confused with #'eq, which bug we no longer have.
If neither expression is constant, don't attempt to handle the
expression in this compiler macro, leave it to byte-compile-eql,
which produces better code anyway.
* bytecomp.el (eq): #'eql is not the function associated with the
byte-eq byte code.
(byte-compile-eql): Add an explicit compile method for this
function, for cases where the cl-macs compiler macro hasn't
reduced it to #'eq or #'equal.
2010-10-25 Aidan Kehoe <kehoea@parhasard.net>
Add compiler macros and compilation sanity-checking for various
functions that take keywords.
* byte-optimize.el (side-effect-free-fns): #'symbol-value is
side-effect free and not error free.
* bytecomp.el (byte-compile-normal-call): Check keyword argument
lists for sanity; store information about the positions where
keyword arguments start using the new byte-compile-keyword-start
property.
* cl-macs.el (cl-const-expr-val): Take a new optional argument,
cl-not-constant, defaulting to nil, in this function; return it if
the expression is not constant.
(cl-non-fixnum-number-p): Make this into a separate function, we
want to pass it to #'every.
(eql): Use it.
(define-star-compiler-macros): Use the same code to generate the
member*, assoc* and rassoc* compiler macros; special-case some
code in #'add-to-list in subr.el.
(remove, remq): Add compiler macros for these two functions, in
preparation for #'remove being in C.
(define-foo-if-compiler-macros): Transform (remove-if-not ...) calls to
(remove ... :if-not) at compile time, which will be a real win
once the latter is in C.
(define-substitute-if-compiler-macros)
(define-subst-if-compiler-macros): Similarly for these functions.
(delete-duplicates): Change this compiler macro to use
#'plists-equal; if we don't have information about the type of
SEQUENCE at compile time, don't bother attempting to inline the
call, the function will be in C soon enough.
(equalp): Remove an old commented-out compiler macro for this, if
we want to see it it's in version control.
(subst-char-in-string): Transform this to a call to nsubstitute or
nsubstitute, if that is appropriate.
* cl.el (ldiff): Don't call setf here, this makes for a load-time
dependency problem in cl-macs.el
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* term/vt100.el:
Refer to XEmacs, not GNU Emacs, in permissions.
* term/bg-mouse.el:
* term/sup-mouse.el:
Put copyright notice in canonical "Copyright DATE AUTHOR" form.
Refer to XEmacs, not GNU Emacs, in permissions.
* site-load.el:
Add permission boilerplate.
* mule/canna-leim.el:
* alist.el:
Refer to XEmacs, not APEL/this program, in permissions.
* mule/canna-leim.el:
Remove my copyright, I've assigned it to the FSF.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* gtk.el:
* gtk-widget-accessors.el:
* gtk-package.el:
* gtk-marshal.el:
* gtk-compose.el:
* gnome.el:
Add copyright notice based on internal evidence.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* easymenu.el: Add reference to COPYING to permission notice.
* gutter.el:
* gutter-items.el:
* menubar-items.el:
Fix typo "Xmacs" in permissions notice.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* auto-save.el:
* font.el:
* fontconfig.el:
* mule/kinsoku.el:
Add "part of XEmacs" text to permission notice.
2010-10-14 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (side-effect-free-fns):
* cl-macs.el (remf, getf):
* cl-extra.el (tailp, cl-set-getf, cl-do-remf):
* cl.el (ldiff, endp):
Tighten up Common Lisp compatibility for #'ldiff, #'endp, #'tailp;
add circularity checking for the first two.
#'cl-set-getf and #'cl-do-remf were Lisp implementations of
#'plist-put and #'plist-remprop; change the names to aliases,
changes the macros that use them to using #'plist-put and
#'plist-remprop directly.
2010-10-12 Aidan Kehoe <kehoea@parhasard.net>
* abbrev.el (fundamental-mode-abbrev-table, global-abbrev-table):
Create both these abbrev tables using the usual
#'define-abbrev-table calls, rather than attempting to
special-case them.
* cl-extra.el: Force cl-macs to be loaded here, if cl-extra.el is
being loaded interpreted. Previously other, later files would
redundantly call (load "cl-macs") when interpreted, it's more
reasonable to do it here, once.
* cmdloop.el (read-quoted-char-radix): Use defcustom here, we
don't have any dump-order dependencies that would prevent that.
* custom.el (eval-when-compile): Don't load cl-macs when
interpreted or when byte-compiling, rely on cl-extra.el in the
former case and the appropriate entry in bytecomp-load-hook in the
latter. Get rid of custom-declare-variable-list, we have no
dump-time dependencies that would require it.
* faces.el (eval-when-compile): Don't load cl-macs when
interpreted or when byte-compiling.
* packages.el: Remove some inaccurate comments.
* post-gc.el (cleanup-simple-finalizers): Use #'delete-if-not
here, now the order of preloaded-file-list has been changed to
make it available.
* subr.el (custom-declare-variable-list): Remove. No need for it.
Also remove a stub define-abbrev-table from this file, given the
current order of preloaded-file-list there's no need for it.
2010-10-10 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-constp) Forms quoted with FUNCTION are
also constant.
(byte-compile-initial-macro-environment): In #'the, if FORM is
constant and does not match TYPE, warn at byte-compile time.
2010-10-10 Aidan Kehoe <kehoea@parhasard.net>
* backquote.el (bq-vector-contents, bq-list*): Remove; the former
is equivalent to (append VECTOR nil), the latter to (list* ...).
(bq-process-2): Use (append VECTOR nil) instead of using
#'bq-vector-contents to convert to a list.
(bq-process-1): Now we use list* instead of bq-list
* subr.el (list*): Moved from cl.el, since it is now required to
be available the first time a backquoted form is encountered.
* cl.el (list*): Move to subr.el.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* test-harness.el (Check-Message):
Add an omitted comma here, thank you the buildbot.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* hash-table.el (hash-table-key-list, hash-table-value-list)
(hash-table-key-value-alist, hash-table-key-value-plist):
Remove some useless #'nreverse calls in these files; our hash
tables have no order, it's not helpful to pretend they do.
* behavior.el (read-behavior):
Do the same in this file, in some code evidently copied from
hash-table.el.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* info.el (Info-insert-dir):
* format.el (format-deannotate-region):
* files.el (cd, save-buffers-kill-emacs):
Use #'some, #'every and related functions for applying boolean
operations to lists, instead of rolling our own ones that cons and
don't short-circuit.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-initial-macro-environment):
* cl-macs.el (the):
Rephrase the docstring, make its implementation when compiling
files a little nicer.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* descr-text.el (unidata-initialize-unicodedata-database)
(unidata-initialize-unihan-database, describe-char-unicode-data)
(describe-char-unicode-data):
Wrap calls to the database functions with (with-fboundp ...),
avoiding byte compile warnings on builds without support for the
database functions.
(describe-char): (reduce #'max ...), not (apply #'max ...), no
need to cons needlessly.
(describe-char): Remove a redundant lambda wrapping
#'extent-properties.
(describe-char-unicode-data): Call #'nsubst when replacing "" with
nil in the result of #'split-string, instead of consing inside
mapcar.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* x-faces.el (x-available-font-sizes):
* specifier.el (let-specifier):
* package-ui.el (pui-add-required-packages):
* msw-faces.el (mswindows-available-font-sizes):
* modeline.el (modeline-minor-mode-menu):
* minibuf.el (minibuf-directory-files):
Replace the O2N (delq nil (mapcar (lambda (W) (and X Y)) Z)) with
the ON (mapcan (lambda (W) (and X (list Y))) Z) in these files.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (= < > <= >=):
When these functions are handed more than two arguments, and those
arguments have no side effects, transform to a series of two
argument calls, avoiding funcall in the byte-compiled code.
* mule/mule-cmds.el (finish-set-language-environment):
Take advantage of this change in a function called 256 times at
startup.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-function-form, byte-compile-quote)
(byte-compile-quote-form):
Warn at compile time, and error at runtime, if a (quote ...) or a
(function ...) form attempts to quote more than one object.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (byte-optimize-apply): Transform (apply 'nconc
(mapcar ...)) to (mapcan ...); warn about use of the first idiom.
* update-elc.el (do-autoload-commands):
* packages.el (packages-find-package-library-path):
* frame.el (frame-list):
* extents.el (extent-descendants):
* etags.el (buffer-tag-table-files):
* dumped-lisp.el (preloaded-file-list):
* device.el (device-list):
* bytecomp-runtime.el (proclaim-inline, proclaim-notinline)
Use #'mapcan, not (apply #'nconc (mapcar ...) in all these files.
* bytecomp-runtime.el (eval-when-compile, eval-and-compile):
In passing, mention that these macros also evaluate the body when
interpreted.
tests/ChangeLog addition:
2011-02-07 Aidan Kehoe <kehoea@parhasard.net>
* automated/lisp-tests.el:
Test lexical scope for `block', `return-from'; add a
Known-Bug-Expect-Failure for a contorted example that fails when
byte-compiled.
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Mon, 07 Feb 2011 12:01:24 +0000 |
| parents | 9f738305f80f |
| children | f5a5501814f5 |
| rev | line source |
|---|---|
| 428 | 1 @c -*-texinfo-*- |
| 2 @c This is part of the XEmacs Lisp Reference Manual. | |
| 444 | 3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc. |
| 428 | 4 @c See the file lispref.texi for copying conditions. |
| 5 @setfilename ../../info/lists.info | |
| 6 @node Lists, Sequences Arrays Vectors, Strings and Characters, Top | |
| 7 @chapter Lists | |
| 8 @cindex list | |
| 9 @cindex element (of list) | |
| 10 | |
| 11 A @dfn{list} represents a sequence of zero or more elements (which may | |
| 12 be any Lisp objects). The important difference between lists and | |
| 13 vectors is that two or more lists can share part of their structure; in | |
| 14 addition, you can insert or delete elements in a list without copying | |
| 15 the whole list. | |
| 16 | |
| 17 @menu | |
| 18 * Cons Cells:: How lists are made out of cons cells. | |
| 19 * Lists as Boxes:: Graphical notation to explain lists. | |
| 20 * List-related Predicates:: Is this object a list? Comparing two lists. | |
| 21 * List Elements:: Extracting the pieces of a list. | |
| 22 * Building Lists:: Creating list structure. | |
| 23 * Modifying Lists:: Storing new pieces into an existing list. | |
| 24 * Sets And Lists:: A list can represent a finite mathematical set. | |
| 25 * Association Lists:: A list can represent a finite relation or mapping. | |
| 26 * Property Lists:: A different way to represent a finite mapping. | |
| 27 * Weak Lists:: A list with special garbage-collection behavior. | |
| 28 @end menu | |
| 29 | |
| 30 @node Cons Cells | |
| 31 @section Lists and Cons Cells | |
| 32 @cindex lists and cons cells | |
| 33 @cindex @code{nil} and lists | |
| 34 | |
| 35 Lists in Lisp are not a primitive data type; they are built up from | |
| 36 @dfn{cons cells}. A cons cell is a data object that represents an | |
| 37 ordered pair. It records two Lisp objects, one labeled as the @sc{car}, | |
| 38 and the other labeled as the @sc{cdr}. These names are traditional; see | |
| 39 @ref{Cons Cell Type}. @sc{cdr} is pronounced ``could-er.'' | |
| 40 | |
| 41 A list is a series of cons cells chained together, one cons cell per | |
| 42 element of the list. By convention, the @sc{car}s of the cons cells are | |
| 43 the elements of the list, and the @sc{cdr}s are used to chain the list: | |
| 44 the @sc{cdr} of each cons cell is the following cons cell. The @sc{cdr} | |
| 45 of the last cons cell is @code{nil}. This asymmetry between the | |
| 46 @sc{car} and the @sc{cdr} is entirely a matter of convention; at the | |
| 47 level of cons cells, the @sc{car} and @sc{cdr} slots have the same | |
| 48 characteristics. | |
| 49 | |
| 50 @cindex list structure | |
| 51 Because most cons cells are used as part of lists, the phrase | |
| 52 @dfn{list structure} has come to mean any structure made out of cons | |
| 53 cells. | |
| 54 | |
| 55 The symbol @code{nil} is considered a list as well as a symbol; it is | |
| 56 the list with no elements. For convenience, the symbol @code{nil} is | |
| 57 considered to have @code{nil} as its @sc{cdr} (and also as its | |
| 58 @sc{car}). | |
| 59 | |
| 60 The @sc{cdr} of any nonempty list @var{l} is a list containing all the | |
| 61 elements of @var{l} except the first. | |
| 62 | |
| 63 @node Lists as Boxes | |
| 64 @section Lists as Linked Pairs of Boxes | |
| 65 @cindex box representation for lists | |
| 66 @cindex lists represented as boxes | |
| 67 @cindex cons cell as box | |
| 68 | |
| 69 A cons cell can be illustrated as a pair of boxes. The first box | |
| 70 represents the @sc{car} and the second box represents the @sc{cdr}. | |
| 71 Here is an illustration of the two-element list, @code{(tulip lily)}, | |
| 72 made from two cons cells: | |
| 73 | |
| 74 @example | |
| 75 @group | |
| 76 --------------- --------------- | |
| 77 | car | cdr | | car | cdr | | |
| 78 | tulip | o---------->| lily | nil | | |
| 79 | | | | | | | |
| 80 --------------- --------------- | |
| 81 @end group | |
| 82 @end example | |
| 83 | |
| 84 Each pair of boxes represents a cons cell. Each box ``refers to'', | |
| 85 ``points to'' or ``contains'' a Lisp object. (These terms are | |
| 86 synonymous.) The first box, which is the @sc{car} of the first cons | |
| 87 cell, contains the symbol @code{tulip}. The arrow from the @sc{cdr} of | |
| 88 the first cons cell to the second cons cell indicates that the @sc{cdr} | |
| 89 of the first cons cell points to the second cons cell. | |
| 90 | |
| 91 The same list can be illustrated in a different sort of box notation | |
| 92 like this: | |
| 93 | |
| 94 @example | |
| 95 @group | |
| 96 ___ ___ ___ ___ | |
| 97 |___|___|--> |___|___|--> nil | |
| 98 | | | |
| 99 | | | |
| 100 --> tulip --> lily | |
| 101 @end group | |
| 102 @end example | |
| 103 | |
| 104 Here is a more complex illustration, showing the three-element list, | |
| 105 @code{((pine needles) oak maple)}, the first element of which is a | |
| 106 two-element list: | |
| 107 | |
| 108 @example | |
| 109 @group | |
| 110 ___ ___ ___ ___ ___ ___ | |
| 111 |___|___|--> |___|___|--> |___|___|--> nil | |
| 112 | | | | |
| 113 | | | | |
| 114 | --> oak --> maple | |
| 115 | | |
| 116 | ___ ___ ___ ___ | |
| 117 --> |___|___|--> |___|___|--> nil | |
| 118 | | | |
| 119 | | | |
| 120 --> pine --> needles | |
| 121 @end group | |
| 122 @end example | |
| 123 | |
| 124 The same list represented in the first box notation looks like this: | |
| 125 | |
| 126 @example | |
| 127 @group | |
| 128 -------------- -------------- -------------- | |
| 129 | car | cdr | | car | cdr | | car | cdr | | |
| 130 | o | o------->| oak | o------->| maple | nil | | |
| 131 | | | | | | | | | | | |
| 132 -- | --------- -------------- -------------- | |
| 133 | | |
| 134 | | |
| 135 | -------------- ---------------- | |
| 136 | | car | cdr | | car | cdr | | |
| 137 ------>| pine | o------->| needles | nil | | |
| 138 | | | | | | | |
| 139 -------------- ---------------- | |
| 140 @end group | |
| 141 @end example | |
| 142 | |
| 143 @xref{Cons Cell Type}, for the read and print syntax of cons cells and | |
| 144 lists, and for more ``box and arrow'' illustrations of lists. | |
| 145 | |
| 146 @node List-related Predicates | |
| 147 @section Predicates on Lists | |
| 148 | |
| 149 The following predicates test whether a Lisp object is an atom, is a | |
| 150 cons cell or is a list, or whether it is the distinguished object | |
| 151 @code{nil}. (Many of these predicates can be defined in terms of the | |
| 152 others, but they are used so often that it is worth having all of them.) | |
| 153 | |
| 154 @defun consp object | |
| 155 This function returns @code{t} if @var{object} is a cons cell, @code{nil} | |
| 156 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list. | |
| 157 @end defun | |
| 158 | |
| 159 @defun atom object | |
| 160 @cindex atoms | |
| 161 This function returns @code{t} if @var{object} is an atom, @code{nil} | |
| 162 otherwise. All objects except cons cells are atoms. The symbol | |
| 163 @code{nil} is an atom and is also a list; it is the only Lisp object | |
| 164 that is both. | |
| 165 | |
| 166 @example | |
| 167 (atom @var{object}) @equiv{} (not (consp @var{object})) | |
| 168 @end example | |
| 169 @end defun | |
| 170 | |
| 171 @defun listp object | |
| 172 This function returns @code{t} if @var{object} is a cons cell or | |
| 1549 | 173 @code{nil}. Otherwise, it returns @code{nil}. @code{true-list-p} is |
| 174 slower, but in some circumstances it is more appropriate. | |
| 428 | 175 |
| 176 @example | |
| 177 @group | |
| 178 (listp '(1)) | |
| 179 @result{} t | |
| 180 @end group | |
| 181 @group | |
| 182 (listp '()) | |
| 183 @result{} t | |
| 184 @end group | |
| 185 @end example | |
| 186 @end defun | |
| 187 | |
| 188 @defun nlistp object | |
| 189 This function is the opposite of @code{listp}: it returns @code{t} if | |
| 190 @var{object} is not a list. Otherwise, it returns @code{nil}. | |
| 191 | |
| 192 @example | |
| 193 (listp @var{object}) @equiv{} (not (nlistp @var{object})) | |
| 194 @end example | |
| 195 @end defun | |
| 196 | |
| 1549 | 197 @defun true-list-p object |
| 198 This function returns @code{t} if @var{object} is an acyclic, | |
| 199 @code{nil}-terminated (ie, not dotted), list. Otherwise it returns | |
| 200 @code{nil}. @code{listp} is faster. | |
| 1554 | 201 @end defun |
| 1549 | 202 |
| 428 | 203 @defun null object |
| 204 This function returns @code{t} if @var{object} is @code{nil}, and | |
| 205 returns @code{nil} otherwise. This function is identical to @code{not}, | |
| 206 but as a matter of clarity we use @code{null} when @var{object} is | |
| 207 considered a list and @code{not} when it is considered a truth value | |
| 208 (see @code{not} in @ref{Combining Conditions}). | |
| 209 | |
| 210 @example | |
| 211 @group | |
| 212 (null '(1)) | |
| 213 @result{} nil | |
| 214 @end group | |
| 215 @group | |
| 216 (null '()) | |
| 217 @result{} t | |
| 218 @end group | |
| 219 @end example | |
| 220 @end defun | |
| 221 | |
| 222 @need 2000 | |
| 223 | |
| 224 @node List Elements | |
| 225 @section Accessing Elements of Lists | |
| 226 @cindex list elements | |
| 227 | |
| 228 @defun car cons-cell | |
| 229 This function returns the value pointed to by the first pointer of the | |
| 230 cons cell @var{cons-cell}. Expressed another way, this function | |
| 231 returns the @sc{car} of @var{cons-cell}. | |
| 232 | |
| 233 As a special case, if @var{cons-cell} is @code{nil}, then @code{car} | |
| 234 is defined to return @code{nil}; therefore, any list is a valid argument | |
| 235 for @code{car}. An error is signaled if the argument is not a cons cell | |
| 236 or @code{nil}. | |
| 237 | |
| 238 @example | |
| 239 @group | |
| 240 (car '(a b c)) | |
| 241 @result{} a | |
| 242 @end group | |
| 243 @group | |
| 244 (car '()) | |
| 245 @result{} nil | |
| 246 @end group | |
| 247 @end example | |
| 248 @end defun | |
| 249 | |
| 250 @defun cdr cons-cell | |
| 251 This function returns the value pointed to by the second pointer of | |
| 252 the cons cell @var{cons-cell}. Expressed another way, this function | |
| 253 returns the @sc{cdr} of @var{cons-cell}. | |
| 254 | |
| 255 As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr} | |
| 256 is defined to return @code{nil}; therefore, any list is a valid argument | |
| 257 for @code{cdr}. An error is signaled if the argument is not a cons cell | |
| 258 or @code{nil}. | |
| 259 | |
| 260 @example | |
| 261 @group | |
| 262 (cdr '(a b c)) | |
| 263 @result{} (b c) | |
| 264 @end group | |
| 265 @group | |
| 266 (cdr '()) | |
| 267 @result{} nil | |
| 268 @end group | |
| 269 @end example | |
| 270 @end defun | |
| 271 | |
| 272 @defun car-safe object | |
| 273 This function lets you take the @sc{car} of a cons cell while avoiding | |
| 274 errors for other data types. It returns the @sc{car} of @var{object} if | |
| 275 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast | |
| 276 to @code{car}, which signals an error if @var{object} is not a list. | |
| 277 | |
| 278 @example | |
| 279 @group | |
| 280 (car-safe @var{object}) | |
| 281 @equiv{} | |
| 282 (let ((x @var{object})) | |
| 283 (if (consp x) | |
| 284 (car x) | |
| 285 nil)) | |
| 286 @end group | |
| 287 @end example | |
| 288 @end defun | |
| 289 | |
| 290 @defun cdr-safe object | |
| 291 This function lets you take the @sc{cdr} of a cons cell while | |
| 292 avoiding errors for other data types. It returns the @sc{cdr} of | |
| 293 @var{object} if @var{object} is a cons cell, @code{nil} otherwise. | |
| 294 This is in contrast to @code{cdr}, which signals an error if | |
| 295 @var{object} is not a list. | |
| 296 | |
| 297 @example | |
| 298 @group | |
| 299 (cdr-safe @var{object}) | |
| 300 @equiv{} | |
| 301 (let ((x @var{object})) | |
| 302 (if (consp x) | |
| 303 (cdr x) | |
| 304 nil)) | |
| 305 @end group | |
| 306 @end example | |
| 307 @end defun | |
| 308 | |
| 309 @defun nth n list | |
| 310 This function returns the @var{n}th element of @var{list}. Elements | |
| 311 are numbered starting with zero, so the @sc{car} of @var{list} is | |
| 312 element number zero. If the length of @var{list} is @var{n} or less, | |
| 313 the value is @code{nil}. | |
| 314 | |
| 315 If @var{n} is negative, @code{nth} returns the first element of | |
| 316 @var{list}. | |
| 317 | |
| 318 @example | |
| 319 @group | |
| 320 (nth 2 '(1 2 3 4)) | |
| 321 @result{} 3 | |
| 322 @end group | |
| 323 @group | |
| 324 (nth 10 '(1 2 3 4)) | |
| 325 @result{} nil | |
| 326 @end group | |
| 327 @group | |
| 328 (nth -3 '(1 2 3 4)) | |
| 329 @result{} 1 | |
| 330 | |
| 331 (nth n x) @equiv{} (car (nthcdr n x)) | |
| 332 @end group | |
| 333 @end example | |
| 334 @end defun | |
| 335 | |
| 336 @defun nthcdr n list | |
| 337 This function returns the @var{n}th @sc{cdr} of @var{list}. In other | |
| 338 words, it removes the first @var{n} links of @var{list} and returns | |
| 339 what follows. | |
| 340 | |
| 341 If @var{n} is zero or negative, @code{nthcdr} returns all of | |
| 342 @var{list}. If the length of @var{list} is @var{n} or less, | |
| 343 @code{nthcdr} returns @code{nil}. | |
| 344 | |
| 345 @example | |
| 346 @group | |
| 347 (nthcdr 1 '(1 2 3 4)) | |
| 348 @result{} (2 3 4) | |
| 349 @end group | |
| 350 @group | |
| 351 (nthcdr 10 '(1 2 3 4)) | |
| 352 @result{} nil | |
| 353 @end group | |
| 354 @group | |
| 355 (nthcdr -3 '(1 2 3 4)) | |
| 356 @result{} (1 2 3 4) | |
| 357 @end group | |
| 358 @end example | |
| 359 @end defun | |
| 360 | |
| 361 Many convenience functions are provided to make it easier for you to | |
| 362 access particular elements in a nested list. All of these can be | |
| 363 rewritten in terms of the functions just described. | |
| 364 | |
| 365 @defun caar cons-cell | |
| 366 @defunx cadr cons-cell | |
| 367 @defunx cdar cons-cell | |
| 368 @defunx cddr cons-cell | |
| 369 @defunx caaar cons-cell | |
| 370 @defunx caadr cons-cell | |
| 371 @defunx cadar cons-cell | |
| 372 @defunx caddr cons-cell | |
| 373 @defunx cdaar cons-cell | |
| 374 @defunx cdadr cons-cell | |
| 375 @defunx cddar cons-cell | |
| 376 @defunx cdddr cons-cell | |
| 377 @defunx caaaar cons-cell | |
| 378 @defunx caaadr cons-cell | |
| 379 @defunx caadar cons-cell | |
| 380 @defunx caaddr cons-cell | |
| 381 @defunx cadaar cons-cell | |
| 382 @defunx cadadr cons-cell | |
| 383 @defunx caddar cons-cell | |
| 384 @defunx cadddr cons-cell | |
| 385 @defunx cdaaar cons-cell | |
| 386 @defunx cdaadr cons-cell | |
| 387 @defunx cdadar cons-cell | |
| 388 @defunx cdaddr cons-cell | |
| 389 @defunx cddaar cons-cell | |
| 390 @defunx cddadr cons-cell | |
| 391 @defunx cdddar cons-cell | |
| 392 @defunx cddddr cons-cell | |
| 393 Each of these functions is equivalent to one or more applications of | |
| 394 @code{car} and/or @code{cdr}. For example, | |
| 395 | |
| 396 @example | |
| 397 (cadr x) | |
| 398 @end example | |
| 399 | |
| 400 is equivalent to | |
| 401 | |
| 402 @example | |
| 403 (car (cdr x)) | |
| 404 @end example | |
| 405 | |
| 406 and | |
| 407 | |
| 408 @example | |
| 409 (cdaddr x) | |
| 410 @end example | |
| 411 | |
| 412 is equivalent to | |
| 413 | |
| 414 @example | |
| 415 (cdr (car (cdr (cdr x)))) | |
| 416 @end example | |
| 417 | |
| 418 That is to say, read the a's and d's from right to left and apply | |
| 419 a @code{car} or @code{cdr} for each a or d found, respectively. | |
| 420 @end defun | |
| 421 | |
| 422 @defun first list | |
| 423 This is equivalent to @code{(nth 0 @var{list})}, i.e. the first element | |
| 424 of @var{list}. (Note that this is also equivalent to @code{car}.) | |
| 425 @end defun | |
| 426 | |
| 427 @defun second list | |
| 428 This is equivalent to @code{(nth 1 @var{list})}, i.e. the second element | |
| 429 of @var{list}. | |
| 430 @end defun | |
| 431 | |
| 432 @defun third list | |
| 433 @defunx fourth list | |
| 434 @defunx fifth list | |
| 435 @defunx sixth list | |
| 436 @defunx seventh list | |
| 437 @defunx eighth list | |
| 438 @defunx ninth list | |
| 439 @defunx tenth list | |
| 440 These are equivalent to @code{(nth 2 @var{list})} through | |
| 441 @code{(nth 9 @var{list})} respectively, i.e. the third through tenth | |
| 442 elements of @var{list}. | |
| 443 @end defun | |
| 444 | |
| 445 @node Building Lists | |
| 446 @section Building Cons Cells and Lists | |
| 447 @cindex cons cells | |
| 448 @cindex building lists | |
| 449 | |
| 450 Many functions build lists, as lists reside at the very heart of Lisp. | |
| 451 @code{cons} is the fundamental list-building function; however, it is | |
| 452 interesting to note that @code{list} is used more times in the source | |
| 453 code for Emacs than @code{cons}. | |
| 454 | |
| 455 @defun cons object1 object2 | |
| 456 This function is the fundamental function used to build new list | |
| 457 structure. It creates a new cons cell, making @var{object1} the | |
| 458 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new cons | |
| 459 cell. The arguments @var{object1} and @var{object2} may be any Lisp | |
| 460 objects, but most often @var{object2} is a list. | |
| 461 | |
| 462 @example | |
| 463 @group | |
| 464 (cons 1 '(2)) | |
| 465 @result{} (1 2) | |
| 466 @end group | |
| 467 @group | |
| 468 (cons 1 '()) | |
| 469 @result{} (1) | |
| 470 @end group | |
| 471 @group | |
| 472 (cons 1 2) | |
| 473 @result{} (1 . 2) | |
| 474 @end group | |
| 475 @end example | |
| 476 | |
| 477 @cindex consing | |
| 478 @code{cons} is often used to add a single element to the front of a | |
| 479 list. This is called @dfn{consing the element onto the list}. For | |
| 480 example: | |
| 481 | |
| 482 @example | |
| 483 (setq list (cons newelt list)) | |
| 484 @end example | |
| 485 | |
| 486 Note that there is no conflict between the variable named @code{list} | |
| 487 used in this example and the function named @code{list} described below; | |
| 488 any symbol can serve both purposes. | |
| 489 @end defun | |
| 490 | |
| 491 @defun list &rest objects | |
| 492 This function creates a list with @var{objects} as its elements. The | |
| 493 resulting list is always @code{nil}-terminated. If no @var{objects} | |
| 494 are given, the empty list is returned. | |
| 495 | |
| 496 @example | |
| 497 @group | |
| 498 (list 1 2 3 4 5) | |
| 499 @result{} (1 2 3 4 5) | |
| 500 @end group | |
| 501 @group | |
| 502 (list 1 2 '(3 4 5) 'foo) | |
| 503 @result{} (1 2 (3 4 5) foo) | |
| 504 @end group | |
| 505 @group | |
| 506 (list) | |
| 507 @result{} nil | |
| 508 @end group | |
| 509 @end example | |
| 510 @end defun | |
| 511 | |
| 512 @defun make-list length object | |
| 513 This function creates a list of length @var{length}, in which all the | |
| 514 elements have the identical value @var{object}. Compare | |
| 515 @code{make-list} with @code{make-string} (@pxref{Creating Strings}). | |
| 516 | |
| 517 @example | |
| 518 @group | |
| 519 (make-list 3 'pigs) | |
| 520 @result{} (pigs pigs pigs) | |
| 521 @end group | |
| 522 @group | |
| 523 (make-list 0 'pigs) | |
| 524 @result{} nil | |
| 525 @end group | |
| 526 @end example | |
| 527 @end defun | |
| 528 | |
| 529 @defun append &rest sequences | |
| 530 @cindex copying lists | |
| 531 This function returns a list containing all the elements of | |
| 532 @var{sequences}. The @var{sequences} may be lists, vectors, or strings, | |
| 533 but the last one should be a list. All arguments except the last one | |
| 534 are copied, so none of them are altered. | |
| 535 | |
| 536 More generally, the final argument to @code{append} may be any Lisp | |
| 537 object. The final argument is not copied or converted; it becomes the | |
| 538 @sc{cdr} of the last cons cell in the new list. If the final argument | |
| 539 is itself a list, then its elements become in effect elements of the | |
| 540 result list. If the final element is not a list, the result is a | |
| 541 ``dotted list'' since its final @sc{cdr} is not @code{nil} as required | |
| 542 in a true list. | |
| 543 | |
| 544 See @code{nconc} in @ref{Rearrangement}, for a way to join lists with no | |
| 545 copying. | |
| 546 | |
| 547 Here is an example of using @code{append}: | |
| 548 | |
| 549 @example | |
| 550 @group | |
| 551 (setq trees '(pine oak)) | |
| 552 @result{} (pine oak) | |
| 553 (setq more-trees (append '(maple birch) trees)) | |
| 554 @result{} (maple birch pine oak) | |
| 555 @end group | |
| 556 | |
| 557 @group | |
| 558 trees | |
| 559 @result{} (pine oak) | |
| 560 more-trees | |
| 561 @result{} (maple birch pine oak) | |
| 562 @end group | |
| 563 @group | |
| 564 (eq trees (cdr (cdr more-trees))) | |
| 565 @result{} t | |
| 566 @end group | |
| 567 @end example | |
| 568 | |
| 569 You can see how @code{append} works by looking at a box diagram. The | |
| 570 variable @code{trees} is set to the list @code{(pine oak)} and then the | |
| 571 variable @code{more-trees} is set to the list @code{(maple birch pine | |
| 572 oak)}. However, the variable @code{trees} continues to refer to the | |
| 573 original list: | |
| 574 | |
| 575 @smallexample | |
| 576 @group | |
| 577 more-trees trees | |
| 578 | | | |
| 579 | ___ ___ ___ ___ -> ___ ___ ___ ___ | |
| 580 --> |___|___|--> |___|___|--> |___|___|--> |___|___|--> nil | |
| 581 | | | | | |
| 582 | | | | | |
| 583 --> maple -->birch --> pine --> oak | |
| 584 @end group | |
| 585 @end smallexample | |
| 586 | |
| 587 An empty sequence contributes nothing to the value returned by | |
| 588 @code{append}. As a consequence of this, a final @code{nil} argument | |
| 589 forces a copy of the previous argument. | |
| 590 | |
| 591 @example | |
| 592 @group | |
| 593 trees | |
| 594 @result{} (pine oak) | |
| 595 @end group | |
| 596 @group | |
| 597 (setq wood (append trees ())) | |
| 598 @result{} (pine oak) | |
| 599 @end group | |
| 600 @group | |
| 601 wood | |
| 602 @result{} (pine oak) | |
| 603 @end group | |
| 604 @group | |
| 605 (eq wood trees) | |
| 606 @result{} nil | |
| 607 @end group | |
| 608 @end example | |
| 609 | |
| 610 @noindent | |
| 611 This once was the usual way to copy a list, before the function | |
| 612 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}. | |
| 613 | |
| 614 With the help of @code{apply}, we can append all the lists in a list of | |
| 615 lists: | |
| 616 | |
| 617 @example | |
| 618 @group | |
| 619 (apply 'append '((a b c) nil (x y z) nil)) | |
| 620 @result{} (a b c x y z) | |
| 621 @end group | |
| 622 @end example | |
| 623 | |
| 624 If no @var{sequences} are given, @code{nil} is returned: | |
| 625 | |
| 626 @example | |
| 627 @group | |
| 628 (append) | |
| 629 @result{} nil | |
| 630 @end group | |
| 631 @end example | |
| 632 | |
| 633 Here are some examples where the final argument is not a list: | |
| 634 | |
| 635 @example | |
| 636 (append '(x y) 'z) | |
| 637 @result{} (x y . z) | |
| 638 (append '(x y) [z]) | |
| 639 @result{} (x y . [z]) | |
| 640 @end example | |
| 641 | |
| 642 @noindent | |
| 643 The second example shows that when the final argument is a sequence but | |
| 644 not a list, the sequence's elements do not become elements of the | |
| 645 resulting list. Instead, the sequence becomes the final @sc{cdr}, like | |
| 646 any other non-list final argument. | |
| 647 | |
| 648 The @code{append} function also allows integers as arguments. It | |
| 649 converts them to strings of digits, making up the decimal print | |
| 650 representation of the integer, and then uses the strings instead of the | |
| 651 original integers. @strong{Don't use this feature; we plan to eliminate | |
| 652 it. If you already use this feature, change your programs now!} The | |
| 653 proper way to convert an integer to a decimal number in this way is with | |
| 654 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string} | |
| 655 (@pxref{String Conversion}). | |
| 656 @end defun | |
| 657 | |
|
5300
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
658 @defun reverse sequence |
|
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
659 This function creates a new sequence whose elements are the elements of |
|
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
660 @var{sequence}, but in reverse order. The original argument @var{sequence} is |
| 428 | 661 @emph{not} altered. |
| 662 | |
| 663 @example | |
| 664 @group | |
| 665 (setq x '(1 2 3 4)) | |
| 666 @result{} (1 2 3 4) | |
| 667 @end group | |
| 668 @group | |
| 669 (reverse x) | |
| 670 @result{} (4 3 2 1) | |
| 671 x | |
| 672 @result{} (1 2 3 4) | |
| 673 @end group | |
| 674 @end example | |
| 675 @end defun | |
| 676 | |
| 677 @node Modifying Lists | |
| 678 @section Modifying Existing List Structure | |
| 679 | |
| 680 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the | |
| 681 primitives @code{setcar} and @code{setcdr}. | |
| 682 | |
| 683 @cindex CL note---@code{rplaca} vrs @code{setcar} | |
| 684 @quotation | |
| 685 @findex rplaca | |
| 686 @findex rplacd | |
| 687 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and | |
| 688 @code{rplacd} to alter list structure; they change structure the same | |
| 689 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions | |
| 690 return the cons cell while @code{setcar} and @code{setcdr} return the | |
| 691 new @sc{car} or @sc{cdr}. | |
| 692 @end quotation | |
| 693 | |
| 694 @menu | |
| 695 * Setcar:: Replacing an element in a list. | |
| 696 * Setcdr:: Replacing part of the list backbone. | |
| 697 This can be used to remove or add elements. | |
| 698 * Rearrangement:: Reordering the elements in a list; combining lists. | |
| 699 @end menu | |
| 700 | |
| 701 @node Setcar | |
| 702 @subsection Altering List Elements with @code{setcar} | |
| 703 | |
| 704 Changing the @sc{car} of a cons cell is done with @code{setcar}. When | |
| 705 used on a list, @code{setcar} replaces one element of a list with a | |
| 706 different element. | |
| 707 | |
| 444 | 708 @defun setcar cons-cell object |
| 709 This function stores @var{object} as the new @sc{car} of @var{cons-cell}, | |
| 428 | 710 replacing its previous @sc{car}. It returns the value @var{object}. |
| 711 For example: | |
| 712 | |
| 713 @example | |
| 714 @group | |
| 715 (setq x '(1 2)) | |
| 716 @result{} (1 2) | |
| 717 @end group | |
| 718 @group | |
| 719 (setcar x 4) | |
| 720 @result{} 4 | |
| 721 @end group | |
| 722 @group | |
| 723 x | |
| 724 @result{} (4 2) | |
| 725 @end group | |
| 726 @end example | |
| 727 @end defun | |
| 728 | |
| 729 When a cons cell is part of the shared structure of several lists, | |
| 730 storing a new @sc{car} into the cons changes one element of each of | |
| 731 these lists. Here is an example: | |
| 732 | |
| 733 @example | |
| 734 @group | |
| 735 ;; @r{Create two lists that are partly shared.} | |
| 736 (setq x1 '(a b c)) | |
| 737 @result{} (a b c) | |
| 738 (setq x2 (cons 'z (cdr x1))) | |
| 739 @result{} (z b c) | |
| 740 @end group | |
| 741 | |
| 742 @group | |
| 743 ;; @r{Replace the @sc{car} of a shared link.} | |
| 744 (setcar (cdr x1) 'foo) | |
| 745 @result{} foo | |
| 746 x1 ; @r{Both lists are changed.} | |
| 747 @result{} (a foo c) | |
| 748 x2 | |
| 749 @result{} (z foo c) | |
| 750 @end group | |
| 751 | |
| 752 @group | |
| 753 ;; @r{Replace the @sc{car} of a link that is not shared.} | |
| 754 (setcar x1 'baz) | |
| 755 @result{} baz | |
| 756 x1 ; @r{Only one list is changed.} | |
| 757 @result{} (baz foo c) | |
| 758 x2 | |
| 759 @result{} (z foo c) | |
| 760 @end group | |
| 761 @end example | |
| 762 | |
| 763 Here is a graphical depiction of the shared structure of the two lists | |
| 764 in the variables @code{x1} and @code{x2}, showing why replacing @code{b} | |
| 765 changes them both: | |
| 766 | |
| 767 @example | |
| 768 @group | |
| 769 ___ ___ ___ ___ ___ ___ | |
| 770 x1---> |___|___|----> |___|___|--> |___|___|--> nil | |
| 771 | --> | | | |
| 772 | | | | | |
| 773 --> a | --> b --> c | |
| 774 | | |
| 775 ___ ___ | | |
| 776 x2--> |___|___|-- | |
| 777 | | |
| 778 | | |
| 779 --> z | |
| 780 @end group | |
| 781 @end example | |
| 782 | |
| 783 Here is an alternative form of box diagram, showing the same relationship: | |
| 784 | |
| 785 @example | |
| 786 @group | |
| 787 x1: | |
| 788 -------------- -------------- -------------- | |
| 789 | car | cdr | | car | cdr | | car | cdr | | |
| 790 | a | o------->| b | o------->| c | nil | | |
| 791 | | | -->| | | | | | | |
| 792 -------------- | -------------- -------------- | |
| 793 | | |
| 794 x2: | | |
| 795 -------------- | | |
| 796 | car | cdr | | | |
| 797 | z | o---- | |
| 798 | | | | |
| 799 -------------- | |
| 800 @end group | |
| 801 @end example | |
| 802 | |
| 803 @node Setcdr | |
| 804 @subsection Altering the CDR of a List | |
| 805 | |
| 806 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}: | |
| 807 | |
| 444 | 808 @defun setcdr cons-cell object |
| 809 This function stores @var{object} as the new @sc{cdr} of @var{cons-cell}, | |
| 428 | 810 replacing its previous @sc{cdr}. It returns the value @var{object}. |
| 811 @end defun | |
| 812 | |
| 813 Here is an example of replacing the @sc{cdr} of a list with a | |
| 814 different list. All but the first element of the list are removed in | |
| 815 favor of a different sequence of elements. The first element is | |
| 816 unchanged, because it resides in the @sc{car} of the list, and is not | |
| 817 reached via the @sc{cdr}. | |
| 818 | |
| 819 @example | |
| 820 @group | |
| 821 (setq x '(1 2 3)) | |
| 822 @result{} (1 2 3) | |
| 823 @end group | |
| 824 @group | |
| 825 (setcdr x '(4)) | |
| 826 @result{} (4) | |
| 827 @end group | |
| 828 @group | |
| 829 x | |
| 830 @result{} (1 4) | |
| 831 @end group | |
| 832 @end example | |
| 833 | |
| 834 You can delete elements from the middle of a list by altering the | |
| 835 @sc{cdr}s of the cons cells in the list. For example, here we delete | |
| 836 the second element, @code{b}, from the list @code{(a b c)}, by changing | |
| 837 the @sc{cdr} of the first cell: | |
| 838 | |
| 839 @example | |
| 840 @group | |
| 841 (setq x1 '(a b c)) | |
| 842 @result{} (a b c) | |
| 843 (setcdr x1 (cdr (cdr x1))) | |
| 844 @result{} (c) | |
| 845 x1 | |
| 846 @result{} (a c) | |
| 847 @end group | |
| 848 @end example | |
| 849 | |
| 850 @need 4000 | |
| 851 Here is the result in box notation: | |
| 852 | |
| 853 @example | |
| 854 @group | |
| 855 -------------------- | |
| 856 | | | |
| 857 -------------- | -------------- | -------------- | |
| 858 | car | cdr | | | car | cdr | -->| car | cdr | | |
| 859 | a | o----- | b | o-------->| c | nil | | |
| 860 | | | | | | | | | | |
| 861 -------------- -------------- -------------- | |
| 862 @end group | |
| 863 @end example | |
| 864 | |
| 865 @noindent | |
| 866 The second cons cell, which previously held the element @code{b}, still | |
| 867 exists and its @sc{car} is still @code{b}, but it no longer forms part | |
| 868 of this list. | |
| 869 | |
| 870 It is equally easy to insert a new element by changing @sc{cdr}s: | |
| 871 | |
| 872 @example | |
| 873 @group | |
| 874 (setq x1 '(a b c)) | |
| 875 @result{} (a b c) | |
| 876 (setcdr x1 (cons 'd (cdr x1))) | |
| 877 @result{} (d b c) | |
| 878 x1 | |
| 879 @result{} (a d b c) | |
| 880 @end group | |
| 881 @end example | |
| 882 | |
| 883 Here is this result in box notation: | |
| 884 | |
| 885 @smallexample | |
| 886 @group | |
| 887 -------------- ------------- ------------- | |
| 888 | car | cdr | | car | cdr | | car | cdr | | |
| 889 | a | o | -->| b | o------->| c | nil | | |
| 890 | | | | | | | | | | | | |
| 891 --------- | -- | ------------- ------------- | |
| 892 | | | |
| 893 ----- -------- | |
| 894 | | | |
| 895 | --------------- | | |
| 896 | | car | cdr | | | |
| 897 -->| d | o------ | |
| 898 | | | | |
| 899 --------------- | |
| 900 @end group | |
| 901 @end smallexample | |
| 902 | |
| 903 @node Rearrangement | |
| 904 @subsection Functions that Rearrange Lists | |
| 905 @cindex rearrangement of lists | |
| 906 @cindex modification of lists | |
| 907 | |
| 908 Here are some functions that rearrange lists ``destructively'' by | |
| 909 modifying the @sc{cdr}s of their component cons cells. We call these | |
| 910 functions ``destructive'' because they chew up the original lists passed | |
| 911 to them as arguments, to produce a new list that is the returned value. | |
| 912 | |
| 913 @ifinfo | |
| 914 See @code{delq}, in @ref{Sets And Lists}, for another function | |
| 915 that modifies cons cells. | |
| 916 @end ifinfo | |
| 917 @iftex | |
| 918 The function @code{delq} in the following section is another example | |
| 919 of destructive list manipulation. | |
| 920 @end iftex | |
| 921 | |
| 922 @defun nconc &rest lists | |
| 923 @cindex concatenating lists | |
| 924 @cindex joining lists | |
| 925 This function returns a list containing all the elements of @var{lists}. | |
| 926 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are | |
| 927 @emph{not} copied. Instead, the last @sc{cdr} of each of the | |
| 928 @var{lists} is changed to refer to the following list. The last of the | |
| 929 @var{lists} is not altered. For example: | |
| 930 | |
| 931 @example | |
| 932 @group | |
| 933 (setq x '(1 2 3)) | |
| 934 @result{} (1 2 3) | |
| 935 @end group | |
| 936 @group | |
| 937 (nconc x '(4 5)) | |
| 938 @result{} (1 2 3 4 5) | |
| 939 @end group | |
| 940 @group | |
| 941 x | |
| 942 @result{} (1 2 3 4 5) | |
| 943 @end group | |
| 944 @end example | |
| 945 | |
| 946 Since the last argument of @code{nconc} is not itself modified, it is | |
| 947 reasonable to use a constant list, such as @code{'(4 5)}, as in the | |
| 948 above example. For the same reason, the last argument need not be a | |
| 949 list: | |
| 950 | |
| 951 @example | |
| 952 @group | |
| 953 (setq x '(1 2 3)) | |
| 954 @result{} (1 2 3) | |
| 955 @end group | |
| 956 @group | |
| 957 (nconc x 'z) | |
| 958 @result{} (1 2 3 . z) | |
| 959 @end group | |
| 960 @group | |
| 961 x | |
| 962 @result{} (1 2 3 . z) | |
| 963 @end group | |
| 964 @end example | |
| 965 | |
| 966 A common pitfall is to use a quoted constant list as a non-last | |
| 967 argument to @code{nconc}. If you do this, your program will change | |
| 968 each time you run it! Here is what happens: | |
| 969 | |
| 970 @smallexample | |
| 971 @group | |
| 972 (defun add-foo (x) ; @r{We want this function to add} | |
| 973 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.} | |
| 974 @end group | |
| 975 | |
| 976 @group | |
| 977 (symbol-function 'add-foo) | |
| 978 @result{} (lambda (x) (nconc (quote (foo)) x)) | |
| 979 @end group | |
| 980 | |
| 981 @group | |
| 982 (setq xx (add-foo '(1 2))) ; @r{It seems to work.} | |
| 983 @result{} (foo 1 2) | |
| 984 @end group | |
| 985 @group | |
| 986 (setq xy (add-foo '(3 4))) ; @r{What happened?} | |
| 987 @result{} (foo 1 2 3 4) | |
| 988 @end group | |
| 989 @group | |
| 990 (eq xx xy) | |
| 991 @result{} t | |
| 992 @end group | |
| 993 | |
| 994 @group | |
| 995 (symbol-function 'add-foo) | |
| 996 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x))) | |
| 997 @end group | |
| 998 @end smallexample | |
| 999 @end defun | |
| 1000 | |
|
5300
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
1001 @defun nreverse sequence |
| 428 | 1002 @cindex reversing a list |
|
5300
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
1003 @cindex reversing a sequence |
|
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
1004 This function reverses the order of the elements of @var{sequence}. |
|
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
1005 Unlike @code{reverse}, @code{nreverse} alters its argument. If |
|
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
1006 @var{sequence} is a list, it does this by reversing the @sc{cdr}s in the |
|
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
1007 cons cells forming the sequence. The cons cell that used to be the last |
|
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
1008 one in @var{sequence} becomes the first cell of the value. |
| 428 | 1009 |
| 1010 For example: | |
| 1011 | |
| 1012 @example | |
| 1013 @group | |
| 1014 (setq x '(1 2 3 4)) | |
| 1015 @result{} (1 2 3 4) | |
| 1016 @end group | |
| 1017 @group | |
| 1018 x | |
| 1019 @result{} (1 2 3 4) | |
| 1020 (nreverse x) | |
| 1021 @result{} (4 3 2 1) | |
| 1022 @end group | |
| 1023 @group | |
| 1024 ;; @r{The cell that was first is now last.} | |
| 1025 x | |
| 1026 @result{} (1) | |
| 1027 @end group | |
| 1028 @end example | |
| 1029 | |
| 1030 To avoid confusion, we usually store the result of @code{nreverse} | |
|
5300
9f738305f80f
Accept sequences generally, not just lists, #'reverse, #'nreverse.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5182
diff
changeset
|
1031 back in the same variable which held the original sequence: |
| 428 | 1032 |
| 1033 @example | |
| 1034 (setq x (nreverse x)) | |
| 1035 @end example | |
| 1036 | |
| 1037 Here is the @code{nreverse} of our favorite example, @code{(a b c)}, | |
| 1038 presented graphically: | |
| 1039 | |
| 1040 @smallexample | |
| 1041 @group | |
| 1042 @r{Original list head:} @r{Reversed list:} | |
| 1043 ------------- ------------- ------------ | |
| 1044 | car | cdr | | car | cdr | | car | cdr | | |
| 1045 | a | nil |<-- | b | o |<-- | c | o | | |
| 1046 | | | | | | | | | | | | | | |
| 1047 ------------- | --------- | - | -------- | - | |
| 1048 | | | | | |
| 1049 ------------- ------------ | |
| 1050 @end group | |
| 1051 @end smallexample | |
| 1052 @end defun | |
| 1053 | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1054 @defun sort* sequence predicate &key (key #'identity) |
| 428 | 1055 @cindex stable sort |
| 1056 @cindex sorting lists | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1057 @cindex sorting arrays |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1058 @cindex sort |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1059 This function sorts @var{sequence} stably, though destructively, and |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1060 returns the sorted sequence. It compares elements using @var{predicate}. A |
| 428 | 1061 stable sort is one in which elements with equal sort keys maintain their |
| 1062 relative order before and after the sort. Stability is important when | |
| 1063 successive sorts are used to order elements according to different | |
| 1064 criteria. | |
| 1065 | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1066 @var{sequence} can be any sequence, that is, a list, a vector, a |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1067 bit-vector, or a string. |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1068 |
| 428 | 1069 The argument @var{predicate} must be a function that accepts two |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1070 arguments. It is called with two elements of @var{sequence}. To get an |
| 428 | 1071 increasing order sort, the @var{predicate} should return @code{t} if the |
| 1072 first element is ``less than'' the second, or @code{nil} if not. | |
| 1073 | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1074 The keyword argument @var{key}, if supplied, is a function used to |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1075 extract an object to be used for comparison from each element of |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1076 @var{sequence}, and defaults to @code{identity}. For example, to sort a |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1077 vector of lists by the numeric value of the first element, you could use |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1078 the following code: |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1079 |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1080 @example |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1081 @group |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1082 (setq example-vector [(1 "foo") (3.14159 bar) (2 . quux)]) |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1083 @result{} [(1 "foo") (3.14159 bar) (2 . quux)] |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1084 @end group |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1085 @group |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1086 (sort* example-vector #'< :key #'car) |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1087 @result{} [(1 "foo") (2 . quux) (3.14159 bar)] |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1088 @end group |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1089 @end example |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1090 |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1091 If @var{sequence} is a list, @code{sort*} rearranges the cons cells |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1092 forming @var{sequence} by changing @sc{cdr}s. A nondestructive sort |
| 428 | 1093 function would create new cons cells to store the elements in their |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1094 sorted order. @code{sort*} treats other sequence types in an analogous |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1095 fashion---if you wish to make a sorted copy without destroying the |
| 428 | 1096 original, copy it first with @code{copy-sequence} and then sort. |
| 1097 | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1098 Sorting will not change the @sc{car}s of the cons cells of a list |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1099 @var{sequence}; the cons cell that originally contained the element @code{a} in |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1100 @var{sequence} still has @code{a} in its @sc{car} after sorting, but it now |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1101 appears in a different position in the sequence due to the change of |
| 428 | 1102 @sc{cdr}s. For example: |
| 1103 | |
| 1104 @example | |
| 1105 @group | |
| 1106 (setq nums '(1 3 2 6 5 4 0)) | |
| 1107 @result{} (1 3 2 6 5 4 0) | |
| 1108 @end group | |
| 1109 @group | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1110 (sort* nums '<) |
| 428 | 1111 @result{} (0 1 2 3 4 5 6) |
| 1112 @end group | |
| 1113 @group | |
| 1114 nums | |
| 1115 @result{} (1 2 3 4 5 6) | |
| 1116 @end group | |
| 1117 @end example | |
| 1118 | |
| 1119 @noindent | |
| 1120 Note that the list in @code{nums} no longer contains 0; this is the same | |
| 1121 cons cell that it was before, but it is no longer the first one in the | |
| 1122 list. Don't assume a variable that formerly held the argument now holds | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1123 the entire sorted list! Instead, save the result of @code{sort*} and use |
| 428 | 1124 that. Most often we store the result back into the variable that held |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1125 the original sequence: |
| 428 | 1126 |
| 1127 @example | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1128 (setq nums (sort* nums '<)) |
| 428 | 1129 @end example |
| 1130 | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1131 In this implementation, @code{sort} is a function alias for |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1132 @code{sort*}, and accepts the same arguments. In older XEmacs, and in |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1133 current GNU Emacs, @code{sort} only accepted lists, and did not accept |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1134 the @var{key} argument, so the byte-compiler will warn you if you call |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1135 @code{sort} with more than two arguments. |
|
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1136 |
| 428 | 1137 @xref{Sorting}, for more functions that perform sorting. |
| 1138 See @code{documentation} in @ref{Accessing Documentation}, for a | |
|
5182
2e528066e2fc
Move #'sort*, #'fill, #'merge to C from cl-seq.el.
Aidan Kehoe <kehoea@parhasard.net>
parents:
1554
diff
changeset
|
1139 useful example of @code{sort*}. |
| 428 | 1140 @end defun |
| 1141 | |
| 1142 @node Sets And Lists | |
| 1143 @section Using Lists as Sets | |
| 1144 @cindex lists as sets | |
| 1145 @cindex sets | |
| 1146 | |
| 1147 A list can represent an unordered mathematical set---simply consider a | |
| 1148 value an element of a set if it appears in the list, and ignore the | |
| 1149 order of the list. To form the union of two sets, use @code{append} (as | |
| 1150 long as you don't mind having duplicate elements). Other useful | |
| 1151 functions for sets include @code{memq} and @code{delq}, and their | |
| 1152 @code{equal} versions, @code{member} and @code{delete}. | |
| 1153 | |
| 1154 @cindex CL note---lack @code{union}, @code{set} | |
| 1155 @quotation | |
| 1156 @b{Common Lisp note:} Common Lisp has functions @code{union} (which | |
| 1157 avoids duplicate elements) and @code{intersection} for set operations, | |
| 1158 but XEmacs Lisp does not have them. You can write them in Lisp if | |
| 1159 you wish. | |
| 1160 @end quotation | |
| 1161 | |
| 1162 @defun memq object list | |
| 1163 @cindex membership in a list | |
| 1164 This function tests to see whether @var{object} is a member of | |
| 1165 @var{list}. If it is, @code{memq} returns a list starting with the | |
| 1166 first occurrence of @var{object}. Otherwise, it returns @code{nil}. | |
| 1167 The letter @samp{q} in @code{memq} says that it uses @code{eq} to | |
| 1168 compare @var{object} against the elements of the list. For example: | |
| 1169 | |
| 1170 @example | |
| 1171 @group | |
| 1172 (memq 'b '(a b c b a)) | |
| 1173 @result{} (b c b a) | |
| 1174 @end group | |
| 1175 @group | |
| 1176 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} | |
| 1177 @result{} nil | |
| 1178 @end group | |
| 1179 @end example | |
| 1180 @end defun | |
| 1181 | |
| 1182 @defun delq object list | |
| 1183 @cindex deletion of elements | |
| 1184 This function destructively removes all elements @code{eq} to | |
| 1185 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says | |
| 1186 that it uses @code{eq} to compare @var{object} against the elements of | |
| 1187 the list, like @code{memq}. | |
| 1188 @end defun | |
| 1189 | |
| 1190 When @code{delq} deletes elements from the front of the list, it does so | |
| 1191 simply by advancing down the list and returning a sublist that starts | |
| 1192 after those elements: | |
| 1193 | |
| 1194 @example | |
| 1195 @group | |
| 1196 (delq 'a '(a b c)) @equiv{} (cdr '(a b c)) | |
| 1197 @end group | |
| 1198 @end example | |
| 1199 | |
| 1200 When an element to be deleted appears in the middle of the list, | |
| 1201 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}). | |
| 1202 | |
| 1203 @example | |
| 1204 @group | |
| 1205 (setq sample-list '(a b c (4))) | |
| 1206 @result{} (a b c (4)) | |
| 1207 @end group | |
| 1208 @group | |
| 1209 (delq 'a sample-list) | |
| 1210 @result{} (b c (4)) | |
| 1211 @end group | |
| 1212 @group | |
| 1213 sample-list | |
| 1214 @result{} (a b c (4)) | |
| 1215 @end group | |
| 1216 @group | |
| 1217 (delq 'c sample-list) | |
| 1218 @result{} (a b (4)) | |
| 1219 @end group | |
| 1220 @group | |
| 1221 sample-list | |
| 1222 @result{} (a b (4)) | |
| 1223 @end group | |
| 1224 @end example | |
| 1225 | |
| 1226 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to | |
| 1227 splice out the third element, but @code{(delq 'a sample-list)} does not | |
| 1228 splice anything---it just returns a shorter list. Don't assume that a | |
| 1229 variable which formerly held the argument @var{list} now has fewer | |
| 1230 elements, or that it still holds the original list! Instead, save the | |
| 1231 result of @code{delq} and use that. Most often we store the result back | |
| 1232 into the variable that held the original list: | |
| 1233 | |
| 1234 @example | |
| 1235 (setq flowers (delq 'rose flowers)) | |
| 1236 @end example | |
| 1237 | |
| 1238 In the following example, the @code{(4)} that @code{delq} attempts to match | |
| 1239 and the @code{(4)} in the @code{sample-list} are not @code{eq}: | |
| 1240 | |
| 1241 @example | |
| 1242 @group | |
| 1243 (delq '(4) sample-list) | |
| 1244 @result{} (a c (4)) | |
| 1245 @end group | |
| 1246 @end example | |
| 1247 | |
| 1248 The following two functions are like @code{memq} and @code{delq} but use | |
| 1249 @code{equal} rather than @code{eq} to compare elements. They are new in | |
| 1250 Emacs 19. | |
| 1251 | |
| 1252 @defun member object list | |
| 1253 The function @code{member} tests to see whether @var{object} is a member | |
| 1254 of @var{list}, comparing members with @var{object} using @code{equal}. | |
| 1255 If @var{object} is a member, @code{member} returns a list starting with | |
| 1256 its first occurrence in @var{list}. Otherwise, it returns @code{nil}. | |
| 1257 | |
| 1258 Compare this with @code{memq}: | |
| 1259 | |
| 1260 @example | |
| 1261 @group | |
| 1262 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.} | |
| 1263 @result{} ((2)) | |
| 1264 @end group | |
| 1265 @group | |
| 1266 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.} | |
| 1267 @result{} nil | |
| 1268 @end group | |
| 1269 @group | |
| 1270 ;; @r{Two strings with the same contents are @code{equal}.} | |
| 1271 (member "foo" '("foo" "bar")) | |
| 1272 @result{} ("foo" "bar") | |
| 1273 @end group | |
| 1274 @end example | |
| 1275 @end defun | |
| 1276 | |
| 1277 @defun delete object list | |
| 1278 This function destructively removes all elements @code{equal} to | |
| 1279 @var{object} from @var{list}. It is to @code{delq} as @code{member} is | |
| 1280 to @code{memq}: it uses @code{equal} to compare elements with | |
| 1281 @var{object}, like @code{member}; when it finds an element that matches, | |
| 1282 it removes the element just as @code{delq} would. For example: | |
| 1283 | |
| 1284 @example | |
| 1285 @group | |
| 1286 (delete '(2) '((2) (1) (2))) | |
| 1287 @result{} '((1)) | |
| 1288 @end group | |
| 1289 @end example | |
| 1290 @end defun | |
| 1291 | |
| 1292 @quotation | |
| 1293 @b{Common Lisp note:} The functions @code{member} and @code{delete} in | |
| 1294 XEmacs Lisp are derived from Maclisp, not Common Lisp. The Common | |
| 1295 Lisp versions do not use @code{equal} to compare elements. | |
| 1296 @end quotation | |
| 1297 | |
| 1298 See also the function @code{add-to-list}, in @ref{Setting Variables}, | |
| 1299 for another way to add an element to a list stored in a variable. | |
| 1300 | |
| 1301 @node Association Lists | |
| 1302 @section Association Lists | |
| 1303 @cindex association list | |
| 1304 @cindex alist | |
| 1305 | |
| 1306 An @dfn{association list}, or @dfn{alist} for short, records a mapping | |
| 1307 from keys to values. It is a list of cons cells called | |
| 1308 @dfn{associations}: the @sc{car} of each cell is the @dfn{key}, and the | |
| 1309 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key'' | |
| 1310 is not related to the term ``key sequence''; it means a value used to | |
| 1311 look up an item in a table. In this case, the table is the alist, and | |
| 1312 the alist associations are the items.} | |
| 1313 | |
| 1314 Here is an example of an alist. The key @code{pine} is associated with | |
| 1315 the value @code{cones}; the key @code{oak} is associated with | |
| 1316 @code{acorns}; and the key @code{maple} is associated with @code{seeds}. | |
| 1317 | |
| 1318 @example | |
| 1319 @group | |
| 1320 '((pine . cones) | |
| 1321 (oak . acorns) | |
| 1322 (maple . seeds)) | |
| 1323 @end group | |
| 1324 @end example | |
| 1325 | |
| 1326 The associated values in an alist may be any Lisp objects; so may the | |
| 1327 keys. For example, in the following alist, the symbol @code{a} is | |
| 1328 associated with the number @code{1}, and the string @code{"b"} is | |
| 1329 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of | |
| 1330 the alist element: | |
| 1331 | |
| 1332 @example | |
| 1333 ((a . 1) ("b" 2 3)) | |
| 1334 @end example | |
| 1335 | |
| 1336 Sometimes it is better to design an alist to store the associated | |
| 1337 value in the @sc{car} of the @sc{cdr} of the element. Here is an | |
| 1338 example: | |
| 1339 | |
| 1340 @example | |
| 1341 '((rose red) (lily white) (buttercup yellow)) | |
| 1342 @end example | |
| 1343 | |
| 1344 @noindent | |
| 1345 Here we regard @code{red} as the value associated with @code{rose}. One | |
| 1346 advantage of this method is that you can store other related | |
| 1347 information---even a list of other items---in the @sc{cdr} of the | |
| 1348 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see | |
| 1349 below) to find the element containing a given value. When neither of | |
| 1350 these considerations is important, the choice is a matter of taste, as | |
| 1351 long as you are consistent about it for any given alist. | |
| 1352 | |
| 1353 Note that the same alist shown above could be regarded as having the | |
| 1354 associated value in the @sc{cdr} of the element; the value associated | |
| 1355 with @code{rose} would be the list @code{(red)}. | |
| 1356 | |
| 1357 Association lists are often used to record information that you might | |
| 1358 otherwise keep on a stack, since new associations may be added easily to | |
| 1359 the front of the list. When searching an association list for an | |
| 1360 association with a given key, the first one found is returned, if there | |
| 1361 is more than one. | |
| 1362 | |
| 1363 In XEmacs Lisp, it is @emph{not} an error if an element of an | |
| 1364 association list is not a cons cell. The alist search functions simply | |
| 1365 ignore such elements. Many other versions of Lisp signal errors in such | |
| 1366 cases. | |
| 1367 | |
| 1368 Note that property lists are similar to association lists in several | |
| 1369 respects. A property list behaves like an association list in which | |
| 1370 each key can occur only once. @xref{Property Lists}, for a comparison | |
| 1371 of property lists and association lists. | |
| 1372 | |
| 1373 @defun assoc key alist | |
| 1374 This function returns the first association for @var{key} in | |
| 1375 @var{alist}. It compares @var{key} against the alist elements using | |
| 1376 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no | |
| 1377 association in @var{alist} has a @sc{car} @code{equal} to @var{key}. | |
| 1378 For example: | |
| 1379 | |
| 1380 @smallexample | |
| 1381 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
| 1382 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) | |
| 1383 (assoc 'oak trees) | |
| 1384 @result{} (oak . acorns) | |
| 1385 (cdr (assoc 'oak trees)) | |
| 1386 @result{} acorns | |
| 1387 (assoc 'birch trees) | |
| 1388 @result{} nil | |
| 1389 @end smallexample | |
| 1390 | |
| 1391 Here is another example, in which the keys and values are not symbols: | |
| 1392 | |
| 1393 @smallexample | |
| 1394 (setq needles-per-cluster | |
| 1395 '((2 "Austrian Pine" "Red Pine") | |
| 1396 (3 "Pitch Pine") | |
| 1397 (5 "White Pine"))) | |
| 1398 | |
| 1399 (cdr (assoc 3 needles-per-cluster)) | |
| 1400 @result{} ("Pitch Pine") | |
| 1401 (cdr (assoc 2 needles-per-cluster)) | |
| 1402 @result{} ("Austrian Pine" "Red Pine") | |
| 1403 @end smallexample | |
| 1404 @end defun | |
| 1405 | |
| 1406 @defun rassoc value alist | |
| 1407 This function returns the first association with value @var{value} in | |
| 1408 @var{alist}. It returns @code{nil} if no association in @var{alist} has | |
| 1409 a @sc{cdr} @code{equal} to @var{value}. | |
| 1410 | |
| 1411 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of | |
| 1412 each @var{alist} association instead of the @sc{car}. You can think of | |
| 1413 this as ``reverse @code{assoc}'', finding the key for a given value. | |
| 1414 @end defun | |
| 1415 | |
| 1416 @defun assq key alist | |
| 1417 This function is like @code{assoc} in that it returns the first | |
| 1418 association for @var{key} in @var{alist}, but it makes the comparison | |
| 1419 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil} | |
| 1420 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}. | |
| 1421 This function is used more often than @code{assoc}, since @code{eq} is | |
| 1422 faster than @code{equal} and most alists use symbols as keys. | |
| 1423 @xref{Equality Predicates}. | |
| 1424 | |
| 1425 @smallexample | |
| 1426 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
| 1427 @result{} ((pine . cones) (oak . acorns) (maple . seeds)) | |
| 1428 (assq 'pine trees) | |
| 1429 @result{} (pine . cones) | |
| 1430 @end smallexample | |
| 1431 | |
| 1432 On the other hand, @code{assq} is not usually useful in alists where the | |
| 1433 keys may not be symbols: | |
| 1434 | |
| 1435 @smallexample | |
| 1436 (setq leaves | |
| 1437 '(("simple leaves" . oak) | |
| 1438 ("compound leaves" . horsechestnut))) | |
| 1439 | |
| 1440 (assq "simple leaves" leaves) | |
| 1441 @result{} nil | |
| 1442 (assoc "simple leaves" leaves) | |
| 1443 @result{} ("simple leaves" . oak) | |
| 1444 @end smallexample | |
| 1445 @end defun | |
| 1446 | |
| 1447 @defun rassq value alist | |
| 1448 This function returns the first association with value @var{value} in | |
| 1449 @var{alist}. It returns @code{nil} if no association in @var{alist} has | |
| 1450 a @sc{cdr} @code{eq} to @var{value}. | |
| 1451 | |
| 1452 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of | |
| 1453 each @var{alist} association instead of the @sc{car}. You can think of | |
| 1454 this as ``reverse @code{assq}'', finding the key for a given value. | |
| 1455 | |
| 1456 For example: | |
| 1457 | |
| 1458 @smallexample | |
| 1459 (setq trees '((pine . cones) (oak . acorns) (maple . seeds))) | |
| 1460 | |
| 1461 (rassq 'acorns trees) | |
| 1462 @result{} (oak . acorns) | |
| 1463 (rassq 'spores trees) | |
| 1464 @result{} nil | |
| 1465 @end smallexample | |
| 1466 | |
| 1467 Note that @code{rassq} cannot search for a value stored in the @sc{car} | |
| 1468 of the @sc{cdr} of an element: | |
| 1469 | |
| 1470 @smallexample | |
| 1471 (setq colors '((rose red) (lily white) (buttercup yellow))) | |
| 1472 | |
| 1473 (rassq 'white colors) | |
| 1474 @result{} nil | |
| 1475 @end smallexample | |
| 1476 | |
| 1477 In this case, the @sc{cdr} of the association @code{(lily white)} is not | |
| 1478 the symbol @code{white}, but rather the list @code{(white)}. This | |
| 1479 becomes clearer if the association is written in dotted pair notation: | |
| 1480 | |
| 1481 @smallexample | |
| 1482 (lily white) @equiv{} (lily . (white)) | |
| 1483 @end smallexample | |
| 1484 @end defun | |
| 1485 | |
| 1486 @defun remassoc key alist | |
| 1487 This function deletes by side effect any associations with key @var{key} | |
| 440 | 1488 in @var{alist}---i.e. it removes any elements from @var{alist} whose |
| 428 | 1489 @code{car} is @code{equal} to @var{key}. The modified @var{alist} is |
| 1490 returned. | |
| 1491 | |
| 1492 If the first member of @var{alist} has a @code{car} that is @code{equal} | |
| 1493 to @var{key}, there is no way to remove it by side effect; therefore, | |
| 1494 write @code{(setq foo (remassoc key foo))} to be sure of changing the | |
| 1495 value of @code{foo}. | |
| 1496 @end defun | |
| 1497 | |
| 1498 @defun remassq key alist | |
| 1499 This function deletes by side effect any associations with key @var{key} | |
| 440 | 1500 in @var{alist}---i.e. it removes any elements from @var{alist} whose |
| 428 | 1501 @code{car} is @code{eq} to @var{key}. The modified @var{alist} is |
| 1502 returned. | |
| 1503 | |
| 1504 This function is exactly like @code{remassoc}, but comparisons between | |
| 1505 @var{key} and keys in @var{alist} are done using @code{eq} instead of | |
| 1506 @code{equal}. | |
| 1507 @end defun | |
| 1508 | |
| 1509 @defun remrassoc value alist | |
| 1510 This function deletes by side effect any associations with value @var{value} | |
| 440 | 1511 in @var{alist}---i.e. it removes any elements from @var{alist} whose |
| 428 | 1512 @code{cdr} is @code{equal} to @var{value}. The modified @var{alist} is |
| 1513 returned. | |
| 1514 | |
| 1515 If the first member of @var{alist} has a @code{car} that is @code{equal} | |
| 1516 to @var{value}, there is no way to remove it by side effect; therefore, | |
| 1517 write @code{(setq foo (remassoc value foo))} to be sure of changing the | |
| 1518 value of @code{foo}. | |
| 1519 | |
| 1520 @code{remrassoc} is like @code{remassoc} except that it compares the | |
| 1521 @sc{cdr} of each @var{alist} association instead of the @sc{car}. You | |
| 1522 can think of this as ``reverse @code{remassoc}'', removing an association | |
| 1523 based on its value instead of its key. | |
| 1524 @end defun | |
| 1525 | |
| 1526 @defun remrassq value alist | |
| 1527 This function deletes by side effect any associations with value @var{value} | |
| 440 | 1528 in @var{alist}---i.e. it removes any elements from @var{alist} whose |
| 428 | 1529 @code{cdr} is @code{eq} to @var{value}. The modified @var{alist} is |
| 1530 returned. | |
| 1531 | |
| 1532 This function is exactly like @code{remrassoc}, but comparisons between | |
| 1533 @var{value} and values in @var{alist} are done using @code{eq} instead of | |
| 1534 @code{equal}. | |
| 1535 @end defun | |
| 1536 | |
| 1537 @defun copy-alist alist | |
| 1538 @cindex copying alists | |
| 1539 This function returns a two-level deep copy of @var{alist}: it creates a | |
| 1540 new copy of each association, so that you can alter the associations of | |
| 1541 the new alist without changing the old one. | |
| 1542 | |
| 1543 @smallexample | |
| 1544 @group | |
| 1545 (setq needles-per-cluster | |
| 1546 '((2 . ("Austrian Pine" "Red Pine")) | |
| 1547 (3 . ("Pitch Pine")) | |
| 1548 @end group | |
| 1549 (5 . ("White Pine")))) | |
| 1550 @result{} | |
| 1551 ((2 "Austrian Pine" "Red Pine") | |
| 1552 (3 "Pitch Pine") | |
| 1553 (5 "White Pine")) | |
| 1554 | |
| 1555 (setq copy (copy-alist needles-per-cluster)) | |
| 1556 @result{} | |
| 1557 ((2 "Austrian Pine" "Red Pine") | |
| 1558 (3 "Pitch Pine") | |
| 1559 (5 "White Pine")) | |
| 1560 | |
| 1561 (eq needles-per-cluster copy) | |
| 1562 @result{} nil | |
| 1563 (equal needles-per-cluster copy) | |
| 1564 @result{} t | |
| 1565 (eq (car needles-per-cluster) (car copy)) | |
| 1566 @result{} nil | |
| 1567 (cdr (car (cdr needles-per-cluster))) | |
| 1568 @result{} ("Pitch Pine") | |
| 1569 @group | |
| 1570 (eq (cdr (car (cdr needles-per-cluster))) | |
| 1571 (cdr (car (cdr copy)))) | |
| 1572 @result{} t | |
| 1573 @end group | |
| 1574 @end smallexample | |
| 1575 | |
| 1576 This example shows how @code{copy-alist} makes it possible to change | |
| 1577 the associations of one copy without affecting the other: | |
| 1578 | |
| 1579 @smallexample | |
| 1580 @group | |
| 1581 (setcdr (assq 3 copy) '("Martian Vacuum Pine")) | |
| 1582 (cdr (assq 3 needles-per-cluster)) | |
| 1583 @result{} ("Pitch Pine") | |
| 1584 @end group | |
| 1585 @end smallexample | |
| 1586 @end defun | |
| 1587 | |
| 1588 @node Property Lists | |
| 1589 @section Property Lists | |
| 1590 @cindex property list | |
| 1591 @cindex plist | |
| 1592 | |
| 1593 A @dfn{property list} (or @dfn{plist}) is another way of representing a | |
| 1594 mapping from keys to values. Instead of the list consisting of conses | |
| 1595 of a key and a value, the keys and values alternate as successive | |
| 1596 entries in the list. Thus, the association list | |
| 1597 | |
| 1598 @example | |
| 1599 ((a . 1) (b . 2) (c . 3)) | |
| 1600 @end example | |
| 1601 | |
| 1602 has the equivalent property list form | |
| 1603 | |
| 1604 @example | |
| 1605 (a 1 b 2 c 3) | |
| 1606 @end example | |
| 1607 | |
| 1608 Property lists are used to represent the properties associated with | |
| 1609 various sorts of objects, such as symbols, strings, frames, etc. | |
| 1610 The convention is that property lists can be modified in-place, | |
| 1611 while association lists generally are not. | |
| 1612 | |
| 1613 Plists come in two varieties: @dfn{normal} plists, whose keys are | |
| 1614 compared with @code{eq}, and @dfn{lax} plists, whose keys are compared | |
| 1615 with @code{equal}, | |
| 1616 | |
| 1617 @defun valid-plist-p plist | |
| 1618 Given a plist, this function returns non-@code{nil} if its format is | |
| 1619 correct. If it returns @code{nil}, @code{check-valid-plist} will signal | |
| 1620 an error when given the plist; that means it's a malformed or circular | |
| 1621 plist or has non-symbols as keywords. | |
| 1622 @end defun | |
| 1623 | |
| 1624 @defun check-valid-plist plist | |
| 1625 Given a plist, this function signals an error if there is anything wrong | |
| 1626 with it. This means that it's a malformed or circular plist. | |
| 1627 @end defun | |
| 1628 | |
| 1629 @menu | |
| 1630 * Working With Normal Plists:: Functions for normal plists. | |
| 1631 * Working With Lax Plists:: Functions for lax plists. | |
| 1632 * Converting Plists To/From Alists:: Alist to plist and vice-versa. | |
| 1633 @end menu | |
| 1634 | |
| 1635 @node Working With Normal Plists | |
| 1636 @subsection Working With Normal Plists | |
| 1637 | |
| 444 | 1638 @defun plist-get plist property &optional default |
| 428 | 1639 This function extracts a value from a property list. The function |
| 444 | 1640 returns the value corresponding to the given @var{property}, or |
| 1641 @var{default} if @var{property} is not one of the properties on the list. | |
| 428 | 1642 @end defun |
| 1643 | |
| 444 | 1644 @defun plist-put plist property value |
| 1645 This function changes the value in @var{plist} of @var{property} to | |
| 1646 @var{value}. If @var{property} is already a property on the list, its value is | |
| 1647 set to @var{value}, otherwise the new @var{property} @var{value} pair is added. | |
| 1648 The new plist is returned; use @code{(setq x (plist-put x property value))} to | |
| 428 | 1649 be sure to use the new value. The @var{plist} is modified by side |
| 1650 effects. | |
| 1651 @end defun | |
| 1652 | |
| 444 | 1653 @defun plist-remprop plist property |
| 1654 This function removes from @var{plist} the property @var{property} and its | |
| 428 | 1655 value. The new plist is returned; use @code{(setq x (plist-remprop x |
| 444 | 1656 property))} to be sure to use the new value. The @var{plist} is |
| 428 | 1657 modified by side effects. |
| 1658 @end defun | |
| 1659 | |
| 444 | 1660 @defun plist-member plist property |
| 1661 This function returns @code{t} if @var{property} has a value specified in | |
| 428 | 1662 @var{plist}. |
| 1663 @end defun | |
| 1664 | |
| 1665 In the following functions, if optional arg @var{nil-means-not-present} | |
| 1666 is non-@code{nil}, then a property with a @code{nil} value is ignored or | |
| 1667 removed. This feature is a virus that has infected old Lisp | |
| 1668 implementations (and thus E-Lisp, due to @sc{rms}'s enamorment with old | |
| 1669 Lisps), but should not be used except for backward compatibility. | |
| 1670 | |
| 1671 @defun plists-eq a b &optional nil-means-not-present | |
| 1672 This function returns non-@code{nil} if property lists A and B are | |
| 1673 @code{eq} (i.e. their values are @code{eq}). | |
| 1674 @end defun | |
| 1675 | |
| 1676 @defun plists-equal a b &optional nil-means-not-present | |
| 1677 This function returns non-@code{nil} if property lists A and B are | |
| 1678 @code{equal} (i.e. their values are @code{equal}; their keys are | |
| 1679 still compared using @code{eq}). | |
| 1680 @end defun | |
| 1681 | |
| 1682 @defun canonicalize-plist plist &optional nil-means-not-present | |
| 1683 This function destructively removes any duplicate entries from a plist. | |
| 1684 In such cases, the first entry applies. | |
| 1685 | |
| 1686 The new plist is returned. If @var{nil-means-not-present} is given, the | |
| 1687 return value may not be @code{eq} to the passed-in value, so make sure | |
| 1688 to @code{setq} the value back into where it came from. | |
| 1689 @end defun | |
| 1690 | |
| 1691 @node Working With Lax Plists | |
| 1692 @subsection Working With Lax Plists | |
| 1693 | |
| 1694 Recall that a @dfn{lax plist} is a property list whose keys are compared | |
| 1695 using @code{equal} instead of @code{eq}. | |
| 1696 | |
| 444 | 1697 @defun lax-plist-get lax-plist property &optional default |
| 428 | 1698 This function extracts a value from a lax property list. The function |
| 444 | 1699 returns the value corresponding to the given @var{property}, or |
| 1700 @var{default} if @var{property} is not one of the properties on the list. | |
| 428 | 1701 @end defun |
| 1702 | |
| 444 | 1703 @defun lax-plist-put lax-plist property value |
| 1704 This function changes the value in @var{lax-plist} of @var{property} to @var{value}. | |
| 428 | 1705 @end defun |
| 1706 | |
| 444 | 1707 @defun lax-plist-remprop lax-plist property |
| 1708 This function removes from @var{lax-plist} the property @var{property} and | |
| 428 | 1709 its value. The new plist is returned; use @code{(setq x |
| 444 | 1710 (lax-plist-remprop x property))} to be sure to use the new value. The |
| 428 | 1711 @var{lax-plist} is modified by side effects. |
| 1712 @end defun | |
| 1713 | |
| 444 | 1714 @defun lax-plist-member lax-plist property |
| 1715 This function returns @code{t} if @var{property} has a value specified in | |
| 428 | 1716 @var{lax-plist}. |
| 1717 @end defun | |
| 1718 | |
| 1719 In the following functions, if optional arg @var{nil-means-not-present} | |
| 1720 is non-@code{nil}, then a property with a @code{nil} value is ignored or | |
| 1721 removed. This feature is a virus that has infected old Lisp | |
| 1722 implementations (and thus E-Lisp, due to @sc{rms}'s enamorment with old | |
| 1723 Lisps), but should not be used except for backward compatibility. | |
| 1724 | |
| 1725 @defun lax-plists-eq a b &optional nil-means-not-present | |
| 1726 This function returns non-@code{nil} if lax property lists A and B are | |
| 1727 @code{eq} (i.e. their values are @code{eq}; their keys are still | |
| 1728 compared using @code{equal}). | |
| 1729 @end defun | |
| 1730 | |
| 1731 @defun lax-plists-equal a b &optional nil-means-not-present | |
| 1732 This function returns non-@code{nil} if lax property lists A and B are | |
| 1733 @code{equal} (i.e. their values are @code{equal}). | |
| 1734 @end defun | |
| 1735 | |
| 1736 @defun canonicalize-lax-plist lax-plist &optional nil-means-not-present | |
| 1737 This function destructively removes any duplicate entries from a lax | |
| 1738 plist. In such cases, the first entry applies. | |
| 1739 | |
| 1740 The new plist is returned. If @var{nil-means-not-present} is given, the | |
| 1741 return value may not be @code{eq} to the passed-in value, so make sure | |
| 1742 to @code{setq} the value back into where it came from. | |
| 1743 @end defun | |
| 1744 | |
| 1745 @node Converting Plists To/From Alists | |
| 1746 @subsection Converting Plists To/From Alists | |
| 1747 | |
| 1748 @defun alist-to-plist alist | |
| 1749 This function converts association list @var{alist} into the equivalent | |
| 1750 property-list form. The plist is returned. This converts from | |
| 1751 | |
| 1752 @example | |
| 1753 ((a . 1) (b . 2) (c . 3)) | |
| 1754 @end example | |
| 1755 | |
| 1756 into | |
| 1757 | |
| 1758 @example | |
| 1759 (a 1 b 2 c 3) | |
| 1760 @end example | |
| 1761 | |
| 1762 The original alist is not modified. | |
| 1763 @end defun | |
| 1764 | |
| 1765 @defun plist-to-alist plist | |
| 1766 This function converts property list @var{plist} into the equivalent | |
| 1767 association-list form. The alist is returned. This converts from | |
| 1768 | |
| 1769 @example | |
| 1770 (a 1 b 2 c 3) | |
| 1771 @end example | |
| 1772 | |
| 1773 into | |
| 1774 | |
| 1775 @example | |
| 1776 ((a . 1) (b . 2) (c . 3)) | |
| 1777 @end example | |
| 1778 | |
| 1779 The original plist is not modified. | |
| 1780 @end defun | |
| 1781 | |
| 1782 The following two functions are equivalent to the preceding two except | |
| 1783 that they destructively modify their arguments, using cons cells from | |
| 1784 the original list to form the new list rather than allocating new | |
| 1785 cons cells. | |
| 1786 | |
| 1787 @defun destructive-alist-to-plist alist | |
| 1788 This function destructively converts association list @var{alist} into | |
| 1789 the equivalent property-list form. The plist is returned. | |
| 1790 @end defun | |
| 1791 | |
| 1792 @defun destructive-plist-to-alist plist | |
| 1793 This function destructively converts property list @var{plist} into the | |
| 1794 equivalent association-list form. The alist is returned. | |
| 1795 @end defun | |
| 1796 | |
| 1797 @node Weak Lists | |
| 1798 @section Weak Lists | |
| 1799 @cindex weak list | |
| 1800 | |
| 1801 A @dfn{weak list} is a special sort of list whose members are not counted | |
| 1802 as references for the purpose of garbage collection. This means that, | |
| 1803 for any object in the list, if there are no references to the object | |
| 1804 anywhere outside of the list (or other weak list or weak hash table), | |
| 1805 that object will disappear the next time a garbage collection happens. | |
| 1806 Weak lists can be useful for keeping track of things such as unobtrusive | |
| 1807 lists of another function's buffers or markers. When that function is | |
| 1808 done with the elements, they will automatically disappear from the list. | |
| 1809 | |
| 1810 Weak lists are used internally, for example, to manage the list holding | |
| 440 | 1811 the children of an extent---an extent that is unused but has a parent |
| 428 | 1812 will still be reclaimed, and will automatically be removed from its |
| 1813 parent's list of children. | |
| 1814 | |
| 1815 Weak lists are similar to weak hash tables (@pxref{Weak Hash Tables}). | |
| 1816 | |
| 1817 @defun weak-list-p object | |
| 1818 This function returns non-@code{nil} if @var{object} is a weak list. | |
| 1819 @end defun | |
| 1820 | |
| 1821 Weak lists come in one of four types: | |
| 1822 | |
| 1823 @table @code | |
| 1824 @item simple | |
| 1825 Objects in the list disappear if not referenced outside of the list. | |
| 1826 | |
| 1827 @item assoc | |
| 1828 Objects in the list disappear if they are conses and either the car or | |
| 1829 the cdr of the cons is not referenced outside of the list. | |
| 1830 | |
| 1831 @item key-assoc | |
| 1832 Objects in the list disappear if they are conses and the car is not | |
| 1833 referenced outside of the list. | |
| 1834 | |
| 1835 @item value-assoc | |
| 1836 Objects in the list disappear if they are conses and the cdr is not | |
| 1837 referenced outside of the list. | |
| 1838 @end table | |
| 1839 | |
| 1840 @defun make-weak-list &optional type | |
| 1841 This function creates a new weak list of type @var{type}. @var{type} is | |
| 1842 a symbol (one of @code{simple}, @code{assoc}, @code{key-assoc}, or | |
| 1843 @code{value-assoc}, as described above) and defaults to @code{simple}. | |
| 1844 @end defun | |
| 1845 | |
| 1846 @defun weak-list-type weak | |
| 1847 This function returns the type of the given weak-list object. | |
| 1848 @end defun | |
| 1849 | |
| 1850 @defun weak-list-list weak | |
| 1851 This function returns the list contained in a weak-list object. | |
| 1852 @end defun | |
| 1853 | |
| 1854 @defun set-weak-list-list weak new-list | |
| 1855 This function changes the list contained in a weak-list object. | |
| 1856 @end defun |