current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

For an assignment I handed in this code to remove duplicates from a stream. 

 (define (remove-duplicate lst)
  (cond ((stream-null? lst) '())
        ((not (member-stream? (stream-car lst) (stream-cdr lst)))
         (cons-stream (stream-car lst) (remove-duplicate (stream-cdr lst))))
        (else (remove-duplicate (stream-cdr lst)))))

(define (member-stream? item x)
  (cond ((stream-null? x) #f)
        ((eq? item (stream-car x)) x)
        (else (mems item (stream-cdr x)))))

Appearantly this isn't an ideal way to do this, but I can't see why. I tested it with a stream of numbers, and it correctly removed the duplicates and returned a stream.

stream-cons, stream-car, stream-cdr and stream-null are defined in the SICP book.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

It's not enough for your code to "work"; it also must work well. In particular, your code materialises the whole stream at the outset, which defeats the purpose of using a stream in the first place.

Instead of checking whether the current element exists in the rest of the stream, check whether the current element has already been seen. Yes, you have to keep track of the seen elements (preferably via a set, but if your Scheme implementation doesn't have that, a list will do in a pinch), but it will mean that your stream will continue to be a stream, rather than just be a glorified list.

Here's an implementation of the concept using lists to track the seen elements (I used SRFI 41 streams instead of SICP streams, since that's what I'm familiar with):

(define (unique-stream str)
  (stream-let recur ((seen '())
                     (str str))
    (if (stream-null? str)
        stream-null
        (let ((item (stream-car str)))
          (if (memv item seen)
              (recur seen (stream-cdr str))
              (stream-cons item (recur (cons item seen) (stream-cdr str))))))))
share|improve this answer
    
Thank you for the answer, and a better solution. Could you maybe please explain a bit more why it is bad that it materialises the whole stream at outset? –  user16655 Apr 21 at 18:59
    
Yes. The whole idea behind streams is that it's supposed to be lazy, that is, it only calculates the results that are explicitly asked for, and nothing more. Materialising more elements of a stream than explicitly asked for breaks the laziness premise of a stream. –  Chris Jester-Young♦ Apr 21 at 20:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.