Infinite Streams

SICP > Modularity, Objects, and State > Streams > Infinite Streams

We have seen how to support the illusion of manipulating streams as complete entities even though, in actuality, we compute only as much of the stream as we need to access. We can exploit this technique to represent sequences efficiently as streams, even if the sequences are very long. What is more striking, we can use streams to represent sequences that are infinitely long. For instance, consider the following definition of the stream of positive integers:
(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))


(define integers (integers-starting-from 1))
This makes sense because integers will be a pair whose car is 1 and whose cdr is a promise to produce the integers beginning with 2. This is an infinitely long stream, but in any given time we can examine only a finite portion of it. Thus, our programs will never know that the entire infinite stream is not there.
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))
Then we can find integers not divisible by 7 simply by accessing elements of this stream:
(stream-ref no-sevens 100)
117
In analogy with integers, we can define the infinite stream of Fibonacci numbers:
(define (fibgen a b)
  (cons-stream a (fibgen b (+ a b))))

(define fibs (fibgen 0 1))
Fibs is a pair whose car is 0 and whose cdr is a promise to evaluate (fibgen 1 1). When we evaluate this delayed (fibgen 1 1), it will produce a pair whose car is 1 and whose cdr is a promise to evaluate (fibgen 1 2), and so on.
For a look at a more exciting infinite stream, we can generalize the no-sevens example to construct the infinite stream of prime numbers, using a method known as the sieve of Eratosthenes. We start with the integers beginning with 2, which is the first prime. To get the rest of the primes, we start by filtering the multiples of 2 from the rest of the integers. This leaves a stream beginning with 3, which is the next prime. Now we filter the multiples of 3 from the rest of this stream. This leaves a stream beginning with 5, which is the next prime, and so on. In other words, we construct the primes by a sieving process, described as follows: To sieve a stream S, form a stream whose first element is the first element of S and the rest of which is obtained by filtering all multiples of the first element of S out of the rest of S and sieving the result. This process is readily described in terms of stream operations:
(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)))
Now to find a particular prime we need only ask for it:
(stream-ref primes 50)
233
It is interesting to contemplate the signal-processing system set up by sieve, shown in the ``Henderson diagram'' in figure . The input stream feeds into an ``unconser'' that separates the first element of the stream from the rest of the stream. The first element is used to construct a divisibility filter, through which the rest is passed, and the output of the filter is fed to another sieve box. Then the original first element is consed onto the output of the internal sieve to form the output stream. Thus, not only is the stream infinite, but the signal processor is also infinite, because the sieve contains a sieve within it.

$\begin{figure}\par\figcaption {The prime sieve viewed as a signal-processing system.}\end{figure}$

Defining streams implicitly
The integers and fibs streams above were defined by specifying ``generating'' procedures that explicitly compute the stream elements one by one. An alternative way to specify streams is to take advantage of delayed evaluation to define streams implicitly. For example, the following expression defines the stream ones to be an infinite stream of ones:
(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 do more interesting things by manipulating streams with operations such as add-streams, which produces the elementwise sum of two given streams:
(define (add-streams s1 s2)
  (stream-map + s1 s2))
Now we can define the integers as follows:
(define integers (cons-stream 1 (add-streams ones integers)))
This defines integers to be a stream whose first element is 1 and the rest of which 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.
We can define the Fibonacci numbers 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:

1 1 2 3 5 8 13 21 ... = (stream-cdr fibs)

0 1 1 2 3 5 8 13 ... = fibs

0 1 1 2 3 5 8 13 21 34 ... = fibs

Scale-stream is another useful procedure in formulating such stream definitions. This multiplies each item in a stream by a given constant:
(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))
For example,
(define double (cons-stream 1 (scale-stream double 2)))
produces the stream of powers of 2: 1, 2, 4, 8, 16, 32, ....
An alternate definition of the stream of primes can be given by starting with the integers and filtering them by testing for primality. We will need the first prime, 2, to get started:
(define primes
  (cons-stream
   2
   (stream-filter prime? (integers-starting-from 3))))
This definition is not so straightforward as it appears, because we will test whether a number n is prime by checking whether n is divisible by a prime (not by just any integer) less than or equal to :
(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) true)
          ((divisible? n (stream-car ps)) false)
          (else (iter (stream-cdr ps)))))
  (iter primes))
This is a recursive definition, 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 ).
Exercise. Without running the program, describe the elements of the stream defined by
(define s (cons-stream 1 (add-streams s s)))
Exercise. Define a procedure mul-streams, analogous to add-streams, that produces the elementwise product of its two input streams. Use this together with the stream of integers to complete the following definition of the stream whose nth element (counting from 0) is n+1 factorial:
(define factorials (cons-stream 1 (mul-streams ?? ??)))
Exercise. Define a procedure partial-sums that takes as argument a stream S and returns the stream whose elements are S₀, S₀+S₁, S₀+S₁+S₂, .... For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15, ....
Exercise. A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers S and notice the following facts about it.
S begins with 1.
The elements of (scale-stream S 2) are also elements of S.
The same is true for (scale-stream S 3) and (scale-stream 5 S).
These are all the elements of S.

Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions:
(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                 (else
                  (cons-stream s1car
                               (merge (stream-cdr s1)
                                      (stream-cdr s2)))))))))
Then the required stream may be constructed with merge, as follows:
(define S (cons-stream 1 (merge ?? ??)))
Fill in the missing expressions in the places marked ?? above.
Exercise. How many additions are performed when we compute the nth Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay exp) simply as (lambda () exp), without using the optimization provided by the memo-proc procedure described in section .
Exercise. Give an interpretation of the stream computed by the following procedure:
(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) den radix)))
(Quotient is a primitive that returns the integer quotient of two integers.) What are the successive elements produced by (expand 1 7 10)? What is produced by (expand 3 8 10)?
Exercise. In section we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with power series, such as

$\begin{displaymath}e^{x} = 1+x+\frac{x^{2}}{2}+\frac{x^{3}}{3\cdot2}+\frac{x^{4}}{4\cdot 3\cdot 2}+\cdots, \end{displaymath}$

$\begin{displaymath}\cos x =1-\frac{x^{2}}{2}+\frac{x^{4}}{4\cdot 3\cdot 2}-\cdots, \end{displaymath}$

$\begin{displaymath}\sin x =x-\frac{x^{3}}{3\cdot 2}+\frac{x^{5}}{5\cdot 4\cdot 3\cdot 2}- \cdots, \end{displaymath}$

represented as infinite streams. We will represent the series $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$ as the stream whose elements are the coefficients a₀, a₁, a₂, a₃, ....

a. The integral of the series $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$ is the series

$\begin{displaymath}c + a_0 x + \frac{1}{2}a_1 x^2 + \frac{1}{3}a_2 x^3 + \frac{1}{4}a_3 x^4 + \cdots \end{displaymath}$

where c is any constant. Define a procedure integrate-series that takes as input a stream a₀, a₁, a₂, ... representing a power series and returns the stream ... of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use integrate-series, we will cons on the appropriate constant.)

b. The function $x\mapsto e^x$ is its own derivative. This implies that e^x and the integral of e^x are the same series, except for the constant term, which is e⁰ =1. Accordingly, we can generate the series for e^x as
(define exp-series
  (cons-stream 1 (integrate-series exp-series)))
Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:
(define cosine-series
  (cons-stream 1 ??))

(define sine-series
  (cons-stream 0 ??))
Exercise. With power series represented as streams of coefficients as in exercise , adding series is implemented by add-streams. Complete the definition of the following procedure for multiplying series:
(define (mul-series s1 s2)
  (cons-stream ?? (add-streams ?? ??)))
You can test your procedure by verifying that sin² x + cos² x = 1, using the series from exercise .
Exercise. Let S be a power series (exercise ) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that $S\cdot X= 1$ . Write S=1+S_R where S_R is the part of S after the constant term. Then we can solve for X as follows:

$\begin{eqnarray*}S \cdot X &=& 1 \cr (1+S_R)\cdot X &=& 1 \cr X + S_R \cdot X &=& 1 \cr X &=& 1 - S_R \cdot X \end{eqnarray*}$

In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of S_R times X. Use this idea to write a procedure invert-unit-series that computes 1/S for a power series S with constant term 1. You will need to use mul-series from exercise .
Exercise. Use the results of exercises and to define a procedure div-series that divides two power series. Div-series should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then div-series should signal an error.) Show how to use div-series together with the result of exercise to generate the power series for tangent.

Previous: Streams Are Delayed Lists

Next: Exploiting the Stream Paradigm

webmaster@arsdigita.org

		1	1	2	3	5	8	13	21	... = `(stream-cdr fibs)`
		0	1	1	2	3	5	8	13	... = `fibs`
0	1	1	2	3	5	8	13	21	34	... = `fibs`