Common Lisp中的线性递归列表差异函数

Question

我正在浏览这个有趣的教程，并坚持他说的最后一件事，“练习：给出联合和差异的线性递归实现。” （列表）

联盟，没有汗水。

差异，汗水。

尝试看起来像这样。 。

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

现在，它返回L1中不在L2中的所有元素，但它只返回所有L2（显然）。类似地，如果我将第3行中的L2更改为“nil”，则它只返回不在L2中但不包含L2的所有L1。

我在解决方法上的尝试看起来并不是递归的，当它们出现时，我最终会得到堆栈溢出（就像我尝试在某处调用（list-diff L2 L1））。

他的任何其他练习，例如list-intersection，只需要遍历L1的元素。在这里，我想从L2中运行关键元素，或者运行（list-diff L2 L1），然后将两者的结果联合起来，但这不再是线性递归。

思考？

（不是功课，真的。我以为我会试着看一些LISP的乐趣。）

编辑：基于响应正确执行此操作的函数是：

(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

设置差异操作L1 \ L2被定义为e所在的所有元素e L1但不是L2。所以在我看来，你的第二次尝试实际上是正确的：

  

同样，如果我改变了L2   3到“nil”，然后它只返回所有   L1不在L2中，但没有   L2。

看起来您正在尝试计算对称差异，尽管它不是我明白这是演习所要求的。

如果你想要聪明一点，你可以将第三个列表传递给函数作为累加器。当L1有元素时，在（null（member（first L1）L2））时将第一个元素推入累加器（并递归调用）。当L1为null时，检查L2的元素与累加器列表，执行相同的操作。当L1和L2为空时，返回累加器列表。

Answer 2

在Lisp中，这是'set difference'的定义：

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. 

这是你修改过的实现：

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