How to check if two lists share any elements?

Question

Besides looping over list items and comparing, what is a good way in elisp to check if there are any shared items between two lists?

For example, in Python this can be done with sets or list comprehension.

a = [1, 2, 3]
b = [3, 5, 0]

items_shared = bool(set(a) & set(b))

Or by checking in a loop.

items_shared = any(True for v in a if v in b)

---

Edit: for the purpose of this question, the same comparison rules for memq seem reasonable.

Answer 1

You can use seq-intersection, it is documented in its docstring and (elisp) Sequence Functions:

seq-intersection is a compiled Lisp function in `seq.el'.

(seq-intersection SEQUENCE1 SEQUENCE2 &optional TESTFN)

Return a list of the elements that appear in both SEQUENCE1 and SEQUENCE2. Equality is defined by TESTFN if non-nil or by `equal' if nil.

for example,

(seq-intersection '(2 3 4 5) '(1 3 5 6 7))
;; => (3 5)

Another choice is cl-intersection from cl-lib.el, unlike seq-intersection, it works for just lists, and it uses eql/eq for testing by default.

Answer 2

I think xuchunyang's is the correct answer, as seq-intersection is a generic function that can work on any built-in or user-defined sequence type, accepts a custom equality predicate, and perfectly conveys the intention, which is to determine whether two sequences intersect.

All these benefits come with some performance overhead, of course, but the performance of seq-intersection should be fine for many applications. However, OP voiced some performance concerns in a comment.

If one really wants to juice this for all the speed they can get, my first suggestion would be to step back and think about whether the application can be designed so that list intersection, an O(MN) operation at worst, isn't necessary. For example, can the lists be sorted, or are their lengths known ahead of time, or can a hash table be used instead, etc.

Failing all of that, a custom intersection function can be written. For generalisation to all sequence types, one should continue to use the seq.el library:

(defun my-seq-intersect-p (seq1 seq2 &optional testfn)
  "Return non-nil if any elements of SEQ1 appear in SEQ2.
Comparison is done with TESTFN if non-nil, otherwise `equal'."
  (seq-some (lambda (elem)
              (seq-contains-p seq2 elem testfn))
            seq1))

In my benchmarks, this runs slightly faster than seq-intersection because of reduced consing and garbage collection, but the difference isn't great.

If the function need only accept lists and the required equality predicate is known ahead of time, then the function can be made far faster as follows:

(defun my-list-intersect-p (list1 list2)
  "Return non-nil if any elements of LIST1 appear in LIST2.
Comparison is done with `equal'."
  (while (and list1 (not (member (car list1) list2)))
    (pop list1))
  list1)

Other lookup functions like memq, cl-member, etc. can be used in place of member if needed.

There is also room for future optimisations in seq.el itself.