如何修复R5RS Scheme中删除两列表公共元素的函数？

问题根源 #

你的代码核心问题出在delete函数——它仅删除列表中第一个匹配的元素，而非所有匹配项。当处理包含重复公共元素的列表时，未被删除的重复项会残留下来，导致结果不符合预期。

比如调用(remove-common '(1 2 3) '(1 2 2 3 4))时：

• 处理(remove l2 l1)时，原delete函数在删除2时只移除了l2中的第一个2，第二个2未被处理，最终残留下来得到(2 4)。

修复方案 #

修改delete函数，使其递归删除列表中所有与目标元素相等的项：

#| 删除列表lis中所有等于ele的元素 |#
(define (delete ele lis)
  (cond
    ((null? ele) lis)
    ((null? lis) '())
    ((equal? ele (car lis)) (delete ele (cdr lis))) ; 递归删除后续所有匹配元素
    (else (cons (car lis) (delete ele (cdr lis))))
    )
  )

#| 移除l1中所有存在于l2的元素 |#
(define (remove l1 l2)
  (if(null? l2) l1
     (if(null? l1) '()
        (remove (delete (car l2) l1) (cdr l2)) )))

(define (remove-common l1 l2)
  (list (remove l1 l2) (remove l2 l1)))

验证修复效果 #

修复后调用目标测试用例：

(remove-common '(1 2 3) '(1 2 2 3 4)) ; 输出：(() (4))

符合预期结果。其他原有测试用例也能正常工作：

(remove-common '(1 2) '(2 4)) ; 输出：((1) (4))
(remove-common '(1 3) '(2 4)) ; 输出：((1 3) (2 4))

内容的提问来源于stack exchange，提问作者csxyyyyy