删除重复项并对列表进行排序

我正在尝试编写一个过程，该过程采用一个可能包含或不包含重复项的列表，然后按排序顺序返回没有重复项的列表。到目前为止我想到的是：

(define (remove-duplicated list)
    (if (null? list)
       '()
        (if (= (car list) (cadr list))
            (cdr list)
            (cons (car list) (remove-duplicates (cdr list))))))  

除了对列表进行排序之外，我不太确定问题是什么。例如，如果我输入

(remove-duplicates '(3 3 4 5 6 6 7))

returns

(3 4 5 6 6 7)

一个相当简单的过程，将接受一个可能或可能不的列表 包含重复项，然后返回没有任何重复项的列表 包括在内，并按排序顺序。

至少有两种方法可以做到这一点：

• 删除重复项后对列表进行排序；或者
• 列表排序后删除重复项。

奥斯卡·洛佩兹指出 https://stackoverflow.com/a/20084810/1281433 that

[您的]实施失败，因为您只测试了两个 连续的值，你必须在其余的元素中搜索当前元素 列表中，使用member。

如果删除重复项，这将是一个问题before排序，因为列表中的给定元素可能在列表中的其他任何位置都有重复项。但是，如果您首先对列表进行排序，那么您将保证任何重复元素do立即遵循原始列表，因此您无需检查整个列表。如果列表已排序，则删除重复项会更容易，但删除重复元素后对列表进行排序并不容易，因此首先对列表进行排序确实有意义，然后then删除重复项。 （我想你可以更有效地编写你自己的sort-and-remove-duplicates程序，但几乎可以肯定不是真正必要的。）

你的代码，如果你假设list已经排序了，是almost正确的。有必要进行两处调整：

1. 在基本情况下，您只需检查是否(null? list)。但是，对于非空列表，您可以比较(car list) and (cadr list)，但如果list只有一个元素，那么(cadr list)是一个错误。幸运的是，只有一个元素的列表没有重复项，因此您的基本情况可以是(or (null? list) (null? (cdr list))).
2. The then第二个的一部分if需要是(remove-duplicated (cdr list)), not (cdr list)， 自从list仍然可以有更多的重复项（例如，(x x x ...) or (x x y y ...)).

这是经过这些修改和一些注释的代码：

(define (remove-duplicated list)
  ;; remove duplicates from a *sorted* list.  Because the 
  ;; list is sorted, any duplicates of an element will
  ;; immediately follow the first occurrence of the element.
  ;;---------------------------------------------------------
  ;; If the list has the form () or (x)
  (if (or (null? list)
          (null? (cdr list)))
      ;; then it has no duplicates, so return it
      list
      ;; otherwise, if the list looks like (x x ...)
      (if (= (car list) (cadr list))
          ;; then you can discard the first element, but you
          ;; still need to remove duplicates from the rest of
          ;; the list, since there can be more duplicates later
          (remove-duplicated (cdr list))
          ;; otherwise, you need the first element of the list
          ;; and can simply remove-duplicated from the rest.
          (cons (car list) (remove-duplicated (cdr list))))))  

这按预期工作：

(remove-duplicated '(1 1 2 3 3 4 5 6))
;=> '(1 2 3 4 5 6)