1

I'm trying to understand how this function works.

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
            (lambda (x)
              (not (divisible? x (stream-car stream))))
            (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

Simply, I use a stream that generates all the integers starting from 2 and, according to the book, it filters the rest of the stream that is not divisible by current element for each new element. How can this filter all the integers that are not divisible by current element without actually reading all the integers?

Will Ness
  • 70,110
  • 9
  • 98
  • 181

2 Answers2

1

The trick is to think how stream-filter works. It is a function from streams to other streams, and this means that it does not actually need to filter the elements of the stream yet: instead it can return a stream which, as you ask for its elements, will filter them suitably.

In particular here is an implementation of stream-filter which I have called filter-stream:

(define (filter-stream test? stream)
  (cond
    ((stream-empty? stream)
     stream)
    ((test? (stream-car stream))
     (cons-stream (stream-car stream)
                  (filter-stream test? (stream-cdr stream))))
    (else
     (filter-stream predicate? (stream-cdr stream)))))

You can see how this works: it chunters down the stream it is given until it finds an element which passes the filter (or until it runs out of stream), at which point it uses cons-stream to construct a new stream consisting of the element that passed the predicate and the result of filtering all the other elements with the same predicate. But constructing that stream doesn't involve calling the predicate on all its elements: it just requires you to make a promise that, at the point someone asks you for an element of that stream, you will indeed filter the elements suitably to return the appropriate element.

In other words stream-filter is a function which takes a stream, which is a potentially infinite object and returns another stream, which again is potentially infinite. And it does this by simply promising to you that, at the point when you ask for some prefix of that infinite stream, it will then compute it for you, safe in the knowledge that you can never ask for all the elements of the stream.

sieve itself then repeatedly stacks these streams on top of each other: each time it finds a prime it constructs a stream which filters out multiples of that prime, from the stream it has been given which is already filtering out all multiples of primes lower than the prime it has just found.

ignis volens
  • 7,040
  • 2
  • 12
  • So basically we take car of the stream and recurring sieve with filtered stream. Once it recurs with the new filtered stream, we again cons car of the stream and filter it again with another test?. – Alihan Aydin Sep 12 '22 at 17:48
  • 1
    @AlihanAydin: yes, except that in order to filter the stream you don't in fact need to do any work *yet*, you just need to promise to do work later. – ignis volens Sep 13 '22 at 10:19
1

The definitions

(define (sieve stream)
  (cons-stream (stream-car stream)
   (sieve 
     (stream-filter (lambda (x) (not (divisible? x (stream-car stream))))
       (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

mean that

primes 
= 
  (sieve
    (integers-starting-from 2))
=
  (cons-stream 2
    (sieve 
      (stream-filter (lambda (x) (not (divisible? x 2)))
        (integers-starting-from 3))))
=
  (cons-stream 2
    (cons-stream 3
      (sieve 
        (stream-filter (lambda (x) (not (divisible? x 3)))
          (stream-filter (lambda (x) (not (divisible? x 2)))
            (integers-starting-from 4))))))
=
  (cons-stream 2
    (cons-stream 3
      (sieve 
        (stream-filter (lambda (x) (not (divisible? x 3)))
          (stream-filter (lambda (x) (not (divisible? x 2)))
            (integers-starting-from 5))))))
=
  (cons-stream 2
    (cons-stream 3
      (cons-stream 5
        (sieve 
          (stream-filter (lambda (x) (not (divisible? x 5)))
            (stream-filter (lambda (x) (not (divisible? x 3)))
              (stream-filter (lambda (x) (not (divisible? x 2)))
                (integers-starting-from 6))))))))

and further

=
  ....
=
  (cons-stream 2
   (cons-stream 3
    (cons-stream 5
     (cons-stream 7
       (sieve 
         (stream-filter (lambda (x) (not (divisible? x 7)))
          (stream-filter (lambda (x) (not (divisible? x 5)))
           (stream-filter (lambda (x) (not (divisible? x 3)))
            (stream-filter (lambda (x) (not (divisible? x 2)))
             (integers-starting-from 9))))))))))
=
  ....
=
  (cons-stream 2
   (cons-stream 3
    (cons-stream 5
     (cons-stream 7
      (cons-stream 11
        (sieve 
          (stream-filter (lambda (x) (not (divisible? x 11)))
           (stream-filter (lambda (x) (not (divisible? x 7)))
            (stream-filter (lambda (x) (not (divisible? x 5)))
             (stream-filter (lambda (x) (not (divisible? x 3)))
              (stream-filter (lambda (x) (not (divisible? x 2)))
                (integers-starting-from 12))))))))))))
=
  ....

which, hopefully, should give you a clearer picture of what is going on here.

(NB: a follow up entry).

Will Ness
  • 70,110
  • 9
  • 98
  • 181