Intersection in Lisp-CodePudding

I am working with common Lisp Programming and I have an error in my code. I want to find the intersection between two lists, L1 and L2. The function only returns NIL.

(defun intersect (L1 L2)
(cond 
((null L1) nil)
((member (first L1) L2)
(t (intersect (rest L1) L2)))))

I don't quite understand what is saved in 't' after the recursion.

Thank you!

CodePudding user response：

Because after (null l1) you return nil instead to return what you have collected so far in an accumuluator (acc).

Also, it is very useful to distinguish the different test functions when testing for equality:

(defun intersect (l1 l2 &key (acc '()) (test #'eql))
  (cond ((null l1) (nreverse acc))
        ((member (car l1) l2 :test test) (intersect (cdr l1) l2 :acc (cons (car l1) acc) :test test))
        (t (intersect (cdr l1) l2 :acc acc :test test))))

CodePudding user response：

You're not using an editor that auto-indents Lisp such as Emacs or Vim.

Here is what I get when I paste your code into Vim, and then automatically reindent:

(defun intersect (L1 L2)
  (cond 
    ((null L1) nil)
    ((member (first L1) L2)
     (t (intersect (rest L1) L2)))))

I can see from the alignment of the (t (intersect that it's not at the same expected nesting level as the other cond cases. I've not counted a single parenthesis.

If the pieces are not put together in the way that you intend, your code will rarely work, other than by fluke (and flukes tend to usually work only for certain inputs).

I don't see in the code what you intend for the cond to produce in the case when (member (first L1) L2) is true. I think you want that case to be:

;; If the first element of L1 is found in L2, then the intersection
;; consists of a list of the first element followed by the intersection
;; of the rest of L1, and L2.
((member (first L1) L2) (cons (first L1) (intersect (rest L1) L2)))

This is very similar to the fallback case, in which the first element of L1 is not found in L2, and so the intersection is just the (intersect (rest L1) L2) part, without (first L1) or anything else being cons-ed onto the front:

(t (intersect (rest L1) L2))

The whole thing is then:

(defun intersect (L1 L2)
  (cond 
    ((null L1) nil)
    ((member (first L1) L2)
       (cons (first L1) (intersect (rest L1) L2)))
    (t (intersect (rest L1) L2)))))