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中的所有L1,但不返回L2.

我在解决方法上的尝试看起来并不是递归的,当它们出现时,我最终会得到堆栈溢出(就像我尝试在某处调用(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但E不在L2.所以在我看来,你的第二次尝试实际上是正确的:

类似地,如果我将第3行中的L2更改为"nil",那么它只返回不在L2中的所有L1,但不返回L2.

看起来你正试图计算对称差异,虽然我不清楚这是练习所要求的.

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