如何判断Scheme列表是否为集合？求实现该判断函数的方案

你提到要写一个Scheme函数set?来判断列表是否是集合（也就是列表里没有重复元素），对应的C语言双重循环思路很清晰——检查每一对元素有没有重复。那我们把这个思路转换成Scheme的递归风格来实现就好啦。

先回顾下你的C语言逻辑：

int count = sizeof(array) / sizeof(array[0]);
for (int i = 0; i < count - 1; i++) {
for (int j = i + 1; j < count; j++) {
if (array[i] == array[j]) { //返回false }
}
}

这个逻辑的核心是：对于列表里的每个元素，检查它后面的所有元素有没有和它重复的；如果有任何一对重复，就不是集合；如果全部检查完都没有重复，就是集合。

那对应的Scheme实现可以这样写：

(define set?
  (lambda (lst)
    ; 空列表是集合
    (if (null? lst)
        #t
        ; 检查第一个元素是否在剩下的列表里出现过
        (if (member (car lst) (cdr lst))
            #f
            ; 递归检查剩下的列表是否是集合
            (set? (cdr lst))))))

逻辑解释： #

• 首先处理基准情况：空列表()本身就是一个集合，直接返回#t（真）。
• 对于非空列表，先取出第一个元素(car lst)，用member函数检查它是否存在于剩下的列表(cdr lst)中：
  • 如果member返回非#f，说明有重复元素，直接返回#f（假）。
  • 如果没有重复，就递归调用set?检查剩下的子列表是否是集合。

举几个测试例子验证下：

(set? '(1 2 3))   ; 返回 #t
(set? '(1 2 2 3)) ; 返回 #f
(set? '())        ; 返回 #t
(set? '(a b c a)) ; 返回 #f

这个实现完全对应了你给出的C语言双重循环的逻辑，只不过用Scheme的递归代替了迭代的循环，更符合函数式编程的风格。

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