2.21.8.1 Infinite streams

As a simple illustration of infinite streams, consider this definition of the natural numbers:

(define nats
  (stream-cons 0
    (stream-map add1 nats)))

the recursion works because it is offset by one from the initial stream-cons. Another sequence that uses the offset trick is this definition of the Fibonacci numbers:

(define fibs
  (stream-cons 1
    (stream-cons 1
      (stream-map +
        fibs
        (stream-cdr fibs)))))

Yet another sequence that uses the same offset trick is the Hamming numbers, named for the mathematician and computer scientist Richard Hamming, defined as all numbers that have no prime factors greater than 5; in other words, Hamming numbers are all numbers expressible as

2i x 3j x 5k

where i, j and k are non–negative integers. The Hamming sequence starts with 1 2 3 4 5 6 8 9 10 12 and is computed starting with 1, taking 2, 3 and 5 times all the previous elements with stream-map, then merging sub-streams and eliminating duplicates:

(define hamming
  (stream-cons 1
    (stream-unique =
      (stream-merge <
        (stream-map (lsec * 2) hamming)
        (stream-map (lsec * 3) hamming)
        (stream-map (lsec * 5) hamming)))))

It is possible to have an infinite stream of infinite streams. Consider the definition of power-table:

(define power-table
  (stream-of
    (stream-of (expt m n)
      (m in (stream-from 1)))
      (n in (stream-from 2))))

which evaluates to an infinite stream of infinite streams:

(stream
  (stream 1 4 9 16 25 ...)
  (stream 1 8 27 64 125 ...)
  (stream 1 16 81 256 625 ...)
  ...)

But even though it is impossible to display power-table in its entirety, it is possible to select just part of it:

(stream->list 10 (stream-ref power-table 1))
  => (1 8 27 64 125 216 343 512 729 1000)

This example clearly shows that the elements of a stream are computed lazily, as they are needed; (stream-ref power-table 0) is not computed, even when its successor is displayed, since computing it would enter an infinite loop.

Chris Reade shows how to calculate the stream of prime numbers according to the sieve of Eratosthenes, using a method that eliminates multiples of the sifting base with addition rather than division:

(define primes (let ()
  (define-stream (next base mult strm)
    (let ((first (stream-car strm))
          (rest (stream-cdr strm)))
      (cond ((< first mult)
              (stream-cons first
                (next base mult rest)))
            ((< mult first)
              (next base (+ base mult) strm))
            (else (next base
                    (+ base mult) rest)))))
  (define-stream (sift base strm)
    (next base (+ base base) strm))
  (define-stream (sieve strm)
    (let ((first (stream-car strm))>
          (rest (stream-cdr strm)))
      (stream-cons first
        (sieve (sift first rest)))))
  (sieve (stream-from 2))))

A final example of infinite streams is a functional pearl from Jeremy Gibbons, David Lester and Richard Bird that enumerates the positive rational numbers without duplicates:

(define rats
  (stream-iterate
    (lambda (x)
      (let* ((n (floor x)) (y (- x n)))
        (/ (- n -1 y))))
    1))