Weird Common Lisp intersection behaviour

I'm trying to get the common elements of two lists. I've tried both the available intersection function and one I implemented myself, both giving the same weird result when trying to test them on lists like (a a ... a) and (a b c d ... z).

Whenever the first list contains only the same element several times and the second list begins with that element the result is the first list.

For example: (intersection '(2 2 2 2) '(2 2 2 3)) returns (2 2 2 2)

The intersection I implemented:

(defun presentp (a l)
  (cond ((null l) nil)
        ((and (atom (car l)) (equal a (car l))) t)
        ((not (atom (car l))) (presentp a (car l)))
        (t (presentp a (cdr l)))))

(defun intersectionp (a b)
  (cond ((not (and a b)) nil)
        ((presentp (car a) b) (append (list (car a)) (intersection (cdr a) b)))
        (t (intersection (cdr a) b))))

How can I get a good result on lists of that type? For example I want (2 2 2) from (intersection '(2 2 2 2) '(2 2 2 3)).

Solution

You need to remove matches from the b list.. When you found an 2 in (2 2 2 3) you should continue with (2 2 3) as b.

Also.. (append (list x) result-list) is the same as (cons x result-list) just with the same or fewer CPU cylces.

(defun intersection (a b)
  (cond ((not (and a b)) nil)
        ((presentp (car a) b)
         (cons (car a) 
               (intersection (cdr a) 
                             (remove (car a) b :count 1))))
        (t (intersection (cdr a) b))))