title: Linearly recursive list-difference function in Common Lisp
body: <p>I was going through <a href="http://www.cs.sfu.ca/CC/310/pwfong/Lisp/1/tutorial1.html" rel="nofollow noreferrer">this</a> 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)</p>
  
  <p>Union, no sweat. </p>
  
  <p>Difference, sweat. </p>
  
  <p>An attempt looks like this. . .</p>
  
  <pre><code>(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))
    )
  )
  </code></pre>
  
  <p>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. </p>
  
  <p>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). </p>
  
  <p>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. </p>
  
  <p>Thoughts? </p>
  
  <p>(not homework, really. I just thought I'd try to look at some LISP for fun.)</p>
  
  <p>EDIT: a function that does this properly, based on the responses is:</p>
  
  <pre><code>(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))
    )
  )
  </code></pre>