Función de lista de diferencia recursiva lineal en Common Lisp

Question

Estaba revisando esto tutorial para la diversión, y quedé estancado en lo último que dice, "Ejercicio: Dar una implementación linealmente recursiva de unión y diferencia". (para una lista)

Unión, sin sudor.

Diferencia, sudor.

Un intento se ve así. . .

(defun list-diff (L1 L2)
  (cond
    ((null L1) L2) 
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

Ahora, eso devuelve todos los elementos que están en L1 que no están en L2, pero solo devuelve todo L2 (obviamente). De manera similar, si cambio L2 en la línea 3 a " nil " ;, entonces solo devuelve todos los L1 que no están en L2, pero ninguno de L2.

Mis intentos de solucionar los problemas no parecen recursivos, y cuando lo son, al final obtengo desbordamientos de pila (como si intentara llamar (list-diff L2 L1) en algún lugar).

Cualquiera de sus otros ejercicios, como la intersección de listas, solo requiere ejecutar los elementos de L1. Aquí, quiero golpear los elementos cruciales de L2, o correr (list-diff L2 L1) y luego unir los resultados de ambos, pero eso ya no es linealmente recursivo.

¿Pensamientos?

(no es tarea, en realidad. Solo pensé que intentaría mirar un poco de LISP por diversión)

EDITAR: una función que hace esto correctamente, según las respuestas es:

(defun list-diff (L1 L2)
  (cond
    ((null L1) nil)
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

Answer 1

La establecer diferencia L1 \ L2 se define como todos los elementos e de tal manera que e está en L1 pero e no en L2. Así que me parece que tu segundo intento es realmente correcto:

  

Del mismo modo, si cambio el L2 en línea   3 a " nil " ;, entonces solo devuelve todos   de L1 que no están en L2, pero ninguno de   L2.

Parece que estás intentando calcular la diferencia simétrica , aunque no lo es Me queda claro que esto es lo que solicita el ejercicio.

Si desea ser inteligente al respecto, probablemente pueda pasar una tercera lista a la función para que sirva como acumulador. Cuando L1 tiene elementos, empuje el primer elemento en el acumulador (y llame recursivamente) cuando (nulo (miembro (primer L1) L2)) . Cuando L1 es nulo, verifique los elementos de L2 en la lista del acumulador, haciendo lo mismo. Cuando L1 y L2 son nulos, devuelva la lista de acumuladores.

Answer 2

En Lisp, esta es la definición de 'establecer diferencia':

set-difference list1 list2 &key (test #'eql) test-not (key #'identity)
   Function
   Returns a list of elements of list1 that do not appear in list2. 

Esa es tu implementación modificada:

(defun list-diff (L1 L2)
  (cond
    ((null L1) L1)
    ((member (first L1) L2) (list-diff (rest L1) L2))
    (t (cons (first l1) (list-diff (rest l1) l2)))))