Função de diferença de lista linearmente recursiva em Lisp comum

Question

Eu estava passando isto Tutorial por diversão e ficou preso na última coisa que ele diz: "Exercício: faça uma implementação linearmente recursiva da união e da diferença". (para uma lista)

União, sem suor.

Diferença, suor.

Uma tentativa se parece com isso. . .

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

Agora, isso retorna todos os elementos que estão em L1 que não estão no L2, mas apenas retorna todo o L2 (obviamente). Da mesma forma, se eu alterar o L2 na linha 3 para "nil", ele apenas retorna todo o L1 que não está em L2, mas nenhum de L2.

Minhas tentativas de trabalho não parecem recursivas e, quando estão, acabo recebendo fluxos de pilha (como se eu tentar ligar (listff l2 L1) em algum lugar).

Qualquer um de seus outros exercícios, como a interferência da lista, requer apenas os elementos de L1. Aqui, quero atingir os elementos cruciais de L2, ou Run (List-Diff L2 L1) e, em seguida, unir os resultados de ambos, mas isso não é mais linearmente recursivo.

Pensamentos?

(Não é dever de casa, realmente. Eu apenas pensei em tentar olhar para um pouco de diversão.)

Editar: uma função que faz isso corretamente, com base nas respostas é:

(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

o Defina a diferença A Operação L1 L2 é definida como todos os elementos e tal que E está em L1, mas e não em L2. Então, parece -me que sua segunda tentativa está realmente correta:

Da mesma forma, se eu alterar o L2 na linha 3 para "nil", ele apenas retorna todo o L1 que não está em L2, mas nenhum de L2.

Parece que você está tentando calcular o diferença simétrica, embora não esteja claro para mim que é isso que o exercício solicita.

Se você quiser ser inteligente, provavelmente poderá passar uma terceira lista na função para servir como um acumulador. Quando L1 tiver elementos, empurre o primeiro elemento para o acumulador (e chame recursivamente) quando (null (member (first L1) L2)). Quando L1 for nulo, verifique os elementos de L2 na lista do acumulador, fazendo a mesma coisa. Quando L1 e L2 forem nulos, retorne a lista de acumuladores.

Answer 2

Em Lisp, esta é a definição de 'diferença de conjunto':

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. 

Essa é a sua implementação 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)))))