2

我正在阅读本教程以获得乐趣，但被他说的最后一句话卡住了，“练习：给出联合和差异的线性递归实现。” （用于列表）

联盟，没有汗水。

差异，汗水。

尝试看起来像这样。. .

(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 中的所有 L1，但不返回 L2。

我对变通方法的尝试看起来并不递归，当它们出现时，我最终会遇到堆栈溢出（就像我尝试在某处调用 (list-diff L2 L1) 一样）。

他的任何其他练习，例如列表交集，只需要遍历 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))
  )
)
4

2 回答 2

6

集合差分操作 L1\L2被定义为所有元素 e 使得 e 在 L1 中但 e 不在 L2 中。所以在我看来你的第二次尝试实际上是正确的：

同样，如果我将第 3 行中的 L2 更改为“nil”，那么它只会返回不在 L2 中的所有 L1，但不返回 L2。

看起来您正在尝试计算对称差异，尽管我不清楚这是练习所要求的。

如果你想聪明一点，你可以将第三个列表传递给函数作为累加器。当 L1 有元素时，将第一个元素推入累加器（并递归调用） when (null (member (first L1) L2))。当 L1 为空时，根据累加器列表检查 L2 的元素，做同样的事情。当 L1 和 L2 为空时，返回累加器列表。

于 2009-03-04T14:18:33.667 回答
4

在 Lisp 中，这是“设置差异”的定义：

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)))))
于 2009-03-04T14:50:52.763 回答