We have already seen how we can use the built-in function member to test set membership. LISP also defines functions like (intersection L1 L2), (union L1 L2) and (difference L1 L2) for boolean operations on sets. In fact, these functions are not difficult to implement. Consider the following implementation of set intersection:

(defun list-intersection (L1 L2)
  "Return a list containing elements belonging to both L1 and L2."
  (cond
   ((null L1) nil)
   ((member (first L1) L2) 
    (cons (first L1) (list-intersection (rest L1) L2)))
   (t (list-intersection (rest L1) L2))))

A trace of executing the function is given below:

USER(80): (trace list-intersection)
(LIST-INTERSECTION)
USER(81): (list-intersection '(1 3 5 7) '(1 2 3 4))
 0: (LIST-INTERSECTION (1 3 5 7) (1 2 3 4))
   1: (LIST-INTERSECTION (3 5 7) (1 2 3 4))
     2: (LIST-INTERSECTION (5 7) (1 2 3 4))
       3: (LIST-INTERSECTION (7) (1 2 3 4))
         4: (LIST-INTERSECTION NIL (1 2 3 4))
         4: returned NIL
       3: returned NIL
     2: returned NIL
   1: returned (3)
 0: returned (1 3)
(1 3)

Keywords: Lisp string,lisp command,lisp comment,lisp manual,lisp programme,lisp function list,lisp object