Functions for Manipulating Lists

The following functions are meant for the special pairs which are lists, as described in Section 5.1. An argument which is not a list could give unexpected results. For example, length is used to determine the number of top level elements in a list.

1 lisp> (length '(a b c))
3
2 lisp> (length '(a b . c))
2

Selecting List Elements

(lastpair L:pair): any expr

Returns the last pair of a L. It is often useful to think of this as a pointer to the last element for use with destructive functions such as rplaca. If L is not a pair then a type mismatch error occurs.

    (de lastpair (l)
      (if (or (atom l) (atom (cdr l)))
        l
        (lastpair (cdr l))))

(lastcar L:pair): any expr

Returns the last element of the pair L. A type mismatch error results if L is not a pair.

(de lastcar (l)
(if (atom l) l (car (lastpair l))))

(nth L:pair N:integer): any expr

Returns the Nth element of the list L. If L is atomic or contains fewer than N elements, an out of range error occurs.

    (de nth (l n)
      (cond ((null l) (range-error))
            ((onep n) (first l))
            (t (nth (rest l) (sub1 n)))))

Note that this definition is not compatible with Common LISP. The Common LISP definition reverses the arguments and defines the car of a list to be the ”zeroth” element.

(pnth L:list N:integer): any expr

Returns a list starting with the nth element of the list L. Note that the result is a pointer to the nth element of L, a destructive function like rplaca can be used to modify the structure of L. If L is atomic or contains fewer than N elements, an out of range error occurs.

    (de pnth (l n)
      (cond ((onep n) l)
            ((not (pairp l)) (range-error))
            (t (pnth (rest l) (sub1 n)))))

5.3.1 Membership and Length of Lists

(member A:any L:list): extra-boolean expr

Returns nil if A is not equal to some top level element of the list L; otherwise it returns the remainder of L whose first element is equal to A.

    (de member (a l)
      (cond ((not (pairp l)) nil)
            ((equal a (car l)) l)
            (t (member a (cdr l)))))

(memq A:any B:list): extra-boolean expr

The same as member except that eq is used for comparison instead of equal. Note that the value returned by either member or memq is eq to the portion of the list which begins with A. Thus a function like rplaca may be used to alter A.

1 lisp> (setq sequence '(1 3 3))
(1 3 3)
2 lisp> (rplaca (memq 3 sequence) 2)
(2 3)
3 lisp> sequence
(1 2 3)

(de length (l)
(if (atom l) 0 (add1 (length (cdr l)))))

Constructing, Appending, and Concatenating Lists

1 lisp> (list (car '(left . right)) (list 'next))
(LEFT (NEXT))

(append U:list V:list): list expr

Returns a constructed list in which the last element of U is followed by the first element of V. The list U is copied, but V is not.

    (de append (u v)
      (cond ((not (pairp u)) v)
            (t (cons (first u) (append (rest u) v)))))

(nconc U:list V:list): list expr

Destructive version of append, the cdr of the last pair of U is modified to reference V. While append creates a copy of U, nconc uses U itself in constructing the result.

    (de nconc (u v)
      (if (not (pairp u))
        v
        (rplacd (lastpair u) v)))

    1 lisp> (setq a '(swan))
    (SWAN)
    3 lisp> (nconc a '(giles))
    (SWAN GILES)
    4 lisp> a
    (SWAN GILES)

(aconc U:list V:any): list expr

Destructively adds element V to the tail of list U.

    1 lisp> (setq a '(phillips))
    (PHILLIPS)
    2 lisp> (progn (aconc a 'posner) a)
    (PHILLIPS POSNER)

(lconc PTR:list LST:list): list expr

Effectively nconc, but avoids scanning from the front to the end of the first list by maintaining a pointer. PTR is a pair whose car is a list L and whose cdr is a reference to the last pair of L. The value returned is the updated pair PTR.

(progn (rplacd (cdr ptr) lst)
(rplacd ptr (lastpair lst)))

This function is useful for building lists from left to right, PTR should be initialized to (nil . nil) before the first call on lconc.

(tconc PTR:list ELM:any): list expr

Effectively aconc, but avoids scanning from the front to the end of the first list by maintaining a pointer. PTR is a pair whose car is a list L and whose cdr is a reference to the last pair of L. The value returned is the updated pair PTR.

    (progn (setq elm (ncons elm))
           (rplacd (cdr ptr) elm)
           (rplacd ptr elm))

This function is useful for building lists from left to right. PTR should be initialized to (nil . nil) before the first call on tconc.

Lists as Sets

A set is a list in which each element occurs only once. Since the order of elements in a set does not matter, these functions may not preserve order.

(adjoin ELEMENT:any SET:list): list expr

Add Element to SET if it is not already a member.

(de adjoin (elm set)
(if (member elm set) set (cons elm set)))

(adjoinq ELEMENT:any SET:list): list expr

Similar to adjoin except that eq is used to test for set membership.

    (de union (x y)
      (if (not (pairp x))
        y
        (union (rest x)
               (if (member (first x) y)
                 y
                 (cons (first x) y)))))

Notice that the two arguments to union are assumed to be sets, if either contains duplicates then the result may contain duplicates as well.

    1 lisp> (union '(1 2 2) '(3))
    (2 1 3)
    2 lisp> (union '(3) '(1 2 2))
    (3 1 2 2)

(unionq X:list Y:list): list expr

Similar to union except that eq is used to test for set membership.

(intersection U:list V:list): list expr

Returns the intersection of sets U and V.

    (de intersection (u v)
      (cond ((not (pairp u)) nil)
            ((member (car u) v)
             (cons (car u)
                   (intersection (cdr u) (delete (car u) v))))
            (t (intersection (cdr u) v))))

Notice that the two arguments to intersection are assumed to be sets, if either contains duplicates then the result may contain duplicates as well.

    1 lisp> (intersection '(1 2) '(2))
    (2)
    2 lisp> (intersection '(2 2) '(1 2 2))
    (2 2)

(intersectionq U:list V:list): list expr

Similar to intersection except that eq is used to test for set membership.

(list2set SET:list): list expr

Remove redundant elements from the top level of SET using equal.

(list2setq SET:list): list expr

Remove redundant elements from the top level of SET using eq.

5.3.2 Deleting Elements of Lists

Note that the functions suffixed by IP will destructively modify the list from which elements are being deleted. If you use such a function do not rely on the result being eq to the argument. The value returned will have all of the elements removed, but the modifications which have been made to the argument may not reflect this. In particular, the leading elements which are equal to the element being deleted will not be spliced out of the list.

1 lisp> (setq this '(a b c))
(a b c)
2 lisp> (deletip 'a this)
(b c)
3 lisp> this
(a b c)
2 lisp> (reversip this)
(c b a)
3 lisp> this
(a)

(delete U:any V:list): list expr

Returns V with the first top level occurrence of U removed from it. Equal is used for comparing elements. The result consists of a copy of the portion of U which comes before the deleted element, and the portion of U which follows the deleted element.

    (de delete (u v)
      (cond ((not (pairp v)) v)
            ((equal (car v) u) (cdr v))
            (t (cons (car v) (delete u (cdr v))))))

(del F:function U:any V:list): list expr

Generalized delete function with F as the comparison function.

1 lisp> (del '(lambda (i e) (> i e)) 0 '(-2 3 -1))
(-2 -1)

(deletip U:any V:list): list expr

The destructive version of delete, V may be modified.

(delq U:any V:list): list expr

Returns V with the first top level occurrence of U removed from it. Eq is used for comparing elements. The result consists of a copy of the portion of U which comes before the deleted element, and the portion of U which follows the deleted element.

(delqip U:any V:list): list expr

The destructive version of delq, V may be modified.

(delasc U:any V:a-list): a-list expr

Returns V with the first top level occurrence of (U . ANY) removed from it. Equal is used for comparisons. The result consists of a copy of the portion of U which comes before the deleted element, and the portion of U which follows the deleted element.

(delascip U:any V:a-list): a-list expr

The destructive version of delasc, V may be modified.

(delatq U:any V:a-list): a-list expr

Returns V with the first top level occurrence of (U . ANY) removed from it. Eq is used for comparisons. The result consists of a copy of the portion of U which comes before the deleted element, and the portion of U which follows the deleted element.

(delatqip U:any V:a-list): a-list expr

The destructive version of delatq, V may be modified.

5.3.3 List Reversal

(reverse U:list): list expr

Returns a copy of the top level of U in reverse order.

    (de reverse (l)
      (do ((result nil (cons (car pointer) result))
           (pointer l (cdr pointer)))
          ((not (pairp pointer)) result)))

(reversip U:list): list expr

The destructive version of reverse. The argument may be destructively modified to produce the result. Note also that the result may not be eq to the argument.

    (de reversip (l)
      (prog (next result)
            (while (pairp l)
              (setq next (cdr l))
              (setq result (rplacd l result))
              (setq l next))
            (return result)))

5.3.4 Functions for Sorting

The gsort module provides functions for sorting lists. Some of the functions take a comparison function as an argument. The comparison function takes two arguments and should return nil if the second argument should come before the first in the sorted result. A lambda expression is acceptable as a comparison function. Note that since sorting requires many comparisons, and thus many calls on the comparison function, the sort will be much faster if the comparison function is compiled.

(gsort TABLE:list LEQ-FN:id,function): list expr

Returns a sorted list. LEQ-FN is the comparison function used to determine the sorting order. The original TABLE is unchanged. Gsort uses a stable sorting algorithm. In other words, if X appears before Y in TABLE then X will appear before Y in the result unless X and Y are out of order.

(gmergesort TABLE:list LEQ-FN:id,function): list expr

The destructive version of gsort, this function is somewhat faster than gsort. Note that you should use the value returned by the function, don’t depend on the modified argument to give the right answer.

(idsort TABLE:list): list expr

Returns a list of the ids in TABLE, sorted into alphabetical order. The original list is unchanged. Case is not significant in determining the alphabetical order.

1 lisp> (setq x '(3 8 -7 2 1 5))
(3 8 -7 2 1 5)
2 lisp>     % sort from smallest to largest
2 lisp> (gsort x 'leq)
(-7 1 2 3 5 8)
3 lisp>     % sort from largest to smallest
3 lisp> (gmergesort x 'geq)
(8 5 3 2 1 -7)
4 lisp>     % note that the value of x has been modified
4 lisp> x
(3 2 1 -7)
5 lisp> (idsort '(the quick brown fox jumped over the lazy dog))
(brown dog fox jumped lazy over quick the the)

5.3 Functions for Manipulating Lists