Cómo calcular la diferencia entre dos conjuntos en emacs lisp, los conjuntos deben ser listas

elisp set

Question

¿Cómo calcular la diferencia entre dos conjuntos en Emacs Lisp? Los conjuntos deben ser listas. El programa debe ser muy simple y corto, o de lo contrario no lo entenderé. Soy un recién nacido.

Gracias

Answer 1

Descargo de responsabilidad: esta no es una manera eficiente de hacerlo en eLisp. Una forma eficiente es a través de una tabla hash con una función hash, pero como preguntaste acerca de las listas, aquí está:

(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)

El segundo es un poco más eficiente, ya que eliminará los elementos ya que hace los controles consiguientes, pero el primero es más corto y más directo.

También tenga en cuenta que las listas no son una buena representación de los conjuntos porque, naturalmente, permiten la repetición. Los mapas Hash son mejores para ese propósito.

Answer 2

Hay una función set-difference en las extensiones Common Lisp:

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

Answer 3

Aquí hay una definición simple y breve, que debería ser fácil de entender. Es esencialmente lo mismo que la función set-difference en la biblioteca Common Lisp para Emacs, pero sin ningún tratamiento de un argumento TEST.

(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

Cuando escribo el código Elisp que tiene muchas transformaciones de datos de lista, uso la biblioteca dash , porque tiene muchas funciones para trabajar con listas. La diferencia establecida se puede hacer con -difference :

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