删除流中的重复项(方案)

Question

我正在尝试在方案 R5RS 中删除流中的重复项。这是我的代码。

(define (remove-duplicates lst)
  (cond ((stream-null?? lst) stream-null?)
        ((not (memq (stream-car lst) (stream-cdr lst)))
         (cons-stream (stream-car lst) (remove-duplicates (stream-cdr lst))))
        (else (remove-duplicates (stream-cdr lst)))))
(define (memq item x)
  (cond ((stream-null?? x) #f)
        ((eq? item (stream-car x)) x)
        (else (memq item (stream-cdr x)))))

我不明白为什么这不起作用。任何解决方案或帮助将不胜感激。

Answer 1

"

不起作用"是一个非常模糊的问题描述，但无论如何我都会尝试回答。

memq并不懒惰，即使是懒惰，出于相对明显的原因，您也无法测试无限流的成员资格。

为了保持流的懒惰，您无法通过"向前"来决定是否应该包含某个项目，只能通过"向后"来决定 - 未来对您来说是隐藏的，您只能根据过去做出决定。

你需要扭转问题 - 而不是过滤掉除最后一个以外的所有实例，你保留第一个并过滤掉其余的，如果你最终到达那里时有任何结果。
（在无穷无尽的流中，一旦找到某些东西就很容易删除它，但不可能发现某些东西不存在。

stream-filter 对于筛选很有用，结果可能如下所示：

(define (remove-duplicates lst)
  (if (stream-null? lst)
      stream-null
      (stream-cons (stream-car lst) 
                   (remove-duplicates 
                    (stream-filter (lambda(x) (not (eq? x (stream-car lst)))) 
                                   (stream-cdr lst))))))