Common Lisp the Language, 2nd Edition

Next: Alteration of List Up: Lists Previous: Conses

# 15.2. Lists

The following functions perform various operations on lists.

The list is one of the original Lisp data types. The very name ``Lisp'' is an abbreviation for ``LISt Processing.''

[Function]
`endp object`

The predicate `endp` is the recommended way to test for the end of a list. It is false of conses, true of `nil`, and an error for all other arguments.

Implementation note: Implementations are encouraged to signal an error, especially in the interpreter, for a non-list argument. The `endp` function is defined so as to allow compiled code to perform simply an atom check or a null check if speed is more important than safety.

[Function]
`list-length list`

`list-length` returns, as an integer, the length of list. `list-length` differs from `length` when the list is circular; `length` may fail to return, whereas `list-length` will return `nil`. For example:

    (list-length '()) => 0
    (list-length '(a b c d)) => 4
    (list-length '(a (b c) d)) => 3
    (let ((x (list 'a b c)))
      (rplacd (last x) x)
      (list-length x)) => nil

`list-length` could be implemented as follows:

    (defun list-length (x)
      (do ((n 0 (+ n 2))            ;Counter
           (fast x (cddr fast))     ;Fast pointer: leaps by 2
           (slow x (cdr slow)))     ;Slow pointer: leaps by 1
          (nil)
        ;; If fast pointer hits the end, return the count.
        (when (endp fast) (return n))
        (when (endp (cdr fast)) (return (+ n 1)))
        ;; If fast pointer eventually equals slow pointer,
        ;;  then we must be stuck in a circular list.
        ;; (A deeper property is the converse: if we are
        ;;  stuck in a circular list, then eventually the
        ;;  fast pointer will equal the slow pointer.
        ;;  That fact justifies this implementation.)
        (when (and (eq fast slow) (> n 0)) (return nil))))

See `length`, which will return the length of any sequence.

[Function]
`nth n list`

`(nth n list)` returns the nth element of list, where the car of the list is the ``zeroth'' element. The argument n must be a non-negative integer. If the length of the list is not greater than n, then the result is `()`, that is, `nil`. (This is consistent with the idea that the car and cdr of `()` are each `()`.) For example:

    (nth 0 '(foo bar gack)) => foo
    (nth 1 '(foo bar gack)) => bar
    (nth 3 '(foo bar gack)) => ()

Compatibility note: This is not the same as the Interlisp function called `nth`, which is similar to but not exactly the same as the Common Lisp function `nthcdr`. This definition of `nth` is compatible with Lisp Machine Lisp and NIL (New Implementation of Lisp). Also, some people have used macros and functions called `nth` of their own in their old MacLisp programs, which may not work the same way.

`nth` may be used to specify a place to `setf`; when `nth` is used in this way, the argument n must be less than the length of the list.

Note that the arguments to `nth` are reversed from the order used by most other sequence selector functions such as `elt`.

[Function]
`first list
``second list
``third list
``fourth list
``fifth list
``sixth list
``seventh list
``eighth list
``ninth list
``tenth list`

These functions are sometimes convenient for accessing particular elements of a list. `first` is the same as `car`, `second` is the same as `cadr`, `third` is the same as `caddr`, and so on. Note that the ordinal numbering used here is one-origin, as opposed to the zero-origin numbering used by `nth`:

    (fifth x) == (nth 4 x)

`setf` may be used with each of these functions to store into the indicated position of a list.

[Function]
`rest list`

`rest` means the same as `cdr` but mnemonically complements `first`. `setf` may be used with `rest` to replace the cdr of a list with a new value.

[Function]
`nthcdr n list`

`(nthcdr n list)` performs the `cdr` operation n times on list, and returns the result. For example:

    (nthcdr 0 '(a b c)) => (a b c)
    (nthcdr 2 '(a b c)) => (c)
    (nthcdr 4 '(a b c)) => ()

In other words, it returns the nth cdr of the list.

Compatibility note: This is similar to the Interlisp function `nth`, except that the Interlisp function is one-based instead of zero-based.

    (car (nthcdr n x)) == (nth n x)

X3J13 voted in January 1989 (ARGUMENTS-UNDERSPECIFIED) to clarify that the argument n must be a non-negative integer.

[Function]
`last list`

`last` returns the last cons (not the last element!) of list. If list is `()`, it returns `()`. For example:

    (setq x '(a b c d))
    (last x) => (d)
    (rplacd (last x) '(e f))
    x => '(a b c d e f)
    (last '(a b c . d)) => (c . d)

X3J13 voted in June 1988 (LAST-N) to extend the `last` function to accept an optional second argument. The effect is to make `last` complementary in operation to `butlast`. The new description (with some additional examples) would be as follows.

[Function]
`last list &optional (n 1)`

`last` returns the tail of the list consisting of the last n conses of list. The list may be a dotted list. It is an error if the list is circular.

The argument n must be a non-negative integer. If n is zero, then the atom that terminates the list is returned. If n is not less than the number of cons cells making up the list, then the list itself is returned.

For example:

    (setq x '(a b c d))
    (last x) => (d)
    (rplacd (last x) '(e f))
    x => '(a b c d e f)
    (last x 3) => (d e f)
    (last '()) => ()
    (last '(a b c . d)) => (c . d)
    (last '(a b c . d) 0) => d
    (last '(a b c . d) 2) => (b c . d)
    (last '(a b c . d) 1729) => (a b c . d)

[Function]
`list &rest args`

`list` constructs and returns a list of its arguments. For example:

    (list 3 4 'a (car '(b . c)) (+ 6 -2)) => (3 4 a b 4)

    (list) => ()
    (list (list 'a 'b) (list 'c 'd 'e)) => ((a b) (c d e))

[Function]
`list* arg &rest others`

`list*` is like `list` except that the last cons of the constructed list is ``dotted.'' The last argument to `list*` is used as the cdr of the last cons constructed; this need not be an atom. If it is not an atom, then the effect is to add several new elements to the front of a list. For example:

    (list* 'a 'b 'c 'd) => (a b c . d)

This is like

    (cons 'a (cons 'b (cons 'c 'd)))

Also:

    (list* 'a 'b 'c '(d e f)) => (a b c d e f)
    (list* x) == x

[Function]
`make-list size &key :initial-element`

This creates and returns a list containing size elements, each of which is initialized to the `:initial-element` argument (which defaults to `nil`). size should be a non-negative integer. For example:

    (make-list 5) => (nil nil nil nil nil)
    (make-list 3 :initial-element 'rah) => (rah rah rah)

[Function]
`append &rest lists`

The arguments to `append` are lists. The result is a list that is the concatenation of the arguments. The arguments are not destroyed. For example:

    (append '(a b c) '(d e f) '() '(g)) => (a b c d e f g)

Note that `append` copies the top-level list structure of each of its arguments except the last. The function `concatenate` can perform a similar operation, but always copies all its arguments. See also `nconc`, which is like `append` but destroys all arguments but the last.

The last argument actually need not be a list but may be any Lisp object, which becomes the tail end of the constructed list. For example, `(append '(a b c) 'd)` => `(a b c . d)`.

`(append x '`()`)` is an idiom once frequently used to copy the list x, but the `copy-list` function is more appropriate to this task.

[Function]
`copy-list list`

This returns a list that is `equal` to list, but not `eq`. Only the top level of list structure is copied; that is, `copy-list` copies in the cdr direction but not in the car direction. If the list is ``dotted,'' that is, `(cdr (last list))` is a non-`nil` atom, this will be true of the returned list also. See also `copy-seq` and `copy-tree`.

[Function]
`copy-alist list`

`copy-alist` is for copying association lists. The top level of list structure of list is copied, just as for `copy-list`. In addition, each element of list that is a cons is replaced in the copy by a new cons with the same car and cdr.

[Function]
`copy-tree object`

`copy-tree` is for copying trees of conses. The argument object may be any Lisp object. If it is not a cons, it is returned; otherwise the result is a new cons of the results of calling `copy-tree` on the car and cdr of the argument. In other words, all conses in the tree are copied recursively, stopping only when non-conses are encountered. Circularities and the sharing of substructure are not preserved.

Compatibility note: This function is called `copy` in Interlisp.

[Function]
`revappend x y`

`(revappend x y)` is exactly the same as `(append (reverse x) y)` except that it is potentially more efficient. Both x and y should be lists. The argument x is copied, not destroyed. Compare this with `nreconc`, which destroys its first argument.

[Function]
`nconc &rest lists`

`nconc` takes lists as arguments. It returns a list that is the arguments concatenated together. The arguments are changed rather than copied. (Compare this with `append`, which copies arguments rather than destroying them.) For example:

    (setq x '(a b c))
    (setq y '(d e f))
    (nconc x y) => (a b c d e f)
    x => (a b c d e f)

Note, in the example, that the value of `x` is now different, since its last cons has been `rplacd`'d to the value of `y`. If one were then to evaluate `(nconc x y)` again, it would yield a piece of ``circular'' list structure, whose printed representation would be `(a b c d e f d e f d e f ...)`, repeating forever; if the `*print-circle*` switch were non-`nil`, it would be printed as `(a b c . #1=(d e f . #1#))`.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify the permissible side effects of certain operations. The side-effect behavior of `nconc` is specified by a recursive relationship outlined in the following table, in which a call to `nconc` matching the earliest possible pattern on the left is required to have side-effect behavior equivalent to the corresponding expression on the right.

    (nconc)                 nil     ;No side effects
    (nconc nil . r)         (nconc . r)
    (nconc x)               x
    (nconc x y)             (let ((p x) (q y))
                              (rplacd (last p) q)
                              p)
    (nconc x y . r)         (nconc (nconc x y) . r)

[Function]
`nreconc x y`

`(nreconc x y)` is exactly the same as `(nconc (nreverse x) y)` except that it is potentially more efficient. Both x and y should be lists. The argument x is destroyed. Compare this with `revappend`.

    (setq planets '(jupiter mars earth venus mercury))
    (setq more-planets '(saturn uranus pluto neptune))
    (nreconc more-planets planets)
    => (neptune pluto uranus saturn jupiter mars earth venus mercury)
      and now the value of more-planets is not well defined

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify the permissible side effects of certain operations; `(nreconc x y)` is permitted and required to have side-effect behavior equivalent to that of `(nconc (nreverse x) y)`.

[Macro]
`push item place`

The form place should be the name of a generalized variable containing a list; item may refer to any Lisp object. The item is consed onto the front of the list, and the augmented list is stored back into place and returned. The form place may be any form acceptable as a generalized variable to `setf`. If the list held in place is viewed as a push-down stack, then `push` pushes an element onto the top of the stack. For example:

    (setq x '(a (b c) d))
    (push 5 (cadr x)) => (5 b c)  and now x => (a (5 b c) d)

The effect of `(push item place)` is roughly equivalent to

    (setf place (cons item place))

except that the latter would evaluate any subforms of place twice, while `push` takes care to evaluate them only once. Moreover, for certain place forms `push` may be significantly more efficient than the `setf` version.

X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER) to clarify order of evaluation (see section 7.2). Note that item is fully evaluated before any part of place is evaluated.

[Macro]
`pushnew item place &key :test :test-not :key`

The form place should be the name of a generalized variable containing a list; item may refer to any Lisp object. If the item is not already a member of the list (as determined by comparisons using the `:test` predicate, which defaults to `eql`), then the item is consed onto the front of the list, and the augmented list is stored back into place and returned; otherwise the unaugmented list is returned. The form place may be any form acceptable as a generalized variable to `setf`. If the list held in place is viewed as a set, then `pushnew` adjoins an element to the set; see `adjoin`.

The keyword arguments to `pushnew` follow the conventions for the generic sequence functions. See chapter 14. In effect, these keywords are simply passed on to the `adjoin` function.

`pushnew` returns the new contents of the place. For example:

    (setq x '(a (b c) d))
    (pushnew 5 (cadr x)) => (5 b c)   and now x => (a (5 b c) d)
    (pushnew 'b (cadr x)) => (5 b c)  and x is unchanged

The effect of

    (pushnew item place :test p)

is roughly equivalent to

    (setf place (adjoin item place :test p))

except that the latter would evaluate any subforms of place twice, while `pushnew` takes care to evaluate them only once. Moreover, for certain place forms `pushnew` may be significantly more efficient than the `setf` version.

X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER) to clarify order of evaluation (see section 7.2). Note that item is fully evaluated before any part of place is evaluated.

[Macro]
`pop place`

The form place should be the name of a generalized variable containing a list. The result of `pop` is the `car` of the contents of place, and as a side effect the `cdr` of the contents is stored back into place. The form place may be any form acceptable as a generalized variable to `setf`. If the list held in place is viewed as a push-down stack, then `pop` pops an element from the top of the stack and returns it. For example:

    (setq stack '(a b c))
    (pop stack) => a  and now stack => (b c)

The effect of `(pop place)` is roughly equivalent to

    (prog1 (car place) (setf place (cdr place)))

except that the latter would evaluate any subforms of place three times, while `pop` takes care to evaluate them only once. Moreover, for certain place forms `pop` may be significantly more efficient than the `setf` version.

X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER) to clarify order of evaluation (see section 7.2).

[Function]
`butlast list &optional n`

This creates and returns a list with the same elements as list, excepting the last n elements. n defaults to 1. The argument is not destroyed. If the list has fewer than n elements, then `()` is returned. For example:

    (butlast '(a b c d)) => (a b c)
    (butlast '((a b) (c d))) => ((a b))
    (butlast '(a)) => ()
    (butlast nil) => ()

The name is from the phrase ``all elements but the last.''

[Function]
`nbutlast list &optional n`

This is the destructive version of `butlast`; it changes the cdr of the cons n+1 from the end of the list to `nil`. n defaults to 1. If the list has fewer than n elements, then `nbutlast` returns `()`, and the argument is not modified. (Therefore one normally writes `(setq a (nbutlast a))` rather than simply `(nbutlast a)`.) For example:

    (setq foo '(a b c d))
    (nbutlast foo) => (a b c)
    foo => (a b c)
    (nbutlast '(a)) => ()
    (nbutlast 'nil) => ()

[Function]
`ldiff list sublist`

list should be a list, and sublist should be a sublist of list, that is, one of the conses that make up list. `ldiff` (meaning ``list difference'') will return a new (freshly consed) list, whose elements are those elements of list that appear before sublist. If sublist is not a tail of list (and in particular if sublist is `nil`), then a copy of the entire list is returned. The argument list is not destroyed. For example:

    (setq x '(a b c d e))
    (setq y (cdddr x)) => (d e)
    (ldiff x y) => (a b c)

    but (ldiff '(a b c d) '(c d)) => (a b c d)

since the sublist was not `eq` to any part of the list.

Next: Alteration of List Up: Lists Previous: Conses