Linearly recursive list-difference function in Common Lisp.

Question

I was going through this tutorial for fun, and got stuck on the very last thing he says, "Exercise: Give a linearly recursive implementation of union and difference." (for a list)

Union, no sweat.

Difference, sweat.

An attempt looks like this. . .

(defun list-diff (L1 L2)
  (cond
    ((null L1) L2) 
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

Now, that returns all the elements that are in L1 that aren't in L2, but it just returns all of L2 (obviously). Similarly, if I change the L2 in line 3 to "nil", then it just returns all of L1 that aren't in L2, but none of L2.

My attempts at work-arounds don't look recursive, and when they are, I end up getting stack-overflows (like if I try calling (list-diff L2 L1) somewhere).

Any of his other exercises, such as list-intersection, only require running through the elements of L1. Here, I want to strike the crucial elements from L2, or run (list-diff L2 L1) and then union the results from both, but that's not really linearly-recursive anymore.

Thoughts?

(not homework, really. I just thought I'd try to look at some LISP for fun.)

EDIT: a function that does this properly, based on the responses is:

(defun list-diff (L1 L2)
  (cond
    ((null L1) nil)
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

Answer 1

The set difference operation L1 \ L2 is defined as all elements e such that e is in L1 but e not in L2. So it looks to me like your second attempt is actually correct:

Similarly, if I change the L2 in line 3 to "nil", then it just returns all of L1 that aren't in L2, but none of L2.

It looks like you're trying to compute the symmetric difference, although it isn't clear to me that this is what the exercise requests.

If you want to be clever about it, you can probably pass a third list into the function to serve as an accumulator. When L1 has elements, push the first element into the accumulator (and call recursively) when (null (member (first L1) L2)). When L1 is null, check the elements of L2 against the accumulator list, doing the same thing. When L1 and L2 are null, return the accumulator list.

Answer 2

In Lisp this is the definition of 'set difference':

set-difference list1 list2 &key (test #'eql) test-not (key #'identity)
   Function
   Returns a list of elements of list1 that do not appear in list2.

That's your modified implementation:

(defun list-diff (L1 L2)
  (cond
    ((null L1) L1)
    ((member (first L1) L2) (list-diff (rest L1) L2))
    (t (cons (first l1) (list-diff (rest l1) l2)))))