How to calculate difference between two sets in emacs lisp,the sets should be lists

Question

How to calculate the difference between two sets in Emacs Lisp? The sets should be lists. The programm should be very simple and short, or else I won't understand it. I'm a newbee.

Thx

Answer 1

When I write Elisp code that has lots of list data transformations, I use dash library, because it has loads of functions to work with lists. Set difference can be done with -difference:

(require 'dash)
(-difference '(1 2 3 4) '(3 4 5 6)) ;; => '(1 2)

Answer 2

There is a set-difference function in the Common Lisp extensions:

elisp> (require 'cl-lib)
cl-lib
elisp> (cl-set-difference '(1 2 3) '(2 3 4))
(1)

Answer 3

Here is a simple & short definition, which should be easy to understand. It is essentially the same as the set-difference function in the Common Lisp library for Emacs, but without any treatment of a TEST argument.

(defun set-diff (list1 list2 &optional key)
  "Combine LIST1 and LIST2 using a set-difference operation.
Optional arg KEY is a function used to extract the part of each list
item to compare.

The result list contains all items that appear in LIST1 but not LIST2.
This is non-destructive; it makes a copy of the data if necessary, to
avoid corrupting the original LIST1 and LIST2."
  (if (or (null list1)  (null list2))
      list1
    (let ((keyed-list2  (and key  (mapcar key list2)))
          (result       ()))
      (while list1
        (unless (if key
                    (member (funcall key (car list1)) keyed-list2)
                  (member (car list1) list2))
          (setq result  (cons (car list1) result)))
        (setq list1  (cdr list1)))
      result)))

Answer 4

GNU Emacs Lisp Reference Manual, Sets and Lists suggests using cl-lib's
cl-set-difference LIST1 LIST2 &key :test :test-not :key

(require 'cl-lib)
(cl-set-difference '(1 2 3) '(2 3 4))
(1)

Answer 5

Disclaimer: this is not an efficient way to do it in eLisp. An efficient way is through a hash-table with a hash function, but since you asked about lists, then here it is:

(defun custom-set-difference (a b)
  (remove-if
     #'(lambda (x) (and (member x a) (member x b)))
     (append a b)))

(custom-set-difference '(1 2 3 4 5) '(2 4 6))

(1 3 5 6)

(defun another-set-difference (a b)
  (if (null a) b
    (let (removed)
      (labels ((find-and-remove
                (c)
                (cond
                 ((null c) nil)
                 ((equal (car c) (car a))
                  (setq removed t) (cdr c))
                 (t (cons (car c) (find-and-remove (cdr c)))))))
        (setf b (find-and-remove b))
        (if removed
            (another-set-difference (cdr a) b)
          (cons (car a) (another-set-difference (cdr a) b)))))))

(another-set-difference '(1 2 3 4 5) '(2 4 6))

(1 3 5 6)

The second is slightly more efficient, because it will remove the elements as it makes consequent checks, but the first is shorter and more straight-forward.

Also note that lists are not good representation of sets because they naturally allow repetition. Hash maps are better for that purpose.