2 @c This is part of the SXEmacs Lisp Reference Manual.
3 @c Copyright (C) 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc.
4 @c Copyright (C) 2005, 2006 Sebastian Freundt <hroptatyr@sxemacs.org>
5 @c See the file lispref.texi for copying conditions.
6 @setfilename ../../info/lists.info
8 @node Lists, Sequences Arrays Vectors, Strings and Characters, Top
11 @cindex element (of list)
13 A @dfn{list} represents a sequence of zero or more elements (which may
14 be any Lisp objects). The important difference between lists and
15 vectors is that two or more lists can share part of their structure; in
16 addition, you can insert or delete elements in a list without copying
20 * Cons Cells:: How lists are made out of cons cells.
21 * Lists as Boxes:: Graphical notation to explain lists.
22 * List-related Predicates:: Is this object a list? Comparing two lists.
23 * List Elements:: Extracting the pieces of a list.
24 * Building Lists:: Creating list structure.
25 * Modifying Lists:: Storing new pieces into an existing list.
26 * Sets And Lists:: A list can represent a finite mathematical set.
27 * Association Lists:: A list can represent a finite relation or mapping.
28 * Property Lists:: A different way to represent a finite mapping.
29 * Skip Lists:: Very efficient dictionary data type.
30 * Weak Lists:: A list with special garbage-collection behavior.
31 * DL-Lists:: A doubly-linked list implementation.
32 * Bloom Filters:: A special set type with anonymous membership.
37 @section Lists and Cons Cells
38 @cindex lists and cons cells
39 @cindex @code{nil} and lists
41 Lists in Lisp are not a primitive data type; they are built up from
42 @dfn{cons cells}. A cons cell is a data object that represents an
43 ordered pair. It records two Lisp objects, one labeled as the @sc{car},
44 and the other labeled as the @sc{cdr}. These names are traditional; see
45 @ref{Cons Cell Type}. @sc{cdr} is pronounced ``could-er.''
47 A list is a series of cons cells chained together, one cons cell per
48 element of the list. By convention, the @sc{car}s of the cons cells are
49 the elements of the list, and the @sc{cdr}s are used to chain the list:
50 the @sc{cdr} of each cons cell is the following cons cell. The @sc{cdr}
51 of the last cons cell is @code{nil}. This asymmetry between the
52 @sc{car} and the @sc{cdr} is entirely a matter of convention; at the
53 level of cons cells, the @sc{car} and @sc{cdr} slots have the same
56 @cindex list structure
57 Because most cons cells are used as part of lists, the phrase
58 @dfn{list structure} has come to mean any structure made out of cons
61 The symbol @code{nil} is considered a list as well as a symbol; it is
62 the list with no elements. For convenience, the symbol @code{nil} is
63 considered to have @code{nil} as its @sc{cdr} (and also as its
66 The @sc{cdr} of any nonempty list @var{l} is a list containing all the
67 elements of @var{l} except the first.
71 @section Lists as Linked Pairs of Boxes
72 @cindex box representation for lists
73 @cindex lists represented as boxes
74 @cindex cons cell as box
76 A cons cell can be illustrated as a pair of boxes. The first box
77 represents the @sc{car} and the second box represents the @sc{cdr}.
78 Here is an illustration of the two-element list, @code{(tulip lily)},
79 made from two cons cells:
83 --------------- ---------------
84 | car | cdr | | car | cdr |
85 | tulip | o---------->| lily | nil |
87 --------------- ---------------
91 Each pair of boxes represents a cons cell. Each box ``refers to'',
92 ``points to'' or ``contains'' a Lisp object. (These terms are
93 synonymous.) The first box, which is the @sc{car} of the first cons
94 cell, contains the symbol @code{tulip}. The arrow from the @sc{cdr} of
95 the first cons cell to the second cons cell indicates that the @sc{cdr}
96 of the first cons cell points to the second cons cell.
98 The same list can be illustrated in a different sort of box notation
104 |___|___|--> |___|___|--> nil
111 Here is a more complex illustration, showing the three-element list,
112 @code{((pine needles) oak maple)}, the first element of which is a
117 ___ ___ ___ ___ ___ ___
118 |___|___|--> |___|___|--> |___|___|--> nil
124 --> |___|___|--> |___|___|--> nil
131 The same list represented in the first box notation looks like this:
135 -------------- -------------- --------------
136 | car | cdr | | car | cdr | | car | cdr |
137 | o | o------->| oak | o------->| maple | nil |
139 -- | --------- -------------- --------------
142 | -------------- ----------------
143 | | car | cdr | | car | cdr |
144 ------>| pine | o------->| needles | nil |
146 -------------- ----------------
150 @xref{Cons Cell Type}, for the read and print syntax of cons cells and
151 lists, and for more ``box and arrow'' illustrations of lists.
154 @node List-related Predicates
155 @section Predicates on Lists
157 The following predicates test whether a Lisp object is an atom, is a
158 cons cell or is a list, or whether it is the distinguished object
159 @code{nil}. (Many of these predicates can be defined in terms of the
160 others, but they are used so often that it is worth having all of them.)
163 This function returns @code{t} if @var{object} is a cons cell, @code{nil}
164 otherwise. @code{nil} is not a cons cell, although it @emph{is} a list.
169 This function returns @code{t} if @var{object} is an atom, @code{nil}
170 otherwise. All objects except cons cells are atoms. The symbol
171 @code{nil} is an atom and is also a list; it is the only Lisp object
175 (atom @var{object}) @equiv{} (not (consp @var{object}))
180 This function returns @code{t} if @var{object} is a cons cell or
181 @code{nil}. Otherwise, it returns @code{nil}.
196 This function is the opposite of @code{listp}: it returns @code{t} if
197 @var{object} is not a list. Otherwise, it returns @code{nil}.
200 (listp @var{object}) @equiv{} (not (nlistp @var{object}))
205 This function returns @code{t} if @var{object} is @code{nil}, and
206 returns @code{nil} otherwise. This function is identical to @code{not},
207 but as a matter of clarity we use @code{null} when @var{object} is
208 considered a list and @code{not} when it is considered a truth value
209 (see @code{not} in @ref{Combining Conditions}).
227 @section Accessing Elements of Lists
228 @cindex list elements
231 This function returns the value pointed to by the first pointer of the
232 cons cell @var{cons-cell}. Expressed another way, this function
233 returns the @sc{car} of @var{cons-cell}.
235 As a special case, if @var{cons-cell} is @code{nil}, then @code{car}
236 is defined to return @code{nil}; therefore, any list is a valid argument
237 for @code{car}. An error is signaled if the argument is not a cons cell
253 This function returns the value pointed to by the second pointer of
254 the cons cell @var{cons-cell}. Expressed another way, this function
255 returns the @sc{cdr} of @var{cons-cell}.
257 As a special case, if @var{cons-cell} is @code{nil}, then @code{cdr}
258 is defined to return @code{nil}; therefore, any list is a valid argument
259 for @code{cdr}. An error is signaled if the argument is not a cons cell
274 @defun car-safe object
275 This function lets you take the @sc{car} of a cons cell while avoiding
276 errors for other data types. It returns the @sc{car} of @var{object} if
277 @var{object} is a cons cell, @code{nil} otherwise. This is in contrast
278 to @code{car}, which signals an error if @var{object} is not a list.
282 (car-safe @var{object})
284 (let ((x @var{object}))
292 @defun cdr-safe object
293 This function lets you take the @sc{cdr} of a cons cell while
294 avoiding errors for other data types. It returns the @sc{cdr} of
295 @var{object} if @var{object} is a cons cell, @code{nil} otherwise.
296 This is in contrast to @code{cdr}, which signals an error if
297 @var{object} is not a list.
301 (cdr-safe @var{object})
303 (let ((x @var{object}))
312 This function returns the @var{n}th element of @var{list}. Elements
313 are numbered starting with zero, so the @sc{car} of @var{list} is
314 element number zero. If the length of @var{list} is @var{n} or less,
315 the value is @code{nil}.
317 If @var{n} is negative, @code{nth} returns the first element of
333 (nth n x) @equiv{} (car (nthcdr n x))
339 This function returns the @var{n}th @sc{cdr} of @var{list}. In other
340 words, it removes the first @var{n} links of @var{list} and returns
343 If @var{n} is zero or negative, @code{nthcdr} returns all of
344 @var{list}. If the length of @var{list} is @var{n} or less,
345 @code{nthcdr} returns @code{nil}.
349 (nthcdr 1 '(1 2 3 4))
353 (nthcdr 10 '(1 2 3 4))
357 (nthcdr -3 '(1 2 3 4))
363 Many convenience functions are provided to make it easier for you to
364 access particular elements in a nested list. All of these can be
365 rewritten in terms of the functions just described.
367 @defun caar cons-cell
368 @defunx cadr cons-cell
369 @defunx cdar cons-cell
370 @defunx cddr cons-cell
371 @defunx caaar cons-cell
372 @defunx caadr cons-cell
373 @defunx cadar cons-cell
374 @defunx caddr cons-cell
375 @defunx cdaar cons-cell
376 @defunx cdadr cons-cell
377 @defunx cddar cons-cell
378 @defunx cdddr cons-cell
379 @defunx caaaar cons-cell
380 @defunx caaadr cons-cell
381 @defunx caadar cons-cell
382 @defunx caaddr cons-cell
383 @defunx cadaar cons-cell
384 @defunx cadadr cons-cell
385 @defunx caddar cons-cell
386 @defunx cadddr cons-cell
387 @defunx cdaaar cons-cell
388 @defunx cdaadr cons-cell
389 @defunx cdadar cons-cell
390 @defunx cdaddr cons-cell
391 @defunx cddaar cons-cell
392 @defunx cddadr cons-cell
393 @defunx cdddar cons-cell
394 @defunx cddddr cons-cell
395 Each of these functions is equivalent to one or more applications of
396 @code{car} and/or @code{cdr}. For example,
417 (cdr (car (cdr (cdr x))))
420 That is to say, read the a's and d's from right to left and apply
421 a @code{car} or @code{cdr} for each a or d found, respectively.
425 This is equivalent to @code{(nth 0 @var{list})}, i.e. the first element
426 of @var{list}. (Note that this is also equivalent to @code{car}.)
430 This is equivalent to @code{(nth 1 @var{list})}, i.e. the second element
442 These are equivalent to @code{(nth 2 @var{list})} through
443 @code{(nth 9 @var{list})} respectively, i.e. the third through tenth
444 elements of @var{list}.
449 @section Building Cons Cells and Lists
451 @cindex building lists
453 Many functions build lists, as lists reside at the very heart of Lisp.
454 @code{cons} is the fundamental list-building function; however, it is
455 interesting to note that @code{list} is used more times in the source
456 code for SXEmacs than @code{cons}.
458 @defun cons object1 object2
459 This function is the fundamental function used to build new list
460 structure. It creates a new cons cell, making @var{object1} the
461 @sc{car}, and @var{object2} the @sc{cdr}. It then returns the new cons
462 cell. The arguments @var{object1} and @var{object2} may be any Lisp
463 objects, but most often @var{object2} is a list.
481 @code{cons} is often used to add a single element to the front of a
482 list. This is called @dfn{consing the element onto the list}. For
486 (setq list (cons newelt list))
489 Note that there is no conflict between the variable named @code{list}
490 used in this example and the function named @code{list} described below;
491 any symbol can serve both purposes.
494 @defun list &rest objects
495 This function creates a list with @var{objects} as its elements. The
496 resulting list is always @code{nil}-terminated. If no @var{objects}
497 are given, the empty list is returned.
502 @result{} (1 2 3 4 5)
505 (list 1 2 '(3 4 5) 'foo)
506 @result{} (1 2 (3 4 5) foo)
515 @defun make-list length object
516 This function creates a list of length @var{length}, in which all the
517 elements have the identical value @var{object}. Compare
518 @code{make-list} with @code{make-string} (@pxref{Creating Strings}).
523 @result{} (pigs pigs pigs)
532 @defun append &rest sequences
533 @cindex copying lists
534 This function returns a list containing all the elements of
535 @var{sequences}. The @var{sequences} may be lists, vectors, or strings,
536 but the last one should be a list. All arguments except the last one
537 are copied, so none of them are altered.
539 More generally, the final argument to @code{append} may be any Lisp
540 object. The final argument is not copied or converted; it becomes the
541 @sc{cdr} of the last cons cell in the new list. If the final argument
542 is itself a list, then its elements become in effect elements of the
543 result list. If the final element is not a list, the result is a
544 ``dotted list'' since its final @sc{cdr} is not @code{nil} as required
547 See @code{nconc} in @ref{Rearrangement}, for a way to join lists with no
550 Here is an example of using @code{append}:
554 (setq trees '(pine oak))
556 (setq more-trees (append '(maple birch) trees))
557 @result{} (maple birch pine oak)
564 @result{} (maple birch pine oak)
567 (eq trees (cdr (cdr more-trees)))
572 You can see how @code{append} works by looking at a box diagram. The
573 variable @code{trees} is set to the list @code{(pine oak)} and then the
574 variable @code{more-trees} is set to the list @code{(maple birch pine
575 oak)}. However, the variable @code{trees} continues to refer to the
582 | ___ ___ ___ ___ -> ___ ___ ___ ___
583 --> |___|___|--> |___|___|--> |___|___|--> |___|___|--> nil
586 --> maple -->birch --> pine --> oak
590 An empty sequence contributes nothing to the value returned by
591 @code{append}. As a consequence of this, a final @code{nil} argument
592 forces a copy of the previous argument.
600 (setq wood (append trees ()))
614 This once was the usual way to copy a list, before the function
615 @code{copy-sequence} was invented. @xref{Sequences Arrays Vectors}.
617 With the help of @code{apply}, we can append all the lists in a list of
622 (apply 'append '((a b c) nil (x y z) nil))
623 @result{} (a b c x y z)
627 If no @var{sequences} are given, @code{nil} is returned:
636 Here are some examples where the final argument is not a list:
642 @result{} (x y . [z])
646 The second example shows that when the final argument is a sequence but
647 not a list, the sequence's elements do not become elements of the
648 resulting list. Instead, the sequence becomes the final @sc{cdr}, like
649 any other non-list final argument.
651 The @code{append} function also allows integers as arguments. It
652 converts them to strings of digits, making up the decimal print
653 representation of the integer, and then uses the strings instead of the
654 original integers. @strong{Don't use this feature; we plan to eliminate
655 it. If you already use this feature, change your programs now!} The
656 proper way to convert an integer to a decimal number in this way is with
657 @code{format} (@pxref{Formatting Strings}) or @code{number-to-string}
658 (@pxref{String Conversion}).
662 This function creates a new list whose elements are the elements of
663 @var{list}, but in reverse order. The original argument @var{list} is
681 @node Modifying Lists
682 @section Modifying Existing List Structure
684 You can modify the @sc{car} and @sc{cdr} contents of a cons cell with the
685 primitives @code{setcar} and @code{setcdr}.
687 @cindex CL note---@code{rplaca} vrs @code{setcar}
691 @b{Common Lisp note:} Common Lisp uses functions @code{rplaca} and
692 @code{rplacd} to alter list structure; they change structure the same
693 way as @code{setcar} and @code{setcdr}, but the Common Lisp functions
694 return the cons cell while @code{setcar} and @code{setcdr} return the
695 new @sc{car} or @sc{cdr}.
699 * Setcar:: Replacing an element in a list.
700 * Setcdr:: Replacing part of the list backbone.
701 This can be used to remove or add elements.
702 * Rearrangement:: Reordering the elements in a list; combining lists.
707 @subsection Altering List Elements with @code{setcar}
709 Changing the @sc{car} of a cons cell is done with @code{setcar}. When
710 used on a list, @code{setcar} replaces one element of a list with a
713 @defun setcar cons-cell object
714 This function stores @var{object} as the new @sc{car} of @var{cons-cell},
715 replacing its previous @sc{car}. It returns the value @var{object}.
734 When a cons cell is part of the shared structure of several lists,
735 storing a new @sc{car} into the cons changes one element of each of
736 these lists. Here is an example:
740 ;; @r{Create two lists that are partly shared.}
743 (setq x2 (cons 'z (cdr x1)))
748 ;; @r{Replace the @sc{car} of a shared link.}
749 (setcar (cdr x1) 'foo)
751 x1 ; @r{Both lists are changed.}
758 ;; @r{Replace the @sc{car} of a link that is not shared.}
761 x1 ; @r{Only one list is changed.}
762 @result{} (baz foo c)
768 Here is a graphical depiction of the shared structure of the two lists
769 in the variables @code{x1} and @code{x2}, showing why replacing @code{b}
774 ___ ___ ___ ___ ___ ___
775 x1---> |___|___|----> |___|___|--> |___|___|--> nil
788 Here is an alternative form of box diagram, showing the same relationship:
793 -------------- -------------- --------------
794 | car | cdr | | car | cdr | | car | cdr |
795 | a | o------->| b | o------->| c | nil |
797 -------------- | -------------- --------------
810 @subsection Altering the CDR of a List
812 The lowest-level primitive for modifying a @sc{cdr} is @code{setcdr}:
814 @defun setcdr cons-cell object
815 This function stores @var{object} as the new @sc{cdr} of @var{cons-cell},
816 replacing its previous @sc{cdr}. It returns the value @var{object}.
819 Here is an example of replacing the @sc{cdr} of a list with a
820 different list. All but the first element of the list are removed in
821 favor of a different sequence of elements. The first element is
822 unchanged, because it resides in the @sc{car} of the list, and is not
823 reached via the @sc{cdr}.
840 You can delete elements from the middle of a list by altering the
841 @sc{cdr}s of the cons cells in the list. For example, here we delete
842 the second element, @code{b}, from the list @code{(a b c)}, by changing
843 the @sc{cdr} of the first cell:
849 (setcdr x1 (cdr (cdr x1)))
857 Here is the result in box notation:
863 -------------- | -------------- | --------------
864 | car | cdr | | | car | cdr | -->| car | cdr |
865 | a | o----- | b | o-------->| c | nil |
867 -------------- -------------- --------------
872 The second cons cell, which previously held the element @code{b}, still
873 exists and its @sc{car} is still @code{b}, but it no longer forms part
876 It is equally easy to insert a new element by changing @sc{cdr}s:
882 (setcdr x1 (cons 'd (cdr x1)))
889 Here is this result in box notation:
893 -------------- ------------- -------------
894 | car | cdr | | car | cdr | | car | cdr |
895 | a | o | -->| b | o------->| c | nil |
896 | | | | | | | | | | |
897 --------- | -- | ------------- -------------
911 @subsection Functions that Rearrange Lists
912 @cindex rearrangement of lists
913 @cindex modification of lists
915 Here are some functions that rearrange lists ``destructively'' by
916 modifying the @sc{cdr}s of their component cons cells. We call these
917 functions ``destructive'' because they chew up the original lists passed
918 to them as arguments, to produce a new list that is the returned value.
921 See @code{delq}, in @ref{Sets And Lists}, for another function
922 that modifies cons cells.
925 The function @code{delq} in the following section is another example
926 of destructive list manipulation.
929 @defun nconc &rest lists
930 @cindex concatenating lists
931 @cindex joining lists
932 This function returns a list containing all the elements of @var{lists}.
933 Unlike @code{append} (@pxref{Building Lists}), the @var{lists} are
934 @emph{not} copied. Instead, the last @sc{cdr} of each of the
935 @var{lists} is changed to refer to the following list. The last of the
936 @var{lists} is not altered. For example:
945 @result{} (1 2 3 4 5)
949 @result{} (1 2 3 4 5)
953 Since the last argument of @code{nconc} is not itself modified, it is
954 reasonable to use a constant list, such as @code{'(4 5)}, as in the
955 above example. For the same reason, the last argument need not be a
965 @result{} (1 2 3 . z)
969 @result{} (1 2 3 . z)
973 A common pitfall is to use a quoted constant list as a non-last
974 argument to @code{nconc}. If you do this, your program will change
975 each time you run it! Here is what happens:
979 (defun add-foo (x) ; @r{We want this function to add}
980 (nconc '(foo) x)) ; @r{@code{foo} to the front of its arg.}
984 (symbol-function 'add-foo)
985 @result{} (lambda (x) (nconc (quote (foo)) x))
989 (setq xx (add-foo '(1 2))) ; @r{It seems to work.}
993 (setq xy (add-foo '(3 4))) ; @r{What happened?}
994 @result{} (foo 1 2 3 4)
1002 (symbol-function 'add-foo)
1003 @result{} (lambda (x) (nconc (quote (foo 1 2 3 4) x)))
1008 @defun nreverse list
1009 @cindex reversing a list
1010 This function reverses the order of the elements of @var{list}.
1011 Unlike @code{reverse}, @code{nreverse} alters its argument by reversing
1012 the @sc{cdr}s in the cons cells forming the list. The cons cell that
1013 used to be the last one in @var{list} becomes the first cell of the
1030 ;; @r{The cell that was first is now last.}
1036 To avoid confusion, we usually store the result of @code{nreverse}
1037 back in the same variable which held the original list:
1040 (setq x (nreverse x))
1043 Here is the @code{nreverse} of our favorite example, @code{(a b c)},
1044 presented graphically:
1048 @r{Original list head:} @r{Reversed list:}
1049 ------------- ------------- ------------
1050 | car | cdr | | car | cdr | | car | cdr |
1051 | a | nil |<-- | b | o |<-- | c | o |
1052 | | | | | | | | | | | | |
1053 ------------- | --------- | - | -------- | -
1055 ------------- ------------
1060 @defun sort list predicate
1062 @cindex sorting lists
1063 This function sorts @var{list} stably, though destructively, and
1064 returns the sorted list. It compares elements using @var{predicate}. A
1065 stable sort is one in which elements with equal sort keys maintain their
1066 relative order before and after the sort. Stability is important when
1067 successive sorts are used to order elements according to different
1070 The argument @var{predicate} must be a function that accepts two
1071 arguments. It is called with two elements of @var{list}. To get an
1072 increasing order sort, the @var{predicate} should return @code{t} if the
1073 first element is ``less than'' the second, or @code{nil} if not.
1075 The destructive aspect of @code{sort} is that it rearranges the cons
1076 cells forming @var{list} by changing @sc{cdr}s. A nondestructive sort
1077 function would create new cons cells to store the elements in their
1078 sorted order. If you wish to make a sorted copy without destroying the
1079 original, copy it first with @code{copy-sequence} and then sort.
1081 Sorting does not change the @sc{car}s of the cons cells in @var{list};
1082 the cons cell that originally contained the element @code{a} in
1083 @var{list} still has @code{a} in its @sc{car} after sorting, but it now
1084 appears in a different position in the list due to the change of
1085 @sc{cdr}s. For example:
1089 (setq nums '(1 3 2 6 5 4 0))
1090 @result{} (1 3 2 6 5 4 0)
1094 @result{} (0 1 2 3 4 5 6)
1098 @result{} (1 2 3 4 5 6)
1103 Note that the list in @code{nums} no longer contains 0; this is the same
1104 cons cell that it was before, but it is no longer the first one in the
1105 list. Don't assume a variable that formerly held the argument now holds
1106 the entire sorted list! Instead, save the result of @code{sort} and use
1107 that. Most often we store the result back into the variable that held
1111 (setq nums (sort nums '<))
1114 @xref{Sorting}, for more functions that perform sorting.
1115 See @code{documentation} in @ref{Accessing Documentation}, for a
1116 useful example of @code{sort}.
1120 @node Sets And Lists
1121 @section Using Lists as Sets
1122 @cindex lists as sets
1125 A list can represent an unordered mathematical set---simply consider a
1126 value an element of a set if it appears in the list, and ignore the
1127 order of the list. To form the union of two sets, use @code{append} (as
1128 long as you don't mind having duplicate elements). Other useful
1129 functions for sets include @code{memq} and @code{delq}, and their
1130 @code{equal} versions, @code{member} and @code{delete}.
1132 @cindex CL note---lack @code{union}, @code{set}
1134 @b{Common Lisp note:} Common Lisp has functions @code{union} (which
1135 avoids duplicate elements) and @code{intersection} for set operations,
1136 but SXEmacs Lisp does not have them. You can write them in Lisp if
1140 @defun memq object list
1141 @cindex membership in a list
1142 This function tests to see whether @var{object} is a member of
1143 @var{list}. If it is, @code{memq} returns a list starting with the
1144 first occurrence of @var{object}. Otherwise, it returns @code{nil}.
1145 The letter @samp{q} in @code{memq} says that it uses @code{eq} to
1146 compare @var{object} against the elements of the list. For example:
1150 (memq 'b '(a b c b a))
1154 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1160 @defun delq object list
1161 @cindex deletion of elements
1162 This function destructively removes all elements @code{eq} to
1163 @var{object} from @var{list}. The letter @samp{q} in @code{delq} says
1164 that it uses @code{eq} to compare @var{object} against the elements of
1165 the list, like @code{memq}.
1168 When @code{delq} deletes elements from the front of the list, it does so
1169 simply by advancing down the list and returning a sublist that starts
1170 after those elements:
1174 (delq 'a '(a b c)) @equiv{} (cdr '(a b c))
1178 When an element to be deleted appears in the middle of the list,
1179 removing it involves changing the @sc{cdr}s (@pxref{Setcdr}).
1183 (setq sample-list '(a b c (4)))
1184 @result{} (a b c (4))
1187 (delq 'a sample-list)
1192 @result{} (a b c (4))
1195 (delq 'c sample-list)
1204 Note that @code{(delq 'c sample-list)} modifies @code{sample-list} to
1205 splice out the third element, but @code{(delq 'a sample-list)} does not
1206 splice anything---it just returns a shorter list. Don't assume that a
1207 variable which formerly held the argument @var{list} now has fewer
1208 elements, or that it still holds the original list! Instead, save the
1209 result of @code{delq} and use that. Most often we store the result back
1210 into the variable that held the original list:
1213 (setq flowers (delq 'rose flowers))
1216 In the following example, the @code{(4)} that @code{delq} attempts to match
1217 and the @code{(4)} in the @code{sample-list} are not @code{eq}:
1221 (delq '(4) sample-list)
1226 The following two functions are like @code{memq} and @code{delq} but use
1227 @code{equal} rather than @code{eq} to compare elements. They are new in
1230 @defun member object list
1231 The function @code{member} tests to see whether @var{object} is a member
1232 of @var{list}, comparing members with @var{object} using @code{equal}.
1233 If @var{object} is a member, @code{member} returns a list starting with
1234 its first occurrence in @var{list}. Otherwise, it returns @code{nil}.
1236 Compare this with @code{memq}:
1240 (member '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are @code{equal}.}
1244 (memq '(2) '((1) (2))) ; @r{@code{(2)} and @code{(2)} are not @code{eq}.}
1248 ;; @r{Two strings with the same contents are @code{equal}.}
1249 (member "foo" '("foo" "bar"))
1250 @result{} ("foo" "bar")
1255 @defun delete object list
1256 This function destructively removes all elements @code{equal} to
1257 @var{object} from @var{list}. It is to @code{delq} as @code{member} is
1258 to @code{memq}: it uses @code{equal} to compare elements with
1259 @var{object}, like @code{member}; when it finds an element that matches,
1260 it removes the element just as @code{delq} would. For example:
1264 (delete '(2) '((2) (1) (2)))
1271 @b{Common Lisp note:} The functions @code{member} and @code{delete} in
1272 SXEmacs Lisp are derived from Maclisp, not Common Lisp. The Common
1273 Lisp versions do not use @code{equal} to compare elements.
1276 See also the function @code{add-to-list}, in @ref{Setting Variables},
1277 for another way to add an element to a list stored in a variable.
1280 @node Association Lists
1281 @section Association Lists
1282 @cindex association list
1285 An @dfn{association list}, or @dfn{alist} for short, records a mapping
1286 from keys to values. It is a list of cons cells called
1287 @dfn{associations}: the @sc{car} of each cell is the @dfn{key}, and the
1288 @sc{cdr} is the @dfn{associated value}.@footnote{This usage of ``key''
1289 is not related to the term ``key sequence''; it means a value used to
1290 look up an item in a table. In this case, the table is the alist, and
1291 the alist associations are the items.}
1293 Here is an example of an alist. The key @code{pine} is associated with
1294 the value @code{cones}; the key @code{oak} is associated with
1295 @code{acorns}; and the key @code{maple} is associated with @code{seeds}.
1305 The associated values in an alist may be any Lisp objects; so may the
1306 keys. For example, in the following alist, the symbol @code{a} is
1307 associated with the number @code{1}, and the string @code{"b"} is
1308 associated with the @emph{list} @code{(2 3)}, which is the @sc{cdr} of
1315 Sometimes it is better to design an alist to store the associated
1316 value in the @sc{car} of the @sc{cdr} of the element. Here is an
1320 '((rose red) (lily white) (buttercup yellow))
1324 Here we regard @code{red} as the value associated with @code{rose}. One
1325 advantage of this method is that you can store other related
1326 information---even a list of other items---in the @sc{cdr} of the
1327 @sc{cdr}. One disadvantage is that you cannot use @code{rassq} (see
1328 below) to find the element containing a given value. When neither of
1329 these considerations is important, the choice is a matter of taste, as
1330 long as you are consistent about it for any given alist.
1332 Note that the same alist shown above could be regarded as having the
1333 associated value in the @sc{cdr} of the element; the value associated
1334 with @code{rose} would be the list @code{(red)}.
1336 Association lists are often used to record information that you might
1337 otherwise keep on a stack, since new associations may be added easily to
1338 the front of the list. When searching an association list for an
1339 association with a given key, the first one found is returned, if there
1342 In SXEmacs Lisp, it is @emph{not} an error if an element of an
1343 association list is not a cons cell. The alist search functions simply
1344 ignore such elements. Many other versions of Lisp signal errors in such
1347 Note that property lists are similar to association lists in several
1348 respects. A property list behaves like an association list in which
1349 each key can occur only once. @xref{Property Lists}, for a comparison
1350 of property lists and association lists.
1352 @defun assoc key alist
1353 This function returns the first association for @var{key} in
1354 @var{alist}. It compares @var{key} against the alist elements using
1355 @code{equal} (@pxref{Equality Predicates}). It returns @code{nil} if no
1356 association in @var{alist} has a @sc{car} @code{equal} to @var{key}.
1360 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1361 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1363 @result{} (oak . acorns)
1364 (cdr (assoc 'oak trees))
1366 (assoc 'birch trees)
1370 Here is another example, in which the keys and values are not symbols:
1373 (setq needles-per-cluster
1374 '((2 "Austrian Pine" "Red Pine")
1378 (cdr (assoc 3 needles-per-cluster))
1379 @result{} ("Pitch Pine")
1380 (cdr (assoc 2 needles-per-cluster))
1381 @result{} ("Austrian Pine" "Red Pine")
1385 @defun rassoc value alist
1386 This function returns the first association with value @var{value} in
1387 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1388 a @sc{cdr} @code{equal} to @var{value}.
1390 @code{rassoc} is like @code{assoc} except that it compares the @sc{cdr} of
1391 each @var{alist} association instead of the @sc{car}. You can think of
1392 this as ``reverse @code{assoc}'', finding the key for a given value.
1395 @defun assq key alist
1396 This function is like @code{assoc} in that it returns the first
1397 association for @var{key} in @var{alist}, but it makes the comparison
1398 using @code{eq} instead of @code{equal}. @code{assq} returns @code{nil}
1399 if no association in @var{alist} has a @sc{car} @code{eq} to @var{key}.
1400 This function is used more often than @code{assoc}, since @code{eq} is
1401 faster than @code{equal} and most alists use symbols as keys.
1402 @xref{Equality Predicates}.
1405 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1406 @result{} ((pine . cones) (oak . acorns) (maple . seeds))
1408 @result{} (pine . cones)
1411 On the other hand, @code{assq} is not usually useful in alists where the
1412 keys may not be symbols:
1416 '(("simple leaves" . oak)
1417 ("compound leaves" . horsechestnut)))
1419 (assq "simple leaves" leaves)
1421 (assoc "simple leaves" leaves)
1422 @result{} ("simple leaves" . oak)
1426 @defun rassq value alist
1427 This function returns the first association with value @var{value} in
1428 @var{alist}. It returns @code{nil} if no association in @var{alist} has
1429 a @sc{cdr} @code{eq} to @var{value}.
1431 @code{rassq} is like @code{assq} except that it compares the @sc{cdr} of
1432 each @var{alist} association instead of the @sc{car}. You can think of
1433 this as ``reverse @code{assq}'', finding the key for a given value.
1438 (setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
1440 (rassq 'acorns trees)
1441 @result{} (oak . acorns)
1442 (rassq 'spores trees)
1446 Note that @code{rassq} cannot search for a value stored in the @sc{car}
1447 of the @sc{cdr} of an element:
1450 (setq colors '((rose red) (lily white) (buttercup yellow)))
1452 (rassq 'white colors)
1456 In this case, the @sc{cdr} of the association @code{(lily white)} is not
1457 the symbol @code{white}, but rather the list @code{(white)}. This
1458 becomes clearer if the association is written in dotted pair notation:
1461 (lily white) @equiv{} (lily . (white))
1465 @defun remassoc key alist
1466 This function deletes by side effect any associations with key @var{key}
1467 in @var{alist}---i.e. it removes any elements from @var{alist} whose
1468 @code{car} is @code{equal} to @var{key}. The modified @var{alist} is
1471 If the first member of @var{alist} has a @code{car} that is @code{equal}
1472 to @var{key}, there is no way to remove it by side effect; therefore,
1473 write @code{(setq foo (remassoc key foo))} to be sure of changing the
1474 value of @code{foo}.
1477 @defun remassq key alist
1478 This function deletes by side effect any associations with key @var{key}
1479 in @var{alist}---i.e. it removes any elements from @var{alist} whose
1480 @code{car} is @code{eq} to @var{key}. The modified @var{alist} is
1483 This function is exactly like @code{remassoc}, but comparisons between
1484 @var{key} and keys in @var{alist} are done using @code{eq} instead of
1488 @defun remrassoc value alist
1489 This function deletes by side effect any associations with value @var{value}
1490 in @var{alist}---i.e. it removes any elements from @var{alist} whose
1491 @code{cdr} is @code{equal} to @var{value}. The modified @var{alist} is
1494 If the first member of @var{alist} has a @code{car} that is @code{equal}
1495 to @var{value}, there is no way to remove it by side effect; therefore,
1496 write @code{(setq foo (remassoc value foo))} to be sure of changing the
1497 value of @code{foo}.
1499 @code{remrassoc} is like @code{remassoc} except that it compares the
1500 @sc{cdr} of each @var{alist} association instead of the @sc{car}. You
1501 can think of this as ``reverse @code{remassoc}'', removing an association
1502 based on its value instead of its key.
1505 @defun remrassq value alist
1506 This function deletes by side effect any associations with value @var{value}
1507 in @var{alist}---i.e. it removes any elements from @var{alist} whose
1508 @code{cdr} is @code{eq} to @var{value}. The modified @var{alist} is
1511 This function is exactly like @code{remrassoc}, but comparisons between
1512 @var{value} and values in @var{alist} are done using @code{eq} instead of
1516 @defun copy-alist alist
1517 @cindex copying alists
1518 This function returns a two-level deep copy of @var{alist}: it creates a
1519 new copy of each association, so that you can alter the associations of
1520 the new alist without changing the old one.
1524 (setq needles-per-cluster
1525 '((2 . ("Austrian Pine" "Red Pine"))
1526 (3 . ("Pitch Pine"))
1528 (5 . ("White Pine"))))
1530 ((2 "Austrian Pine" "Red Pine")
1534 (setq copy (copy-alist needles-per-cluster))
1536 ((2 "Austrian Pine" "Red Pine")
1540 (eq needles-per-cluster copy)
1542 (equal needles-per-cluster copy)
1544 (eq (car needles-per-cluster) (car copy))
1546 (cdr (car (cdr needles-per-cluster)))
1547 @result{} ("Pitch Pine")
1549 (eq (cdr (car (cdr needles-per-cluster)))
1550 (cdr (car (cdr copy))))
1555 This example shows how @code{copy-alist} makes it possible to change
1556 the associations of one copy without affecting the other:
1560 (setcdr (assq 3 copy) '("Martian Vacuum Pine"))
1561 (cdr (assq 3 needles-per-cluster))
1562 @result{} ("Pitch Pine")
1568 @node Property Lists
1569 @section Property Lists
1570 @cindex property list
1573 A @dfn{property list} (or @dfn{plist}) is another way of representing a
1574 mapping from keys to values. Instead of the list consisting of conses
1575 of a key and a value, the keys and values alternate as successive
1576 entries in the list. Thus, the association list
1579 ((a . 1) (b . 2) (c . 3))
1582 has the equivalent property list form
1588 Property lists are used to represent the properties associated with
1589 various sorts of objects, such as symbols, strings, frames, etc.
1590 The convention is that property lists can be modified in-place,
1591 while association lists generally are not.
1593 Plists come in two varieties: @dfn{normal} plists, whose keys are
1594 compared with @code{eq}, and @dfn{lax} plists, whose keys are compared
1597 @defun valid-plist-p plist
1598 Given a plist, this function returns non-@code{nil} if its format is
1599 correct. If it returns @code{nil}, @code{check-valid-plist} will signal
1600 an error when given the plist; that means it's a malformed or circular
1601 plist or has non-symbols as keywords.
1604 @defun check-valid-plist plist
1605 Given a plist, this function signals an error if there is anything wrong
1606 with it. This means that it's a malformed or circular plist.
1610 * Working With Normal Plists:: Functions for normal plists.
1611 * Working With Lax Plists:: Functions for lax plists.
1612 * Converting Plists To/From Alists:: Alist to plist and vice-versa.
1616 @node Working With Normal Plists
1617 @subsection Working With Normal Plists
1619 @defun plist-get plist property &optional default
1620 This function extracts a value from a property list. The function
1621 returns the value corresponding to the given @var{property}, or
1622 @var{default} if @var{property} is not one of the properties on the list.
1625 @defun plist-put plist property value
1626 This function changes the value in @var{plist} of @var{property} to
1627 @var{value}. If @var{property} is already a property on the list, its value is
1628 set to @var{value}, otherwise the new @var{property} @var{value} pair is added.
1629 The new plist is returned; use @code{(setq x (plist-put x property value))} to
1630 be sure to use the new value. The @var{plist} is modified by side
1634 @defun plist-remprop plist property
1635 This function removes from @var{plist} the property @var{property} and its
1636 value. The new plist is returned; use @code{(setq x (plist-remprop x
1637 property))} to be sure to use the new value. The @var{plist} is
1638 modified by side effects.
1641 @defun plist-member plist property
1642 This function returns @code{t} if @var{property} has a value specified in
1646 In the following functions, if optional arg @var{nil-means-not-present}
1647 is non-@code{nil}, then a property with a @code{nil} value is ignored or
1648 removed. This feature is a virus that has infected old Lisp
1649 implementations (and thus E-Lisp, due to @sc{rms}'s enamorment with old
1650 Lisps), but should not be used except for backward compatibility.
1652 @defun plists-eq a b &optional nil-means-not-present
1653 This function returns non-@code{nil} if property lists A and B are
1654 @code{eq} (i.e. their values are @code{eq}).
1657 @defun plists-equal a b &optional nil-means-not-present
1658 This function returns non-@code{nil} if property lists A and B are
1659 @code{equal} (i.e. their values are @code{equal}; their keys are
1660 still compared using @code{eq}).
1663 @defun canonicalize-plist plist &optional nil-means-not-present
1664 This function destructively removes any duplicate entries from a plist.
1665 In such cases, the first entry applies.
1667 The new plist is returned. If @var{nil-means-not-present} is given, the
1668 return value may not be @code{eq} to the passed-in value, so make sure
1669 to @code{setq} the value back into where it came from.
1673 @node Working With Lax Plists
1674 @subsection Working With Lax Plists
1676 Recall that a @dfn{lax plist} is a property list whose keys are compared
1677 using @code{equal} instead of @code{eq}.
1679 @defun lax-plist-get lax-plist property &optional default
1680 This function extracts a value from a lax property list. The function
1681 returns the value corresponding to the given @var{property}, or
1682 @var{default} if @var{property} is not one of the properties on the list.
1685 @defun lax-plist-put lax-plist property value
1686 This function changes the value in @var{lax-plist} of @var{property} to @var{value}.
1689 @defun lax-plist-remprop lax-plist property
1690 This function removes from @var{lax-plist} the property @var{property} and
1691 its value. The new plist is returned; use @code{(setq x
1692 (lax-plist-remprop x property))} to be sure to use the new value. The
1693 @var{lax-plist} is modified by side effects.
1696 @defun lax-plist-member lax-plist property
1697 This function returns @code{t} if @var{property} has a value specified in
1701 In the following functions, if optional arg @var{nil-means-not-present}
1702 is non-@code{nil}, then a property with a @code{nil} value is ignored or
1703 removed. This feature is a virus that has infected old Lisp
1704 implementations (and thus E-Lisp, due to @sc{rms}'s enamorment with old
1705 Lisps), but should not be used except for backward compatibility.
1707 @defun lax-plists-eq a b &optional nil-means-not-present
1708 This function returns non-@code{nil} if lax property lists A and B are
1709 @code{eq} (i.e. their values are @code{eq}; their keys are still
1710 compared using @code{equal}).
1713 @defun lax-plists-equal a b &optional nil-means-not-present
1714 This function returns non-@code{nil} if lax property lists A and B are
1715 @code{equal} (i.e. their values are @code{equal}).
1718 @defun canonicalize-lax-plist lax-plist &optional nil-means-not-present
1719 This function destructively removes any duplicate entries from a lax
1720 plist. In such cases, the first entry applies.
1722 The new plist is returned. If @var{nil-means-not-present} is given, the
1723 return value may not be @code{eq} to the passed-in value, so make sure
1724 to @code{setq} the value back into where it came from.
1728 @node Converting Plists To/From Alists
1729 @subsection Converting Plists To/From Alists
1731 @defun alist-to-plist alist
1732 This function converts association list @var{alist} into the equivalent
1733 property-list form. The plist is returned. This converts from
1736 ((a . 1) (b . 2) (c . 3))
1745 The original alist is not modified.
1748 @defun plist-to-alist plist
1749 This function converts property list @var{plist} into the equivalent
1750 association-list form. The alist is returned. This converts from
1759 ((a . 1) (b . 2) (c . 3))
1762 The original plist is not modified.
1765 The following two functions are equivalent to the preceding two except
1766 that they destructively modify their arguments, using cons cells from
1767 the original list to form the new list rather than allocating new
1770 @defun destructive-alist-to-plist alist
1771 This function destructively converts association list @var{alist} into
1772 the equivalent property-list form. The plist is returned.
1775 @defun destructive-plist-to-alist plist
1776 This function destructively converts property list @var{plist} into the
1777 equivalent association-list form. The alist is returned.
1785 Like association lists or property lists, a skip list is another
1786 dictionary data type. That is skip lists can be used to represent a
1787 finite key-value mapping. See @xref{Association Lists}, and
1788 @xref{Property Lists}.
1790 However, alists and plists are very inefficient at almost any
1791 operation for large key spaces. For instance, looking up the value of
1792 a given key is accomplished by linear probing. This implies that
1793 searching for a key not in the key space is a worst case, the list has
1794 to be traversed in its entirety as it contains no superior structure
1795 or indicators which help to identify keys not belonging to the key
1798 On the other hand, given an alist or plist this lack of structure
1799 induces a class of equivalent alists or plists with respect to the
1800 storage representation. This would make it possible to add new
1801 elements in constant time by just prepending them to the front of the
1804 Anyway, without manual intervention SXEmacs' association and property
1805 lists @strong{cannot} add elements in constant time. Instead they try
1806 to avoid duplicate keys and thence crawl the entire list to make sure
1807 the key to be added is not already there.
1810 @defun make-skiplist
1811 Return a new empty skiplist object.
1814 @defun skiplistp object
1815 Return non-@code{nil} if @var{object} is a skiplist, @code{nil}
1819 @defun skiplist-empty-p skiplist
1820 Return non-@code{nil} if @var{skiplist} is empty, @code{nil}
1824 @defun put-skiplist skiplist key value
1825 Add @var{key} to the @var{skiplist} and assign @var{value}.
1826 Hereby, the skiplist object is modified by side-effect.
1829 @defun get-skiplist skiplist key &optional default
1830 Return the value of @var{key} in @var{skiplist}.
1831 If @var{key} is not an element, return @code{nil} instead or --
1832 if specified -- @var{default}.
1835 @defun remove-skiplist skiplist key
1836 Remove the element specified by @var{key} from @var{skiplist}.
1837 If @var{key} is not an element, this is a no-op.
1840 @defun skiplist-owns-p skiplist key
1841 Return non-@code{nil} if @var{key} is associated with a value in
1842 @var{skiplist}, @code{nil} otherwise.
1845 @defun skiplist-size skiplist
1846 Return the size of @var{skiplist}, that is the number of elements.
1849 @defun copy-skiplist skiplist
1850 Return a copy of skiplist @var{skiplist}.
1851 The elements of @var{skiplist} are not copied; they are shared
1855 @defun skiplist-to-alist skiplist
1856 Return the ordinary association list induced by @var{skiplist}.
1859 @defun skiplist-to-plist skiplist
1860 Return the ordinary property list induced by @var{skiplist}.
1863 @defun alist-to-skiplist alist
1864 Return a skiplist from @var{alist} with equal key space and image.
1867 @defun plist-to-skiplist plist
1868 Return a skiplist from @var{plist} with equal key space and image.
1871 @defun skiplist-union &rest skiplists
1872 Return the union skiplist of @var{skiplists},
1873 that is a skiplist containing all key-value-pairs which are in at
1874 least one skiplist of @var{skiplists}.
1876 Note: Key-value-pairs with equal keys and distinct values are
1877 processed from left to right, that is the final union for such pairs
1878 contains the value of the rightmost skiplist in @var{skiplists}.
1881 @defun skiplist-intersection &rest skiplists
1882 Return the intersection skiplist of @var{skiplists},
1883 that is a skiplist containing all key-value-pairs which are in all
1884 skiplists of @var{skiplists}.
1886 Note: Key-value-pairs with equal keys and distinct values are
1887 processed from right to left, that is the final intersection for such
1888 pairs contains the value of the leftmost skiplist in @var{skiplists}.
1891 @defun map-skiplist function skiplist
1892 Map @var{function} over entries in @var{skiplist}, calling it with two
1893 args, each key and value in @var{skiplist}.
1895 @var{function} may not modify @var{skiplist}, with the one exception
1896 that @var{function} may remove or reput the entry currently being
1897 processed by @var{function}.
1906 A @dfn{weak list} is a special sort of list whose members are not counted
1907 as references for the purpose of garbage collection. This means that,
1908 for any object in the list, if there are no references to the object
1909 anywhere outside of the list (or other weak list or weak hash table),
1910 that object will disappear the next time a garbage collection happens.
1911 Weak lists can be useful for keeping track of things such as unobtrusive
1912 lists of another function's buffers or markers. When that function is
1913 done with the elements, they will automatically disappear from the list.
1915 Weak lists are used internally, for example, to manage the list holding
1916 the children of an extent---an extent that is unused but has a parent
1917 will still be reclaimed, and will automatically be removed from its
1918 parent's list of children.
1920 Weak lists are similar to weak hash tables (@pxref{Weak Hash Tables}).
1922 @defun weak-list-p object
1923 This function returns non-@code{nil} if @var{object} is a weak list.
1926 Weak lists come in one of four types:
1930 Objects in the list disappear if not referenced outside of the list.
1933 Objects in the list disappear if they are conses and either the car or
1934 the cdr of the cons is not referenced outside of the list.
1937 Objects in the list disappear if they are conses and the car is not
1938 referenced outside of the list.
1941 Objects in the list disappear if they are conses and the cdr is not
1942 referenced outside of the list.
1945 @defun make-weak-list &optional type
1946 This function creates a new weak list of type @var{type}. @var{type} is
1947 a symbol (one of @code{simple}, @code{assoc}, @code{key-assoc}, or
1948 @code{value-assoc}, as described above) and defaults to @code{simple}.
1951 @defun weak-list-type weak
1952 This function returns the type of the given weak-list object.
1955 @defun weak-list-list weak
1956 This function returns the list contained in a weak-list object.
1959 @defun set-weak-list-list weak new-list
1960 This function changes the list contained in a weak-list object.
1965 @section Doubly-Linked Lists
1967 @cindex doubly-linked list
1969 A doubly-linked list is a mere extension of the ordinary linked list.
1970 While the latter one has an entry pointer to the first element of the
1971 list (obtainable via @code{car}) and for each element a pointer to the
1972 next element (obtainable via @code{cdr}), the doubly-linked list
1973 (dl-list for short) has both, an entry pointer to the first element and
1974 an entry pointer to the last element. These are obtainable via
1975 @code{dllist-car} and @code{dllist-rac}, respectively. Moreover, all
1976 elements of the dl-list point to the next and the previous element.
1978 This well-known structure supports both appending and prepending
1979 elements in the same time complexity class.
1981 @defun dllist &rest initial-elements
1982 Return a doubly-linked list.
1984 Optionally passed arguments are filled into the resulting dllist.
1987 @defun dllistp object
1988 Return non-@code{nil} if @var{object} is a dllist, @code{nil}
1992 @defun dllist-empty-p dllist
1993 Return non-@code{nil} if @var{dllist} is empty, @code{nil} otherwise.
1996 @defun dllist-size dllist
1997 Return the size of @var{dllist}, that is the number of elements.
2001 @defun dllist-car dllist
2002 Return the front element of @var{dllist}.
2005 @defun dllist-rac dllist
2006 Return the back element of @var{dllist}.
2010 Note: All of the following modifier functions work by side-effect.
2012 @defun dllist-prepend dllist element
2013 Add @var{element} to the front of @var{dllist}.
2016 @defun dllist-append dllist element
2017 Add @var{element} to the back of @var{dllist}.
2020 @defun dllist-pop-car dllist
2021 Remove the front element of @var{dllist} and return it.
2024 @defun dllist-pop-rac dllist
2025 Remove the back element of @var{dllist} and return it.
2028 In box notation a dllist looks like
2033 | _____|_ _v___|_ _v___|_
2034 --> |_______| |_______| |_______| <--
2036 nil <-- | |_______| | |_______| | |
2045 Let us look at some examples.
2057 @result{} (dllist 2)
2059 @result{} (dllist 2 4)
2061 @result{} (dllist 2 4 6)
2072 (dllist-prepend d (dllist-pop-rac d))
2073 @result{} (dllist 6 2 4)
2074 (dllist-append d (dllist-pop-car d))
2075 @result{} (dllist 2 4 6)
2082 Of course, dl-lists can be converted to ordinary lisp lists.
2084 @defun dllist-to-list dllist
2085 Return the ordinary list induced by @var{dllist}, that is start with
2086 the first element in @var{dllist} and traverse through the back.
2089 @defun dllist-to-list-reversed dllist
2090 Return the ordinary list induced by @var{dllist} in reverse order,
2091 that is start with the last element in @var{dllist} and traverse
2099 (dllist-to-list-reversed d)
2106 @section Bloom Filters
2107 @cindex Bloom filters
2109 The concept of a Bloom filter was introduces by Burton H. Bloom in 1970.
2110 It is a constant space complexity, probabilistic data structure that is
2111 used to do so-called membership decisions on anonymous sets. That is,
2112 you can easily decide whether a given element is a member of a certain
2113 set, whereas you cannot select elements from it (or even traverse
2114 through all elements). Moreover, like hash-tables the time complexity
2115 of Bloom filters for adding and removing elements, as well as
2116 membership-decision is in O(1) -- it is in O(@var{k}) indeed where
2117 @var{k} is the degree of the Bloom filter.
2119 Probabilistic, however, means that false positives are possible, but
2120 false negatives are not. The probability of false positives grows
2121 subexponentially with the number of added elements.
2123 Another interesting property of Bloom filters of equal order and
2124 degree is the ability to perform set union and intersection operations
2125 within O(1) space and time complexity!
2127 SXEmacs' Bloom filters have their own lisp-type, but they do not have
2128 a special input syntax.
2130 @defun make-bloom &optional order degree
2131 Return an empty bloom-filter.
2133 Optional argument @var{order} (a positive integer) specifies the
2134 ``length'' of the internal filter vector, defaults to 256.
2136 Optional argument @var{degree} (a positive integer) specifies the
2137 number of hash slices, defaults to 8.
2140 For reasons of convenience, we also provide a constructor for a
2141 complete Bloom filter. That is a bloom filter which owns any possible
2144 @defun make-bloom-universe &optional order degree
2145 Return a complete bloom-filter.
2147 Optional argument @var{order} (a positive integer) specifies the
2148 ``length'' of the internal filter vector, defaults to 256.
2150 Optional argument @var{degree} (a positive integer) specifies the
2151 number of hash slices, defaults to 8.
2155 @defun bloomp object
2156 Return non-@code{nil} if @var{object} is a bloom filter,
2157 @code{nil} otherwise.
2160 There are two further auxiliary functions to determine the bloom
2163 @defun bloom-order bloom
2164 Return the order of the bloom-filter @var{bloom}.
2167 @defun bloom-degree bloom
2168 Return the degree of the bloom-filter @var{bloom}.
2172 Adding/removing elements to/from a bloom filter always works by
2175 @defun bloom-add bloom element
2176 Add @var{element} to the bloom-filter @var{bloom}.
2179 @defun bloom-remove bloom element
2180 Remove @var{element} from the bloom-filter @var{bloom}.
2184 The membership decision is done with @code{bloom-owns-p}.
2186 @defun bloom-owns-p bloom element
2187 Return non-@code{nil} if @var{element} is in the bloom-filter
2193 (setq bl (make-bloom))
2194 @result{} #<bloom-filter :order 256 :degree 8 :size 0>
2200 Now we want to add three integers and test some memberships.
2213 (bloom-owns-p bl 12)
2215 (bloom-owns-p bl 21)
2219 (bloom-owns-p bl 13)
2221 (bloom-owns-p bl 17)
2227 Now let us remove some elements
2231 (bloom-remove bl 12)
2238 (bloom-owns-p bl 12)
2240 (bloom-owns-p bl 21)
2247 Of course, Bloom filters work with any lisp type (not just integers).
2248 Internally, they use an object's hash value and scatter it over a
2253 (bloom-owns-p bl "horse")
2255 (bloom-add bl "horse")
2257 (bloom-owns-p bl "horse")
2259 (bloom-owns-p bl "snake")
2265 As remarked above, union and intersection of Bloom-filters of equal
2266 order and degree is possible in constant time regardless of the size.
2268 @defun bloom-union &rest blooms
2269 Return the union Bloom filter of all arguments.
2272 @defun bloom-intersection &rest blooms
2273 Return the intersection Bloom filter of all arguments.
2278 (setq bl1 (make-bloom))
2279 @result{} #<bloom-filter :order 256 :degree 8 :size 0>
2284 (bloom-add bl1 'foobar)
2289 (setq bl2 (make-bloom))
2290 @result{} #<bloom-filter :order 256 :degree 8 :size 0>
2291 (bloom-add bl2 "horse")
2293 (bloom-add bl2 "snail")
2295 (bloom-add bl2 'foobar)
2300 (setq blu (bloom-union bl1 bl2))
2301 @result{} #<bloom-filter :order 256 :degree 8 :size 6>
2302 (bloom-owns-p blu 2)
2304 (bloom-owns-p blu 4)
2306 (bloom-owns-p blu "horse")
2308 (bloom-owns-p blu "snail")
2310 (bloom-owns-p blu 'foobar)
2315 (setq bli (bloom-intersection bl1 bl2))
2316 @result{} #<bloom-filter :order 256 :degree 8 :size 0>
2317 (bloom-owns-p bli 2)
2319 (bloom-owns-p bli 4)
2321 (bloom-owns-p bli "horse")
2323 (bloom-owns-p bli "snail")
2325 (bloom-owns-p bli 'foobar)
2331 Now we want to illustrate the extreme performance gain over lists, and
2332 compare to the performance of hash-tables. Therefore, we use a setup
2333 routine which fills a data container with 10000 distinct elements. Then
2334 we do 50000 membership tests. Let's start with ordinary lisp lists. For
2335 each of these both tests we measure the time.
2339 (defun test-element ()
2340 "Return a random test element."
2342 @result{} test-element
2352 (let ((start (current-btime)))
2354 (setq tlist (cons (test-element) tlist)))
2355 (- (current-btime) start))
2360 ;; 50000 membership tests on tlist @dots{} take a coffee break
2363 (let ((start (current-btime)))
2365 (member (test-element) tlist))
2366 (- (current-btime) start))
2372 Let's consider hash-tables:
2375 (setq thash (make-hash-table))
2376 @result{} #<hash-table size 0/29 0x1619>
2379 (let ((start (current-btime)))
2381 (puthash (test-element) 'some-value thash))
2382 (- (current-btime) start))
2387 ;; 50000 membership tests on thash
2390 (let ((start (current-btime)))
2392 (gethash (test-element) thash))
2393 (- (current-btime) start))
2399 Let's finish our considerations with Bloom filters:
2402 (setq tbfil (make-bloom))
2403 @result{} #<bloom-filter :order 256 :degree 8 :size 0>
2406 (let ((start (current-btime)))
2408 (bloom-add tbfil (test-element)))
2409 (- (current-btime) start))
2414 ;; 50000 membership tests on tbfil
2417 (let ((start (current-btime)))
2419 (bloom-owns-p tbfil (test-element)))
2420 (- (current-btime) start))
2425 Evaluating all these results, we can state that hash-tables and
2426 Bloom-filters provide equal performance. For extremely large sets,
2427 Bloom-filters may profit from the absence of resizing the underlying
2432 ;; 400000 insertions into a bloom-filter
2433 (setq tbfil (make-bloom))
2434 @result{} #<bloom-filter :order 256 :degree 8 :size 0>
2437 (let ((start (current-btime)))
2439 (bloom-add tbfil (test-element)))
2440 (- (current-btime) start))
2445 ;; 400000 insertions into a hash-table
2446 (setq thash (make-hash-table))
2447 @result{} #<hash-table size 0/29 0x1066>
2450 (let ((start (current-btime)))
2452 (puthash (test-element) 'some-value thash))
2453 (- (current-btime) start))
2458 Furthermore, Bloom filters are able to track how often equal elements
2459 have been inserted, for hash-tables the value field may be used to
2460 implement something similar.
2462 However, bloom filters tend to report more and more false positives
2463 the more elements you add. False negatives are @strong{never}
2464 possible. That means with a sufficiently small bloom filter and a
2465 sufficiently large set of elements it is just a matter of probability
2466 when this filter will turn into a universe.
2469 (setq b4 (make-bloom 256 64))
2470 @result{} #<bloom-filter :order 256 :degree 64 :size 0>
2472 ;; now add 800000 numbers to it
2478 (bloom-owns-p b4 'a-symbol-I-never-added)
2480 (bloom-owns-p b4 "a string I never added")
2482 (bloom-owns-p b4 [a vector I never added])
2487 We see that @code{b4} has turned into a quasi-universe. There might
2488 be objects which are not yet in @code{b4}, but the probability to find
2489 one is extremely small.
2491 Given a bloom filter of degree @var{d} and size @var{s}, and given
2492 the bloom filter already contains @var{n} elements, the exact
2493 probability to get a false positive (an element which has not been
2494 added, but @code{bloom-owns-p} reports so) is:
2499 \left(1 - \left(1 - {1\over s}\right)^{dn}\right)^d
2504 (1 - (1 - 1/s)^(d*n))^d
2508 So for our example the probability is veeery close to one, to be
2512 0.9999...99993386493554255105254275560...
2517 @c @c @c lists.texi ends here