3

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.

4
  • 1
    Define "shared items". Do you mean list elements? How do you define "shared", i.e., what equality predicate do you want to determine sameness of list elements: eq, equal, something else? The question is not clear, so far.
    – Drew
    Jan 9, 2020 at 17:12
  • Added examples.
    – ideasman42
    Jan 10, 2020 at 8:35
  • The question remains - equality comparison with what predicate? eq? equal? Python examples don't tell us how you want to compare Lisp list elements. See, for example, the difference between memq and member.
    – Drew
    Jan 10, 2020 at 16:40
  • For the purpose of this question, memq seems reasonable, although both can be useful.
    – ideasman42
    Jan 11, 2020 at 2:18

2 Answers 2

6

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.

2
  • While this is a good answer it would be faster if there is no need to build the intersection first, since the result only needs to be a boolean. This isn't hard to write a function for that of course - if elisp doesn't have it included.
    – ideasman42
    Jan 10, 2020 at 8:42
  • 1
    @ideasman42 I am not aware of such builtin function, and dash.el doesn't have such function, so it's likely you need to write it by yourself.
    – xuchunyang
    Jan 10, 2020 at 8:55
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.