删除流中的重复项（方案）

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

"Doesn't work"问题描述的很模糊，不过我还是尽量回答一下。

memq 不是懒惰，即使是懒惰，您也不能因为相对明显的原因测试无限流中的成员资格。

为了保持流的惰性，您不能通过查看 "forwards" 来决定是否应该包含一个项目，只能 "backwards" - 未来对您是隐藏的，您只能根据自己的决定关于过去。

您需要扭转问题 - 不是过滤掉除最后一个以外的所有实例，而是保留第一个并过滤掉其余实例，如果任何结果都存在你终于到了那里。
（层出不穷，找到东西很容易去掉，但是发现不存在的东西是不可能的。）

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))))))

删除流中的重复项（方案）

Remove duplicates in streams (Scheme)

scheme

stream

r5rs