[edit]

Infinite Streams

Introduction

We have seen how to support the illusion of manipulating a stream as a complete sequence, when in actuality we only compute as much of the stream as we need. We can exploit this technique to represent sequences efficiently as streams, even if the sequences are very long. But more importantly, we can use streams to represent sequences that are infinitely long. For instance, suppose we define the following:

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

Then integers represents the stream of all positive integers. More specifically, the stream-car of integers is 1 and the stream-cdr of integers is a promise equivalent to (integers-starting-from 2).

Using integers, we can define other infinite streams, such as the stream of integers that are not divisible by 7:

(define (divisible? x y)
  (= (remainder x y) 0))
(define no-sevens
  (stream-filter (lambda (x) (not (divisible? x 7)))
                 integers))

We can then find integers not divisible by 7 simply by accessing elements of this stream:

-> (stream-ref no-sevens 100)
117

Stream Procedures

The way we've been defining streams up until now is very similar to the way we define lists. Now we're going to take a more "streamy" approach.

We can take advantage of delayed evaluation to implicitly define streams. For example, we can define an infinite stream of all ones like this:

(define ones (cons-stream 1 ones))

This works much like the definition of a recursive procedure: ones is a pair whose car is 1 and whose cdr is a promise to evaluate ones. Evaluating the cdr gives us again a 1 and a promise to evaluate ones, and so on.

We can also define a stream procedure add-streams, which produces the elementwise sum of two streams:

(define (add-streams s1 s2)
  (stream-map + s1 s2)

For example, (add-streams ones ones) would produce a stream of all twos.

We can redefine then define integers implicitly:

(define integers (cons-stream 1 (add-streams ones integers)))

This defines integers to be a stream whose stream-car is 1 and whose stream-cdr is the sum of ones and integers. Thus, the second element of integers is 1 plus the first element of integers, or 2; the third element of integers is 1 plus the second element of integers, or 3; and so on. This definition works because, at any point, enough of the integers stream has been generated so that we can feed it back into the definition to produce the next integer.

Note on `stream-map`

Note that in the example above, we called stream-map with two streams. Previously, we used stream-map with just one stream:

-> (define x (cons-stream 1 (cons-stream 2 (cons-stram 3 the-empty-stream))))
-> (stream-map square x)
(1 #[stream with car 4])

You can use stream-map with any number of streams, given that the procedure you give has the corresponding number of arguments:

-> (stream-map + x x)
(2 #[stream with car 4])

Naturally, the actual definition of stream-map is slightly different, but don't worry about it for now.

We can also define the Fibonacci sequence in the same style:

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs) fibs))))

This definition says that fibs is a stream beginning with 0 and 1, such that the rest of the stream can be generated by adding fibs to itself shifted by one place.

Another stream operation that we can use is scale-stream. It takes in two arguments—a stream of integers and an integer—and multiplies all elements in the stream by the integer:

(define (scale-stream strm factor)
  (stream-map (lambda (x) (* x factor)) strm))

We can now define a stream of all the powers of 2 like so:

(define doubles (cons-stream 1 (scale-stream doubles 2)))

We can define the infinite stream of primes in a different, implicit way now:

(define primes
  (cons-stream 2
               (stream-filter prime?
                              (integers-starting-from 3))))

This might seem fairly straightforward—we start with the first prime, 2, and we then cons-stream the rest of the integers that are prime to it. However, the way that prime? is defined makes this problem a little more subtle.

We check if a number is prime by seeing whether it is divisible by any prime (not just any integer!) less than √(n):

(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) #t)
          ((divisible? n (stream-car ps)) #f)
          (else (iter (stream-cdr ps)))))
  (iter primes))

This is a recursive definition (much like you saw in trees!) since primes is defined in terms of the prime? predicate, which itself uses the primes stream. The reason this procedure works is that, at any point, enough of the primes stream has been generated to test the primality of the numbers we need to check next. That is, for every n we test for primality, either n is not prime (in which case there is a prime already generated that divides it) or n is prime (in which case there is a prime already generated -- i.e., a prime less than n -- that is greater than √(n))