Funzione di differenza di elenco linearmente ricorsiva in Common Lisp

Question

Stavo attraversando questo tutorial per divertimento, e sono rimasto bloccato sull'ultima cosa che dice, "Esercizio: Dai un'implementazione linearmente ricorsiva di unione e differenza." (per un elenco)

Unione, niente sudore.

Differenza, sudore.

Un tentativo è simile al seguente. . .

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

Ora, questo restituisce tutti gli elementi che sono in L1 che non sono in L2, ma restituisce solo tutto L2 (ovviamente). Allo stesso modo, se cambio L2 nella riga 3 in "zero", allora restituisce solo tutto L1 che non è in L2, ma nessuno di L2.

I miei tentativi di soluzioni alternative non sembrano ricorsivi e, quando lo sono, finisco per ottenere stack-overflow (come se provassi a chiamare (list-diff L2 L1) da qualche parte).

Qualunque altro suo esercizio, come l'elenco-intersezione, richiede solo di scorrere gli elementi di L1. Qui, voglio colpire gli elementi cruciali da L2, o eseguire (list-diff L2 L1) e quindi unire i risultati da entrambi, ma non è più realmente linearmente ricorsivo.

Pensieri?

(non i compiti a casa, davvero. Pensavo solo di provare a guardare un po 'di LISP per divertimento.)

EDIT: una funzione che lo fa correttamente, in base alle risposte è:

(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

L'operazione imposta la differenza L1 \ L2 è definita come tutti gli elementi e tali che L1 ma e non in L2. Quindi mi sembra che il tuo secondo tentativo sia effettivamente corretto:

  

Allo stesso modo, se cambio L2 in linea   Da 3 a "zero", quindi restituisce tutto   di L1 che non sono in L2, ma nessuno di   L2.

Sembra che tu stia tentando di calcolare la differenza simmetrica , anche se non lo è mi è chiaro che questo è ciò che richiede l'esercizio.

Se vuoi essere intelligente, puoi probabilmente passare un terzo elenco nella funzione per fungere da accumulatore. Quando L1 ha elementi, inserisci il primo elemento nell'accumulatore (e chiama in modo ricorsivo) quando (null (membro (primo L1) L2)) . Quando L1 è nullo, controlla gli elementi di L2 rispetto all'elenco degli accumulatori, facendo la stessa cosa. Quando L1 e L2 sono nulli, restituisce l'elenco di accumulatori.

Answer 2

In Lisp questa è la definizione di 'imposta differenza':

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. 

Questa è l'implementazione modificata:

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