代码之家 › 专栏 › 技术社区 › Baltimark

常用Lisp中的线性递归列表差分函数

common-lisp lisp recursion algorithm

Baltimark · 技术社区 · 16 年前

我正在经历 this 为了好玩,他最后一句话就是:“练习:给出联合和差异的线性递归实现。”

团结,不流汗。

区别,汗水。

一次尝试看起来是这样的。…

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

我在工作区的尝试看起来不是递归的,当它们是递归的时,我最终会得到堆栈溢出(比如我尝试在某处调用(列出diff l2 l1))。

他的任何其他练习,如列表交集,只需要遍历l1的元素。在这里,我想从l2中删除关键元素,或者运行(列出diff l2 l1),然后合并两个元素的结果,但这不再是线性递归。

思想?

(不是家庭作业,真的。我只是想试着看一些口齿不清的笑话。)

编辑:根据响应正确执行此操作的函数是:

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

2 回复 | 直到 16 年前

zweiterlinde 16 年前

这个 set difference 操作l1 \l2被定义为所有元素e,这样e在l1中而不是在l2中。所以在我看来你的第二次尝试是正确的:

类似地,如果我更改了行中的l2 3到“零”,然后返回所有不在l2中的l1,但没有 L2。

你好像在计算 symmetric difference 尽管我不清楚这是运动要求的。

如果你想聪明点,你可以将第三个列表传递到函数中作为一个累加器。当l1有元素时,当 (null (member (first L1) L2)) . 当l1为空时,对照累加器列表检查l2的元素,执行相同的操作。当l1和l2为空时,返回累加器列表。

Rainer Joswig mmmmmm 16 年前

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