Intersection of multiple lists in elisp

Question

How to get the intersection of multiple lists using elisp? I'm a elisp newbie but I'm imagining there is some builtin function or a nicer solution using reduce. I cobbled this together, but it seems overly complicated.

;; get the intersection of these lists
;; result should be (3 4 5)
(setq test '((0 1 2 3 4 5) (2 3 4 5 6) (3 4 5 6 7)))

(require 'cl-lib)
(cl-remove-if-not
 (lambda (x) (cl-every
         (lambda (y) (> (length (memq x y) ) 0 ) )
         (cdr test) ) )
 (car test) )
;; ( 3 4 5)

Renzo · Accepted Answer · 2015-08-19T19:53:50.260

7

There is a cl-intersection that takes only two operands:

(cl-intersection '(0 1 2 3 4 5) '(2 3 4 5 6))

You can use it do define your own intersection:

(defun my-intersection(l)
    (cond ((null l) nil)
          ((null (cdr l)) (car l))
          (t (cl-intersection (car l) (my-intersection (cdr l))))))

(my-intersection '((0 1 2 3 4 5) (2 3 4 5 6) (3 4 5 6 7)))

Updated

Thanks to the @Tobias comment below, you could have in the new function the same keyword parameters of cl-intersection, that is (:test :test-not :key) and propagate them to all the calls to it inside the recursion.

Here is the extended version:

(defun my-intersection(l &rest cl-keys)
    (cond ((null l) nil)
          ((null (cdr l)) (car l))
          (t (apply 'cl-intersection (car l) (apply 'my-intersection (cdr l) cl-keys) cl-keys))))

edited Aug 19 '15 at 19:53

answered Jul 15 '15 at 05:56

Renzo

26,848
5
49
61

2

Proposal: Add an argument `&rest rest` and replace the `cl-intersection` by `(apply 'cl-intersection (car l) (apply 'my-intersection (cdr l) rest) rest)`. In this way you can use the optional arguments like `:test` and so on. Maybe as an extended version. – Tobias Aug 19 '15 at 16:47
What if I would like to do the same thing except with a vector? – Cameron Jan 27 '17 at 21:55

score 4 · Answer 2 · edited May 23 '17 at 12:15

Install dash third-party list manipulation library (follow instructions to install it). Then you need:

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

If you need a function that accepts variable number of lists, instead of a single list of lists, wrap it in a function using &rest keyword, like that:

(defun -intersection* (&rest list-of-lists)
  (-reduce '-intersection list-of-lists))
;; (-intersection* '(1 2 3 4) '(2 3 4 5) '(3 4 5 6)) ; => (3 4)

If it's the first time you use -reduce, it's a “fold” function: it takes a binary function, a list of elements, and reduces them to a final result one list element at a time. This answer explains the concept behind the fold.

Intersection of multiple lists in elisp

2 Answers2