scheme - Scheme：一个好的集合函数

Question

我需要编写一个好的集合函数来检查它的参数是否lst是一个正确表示的集合，即它是一个仅由整数组成的列表，没有重复，并返回真#t 或假#f。例如：

(good-set? (1 5 2)) => #t

(good-set? ()) => #t

(good-set? (1 5 5)) => #f

(good-set? (1 (5) 2)) => #f

所以我开始将函数编写为：

(define (good-set? lst) 

所以我不知道在此之后如何进行。有人可以帮忙吗？

Answer 1

为此，检查第一个数字是否重复，如果不是，则通过检查其余数字进行递归。像这样：

(define (good-set? list)
  (or (null? list)                      ; nothing left, good!
      (let ((head (car list)))
            (rest (cdr list)))
        (and (number? head)             ; a number
             (not (member = head rest)) ; not in the rest
             (good-set? rest)))))       ; check the rest

如果你需要member，那么

(define (member pred item list)
  (and (not (null? list))
       (or (pred item (car list))
           (member pred item (cdr list)))))

Answer 2

集合是内置在 Racket 标准库中的：我建议不要根据列表重新实现它们，除非你真的需要做一些定制的事情。

---

如果我们需要将此视为家庭作业，我建议使用设计方法来系统地解决这个问题。在这种情况下，请参阅How to Design Programs之类的关于设计适用于列表的函数的内容。作为一个简短的草图，我们会系统地弄清楚：

• 我正在使用的数据的结构是什么？
• 我考虑哪些测试用例？（包括基本情况）
• 函数的整体形状是什么？
• 的含义是natural recursion什么？
• 我如何结合结果natural recursion来计算总数的解决方案？

Answer 3

andmap正如@soegaard 所建议的那样，一种选择是使用和设置：

(define (good-set? lst)                  ; it's a good set if:
  (and (andmap integer? lst)             ; all its elements are integers and
       (= (length lst)                   ; the list's length equals the size
          (set-count (list->set lst))))) ; of a set with the same elements

但是，如果您不能使用集合或其他高级程序，则遍历列表并测试当前元素是否为整数并且不存在于列表中的其他位置（member用于此），对每个元素重复此测试直到有列表中没有更多元素。以下是总体思路，请填空：

(define (good-set? lst)
  (cond (<???>                ; if the list is empty
         <???>)               ; then it's a good set
        ((or <???>            ; if the 1st element is not an integer or
             <???>)           ; the 1st element is in the rest of the list
         <???>)               ; then it's NOT a good set
        (else                 ; otherwise
         (good-set? <???>)))) ; advance recursion