GNU Info

(elisp)Rearrangement

---

Prev: Setcdr Up: Modifying Lists

---

Enter node , (file) or (file)node

Functions that Rearrange Lists
------------------------------

   Here are some functions that rearrange lists "destructively" by
modifying the CDRs of their component cons cells.  We call these
functions "destructive" because they chew up the original lists passed
to them as arguments, relinking their cons cells to form a new list that
is the returned value.

   See `delq', in Note: Sets And Lists, for another function that
modifies cons cells.

 - Function: nconc &rest lists
     This function returns a list containing all the elements of LISTS.
     Unlike `append' (Note: Building Lists), the LISTS are _not_
     copied.  Instead, the last CDR of each of the LISTS is changed to
     refer to the following list.  The last of the LISTS is not
     altered.  For example:

          (setq x '(1 2 3))
               => (1 2 3)
          (nconc x '(4 5))
               => (1 2 3 4 5)
          x
               => (1 2 3 4 5)

     Since the last argument of `nconc' is not itself modified, it is
     reasonable to use a constant list, such as `'(4 5)', as in the
     above example.  For the same reason, the last argument need not be
     a list:

          (setq x '(1 2 3))
               => (1 2 3)
          (nconc x 'z)
               => (1 2 3 . z)
          x
               => (1 2 3 . z)

     However, the other arguments (all but the last) must be lists.

     A common pitfall is to use a quoted constant list as a non-last
     argument to `nconc'.  If you do this, your program will change
     each time you run it!  Here is what happens:

          (defun add-foo (x)            ; We want this function to add
            (nconc '(foo) x))           ;   `foo' to the front of its arg.
          
          (symbol-function 'add-foo)
               => (lambda (x) (nconc (quote (foo)) x))
          
          (setq xx (add-foo '(1 2)))    ; It seems to work.
               => (foo 1 2)
          (setq xy (add-foo '(3 4)))    ; What happened?
               => (foo 1 2 3 4)
          (eq xx xy)
               => t
          
          (symbol-function 'add-foo)
               => (lambda (x) (nconc (quote (foo 1 2 3 4) x)))

 - Function: nreverse list
     This function reverses the order of the elements of LIST.  Unlike
     `reverse', `nreverse' alters its argument by reversing the CDRs in
     the cons cells forming the list.  The cons cell that used to be
     the last one in LIST becomes the first cons cell of the value.

     For example:

          (setq x '(a b c))
               => (a b c)
          x
               => (a b c)
          (nreverse x)
               => (c b a)
          ;; The cons cell that was first is now last.
          x
               => (a)

     To avoid confusion, we usually store the result of `nreverse' back
     in the same variable which held the original list:

          (setq x (nreverse x))

     Here is the `nreverse' of our favorite example, `(a b c)',
     presented graphically:

          Original list head:                       Reversed list:
           -------------        -------------        ------------
          | car  | cdr  |      | car  | cdr  |      | car | cdr  |
          |   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
          |      |      |   |  |      |   |  |   |  |     |   |  |
           -------------    |   --------- | -    |   -------- | -
                            |             |      |            |
                             -------------        ------------

 - Function: sort list predicate
     This function sorts LIST stably, though destructively, and returns
     the sorted list.  It compares elements using PREDICATE.  A stable
     sort is one in which elements with equal sort keys maintain their
     relative order before and after the sort.  Stability is important
     when successive sorts are used to order elements according to
     different criteria.

     The argument PREDICATE must be a function that accepts two
     arguments.  It is called with two elements of LIST.  To get an
     increasing order sort, the PREDICATE should return `t' if the
     first element is "less than" the second, or `nil' if not.

     The comparison function PREDICATE must give reliable results for
     any given pair of arguments, at least within a single call to
     `sort'.  It must be "antisymmetric"; that is, if A is less than B,
     B must not be less than A.  It must be "transitive"--that is, if A
     is less than B, and B is less than C, then A must be less than C.
     If you use a comparison function which does not meet these
     requirements, the result of `sort' is unpredictable.

     The destructive aspect of `sort' is that it rearranges the cons
     cells forming LIST by changing CDRs.  A nondestructive sort
     function would create new cons cells to store the elements in their
     sorted order.  If you wish to make a sorted copy without
     destroying the original, copy it first with `copy-sequence' and
     then sort.

     Sorting does not change the CARs of the cons cells in LIST; the
     cons cell that originally contained the element `a' in LIST still
     has `a' in its CAR after sorting, but it now appears in a
     different position in the list due to the change of CDRs.  For
     example:

          (setq nums '(1 3 2 6 5 4 0))
               => (1 3 2 6 5 4 0)
          (sort nums '<)
               => (0 1 2 3 4 5 6)
          nums
               => (1 2 3 4 5 6)

     *Warning*: Note that the list in `nums' no longer contains 0; this
     is the same cons cell that it was before, but it is no longer the
     first one in the list.  Don't assume a variable that formerly held
     the argument now holds the entire sorted list!  Instead, save the
     result of `sort' and use that.  Most often we store the result
     back into the variable that held the original list:

          (setq nums (sort nums '<))

     Note: Sorting, for more functions that perform sorting.  See
     `documentation' in Note: Accessing Documentation, for a useful
     example of `sort'.