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:

Original	JavaScript
(define (integers-starting-from n) (cons-stream n (integers-starting-from (+ n 1))))	function integers_starting_from(n) { return pair(n, () => integers_starting_from(n + 1)); }

Original	JavaScript
(define integers (integers-starting-from 1))	const integers = integers_starting_from(1);

This makes sense because integers will be a pair whose car head is 1 and whose cdr tail 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:

Original	JavaScript
(define (divisible? x y) (= (remainder x y) 0))	function is_divisible(x, y) { return x % y === 0; }

Original	JavaScript
(define no-sevens (stream-filter (lambda (x) (not (divisible? x 7))) integers))	const no_sevens = stream_filter(x => ! is_divisible(x, 7), integers);

Then we can find integers not divisible by 7 simply by accessing elements of this stream:

Original	JavaScript
(stream-ref no-sevens 100) 117	stream_ref(no_sevens, 100); 117

In analogy with integers, we can define the infinite stream of Fibonacci numbers:

Original	JavaScript
(define (fibgen a b) (cons-stream a (fibgen b (+ a b)))) (define fibs (fibgen 0 1))	function fibgen(a, b) { return pair(a, () => fibgen(b, a + b)); } const fibs = fibgen(0, 1);

Fibs The constant fibs is a pair whose car head is 0 and whose cdr tail is a promise to evaluate (fibgen 1 1). fibgen(1, 1). When we evaluate this delayed (fibgen 1 1), fibgen(1, 1), it will produce a pair whose car head is 1 and whose cdr tail is a promise to evaluate (fibgen 1 2), fibgen(1, 2), and so on.

For a look at a more exciting infinite stream, we can generalize the no-sevens no_sevens example to construct the infinite stream of prime numbers, using a method known as the sieve of Eratosthenes.[1] 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:

Original	JavaScript
(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)))	function sieve(stream) { return pair(head(stream), () => sieve(stream_filter( x => ! is_divisible(x, head(stream)), stream_tail(stream)))); } const primes = sieve(integers_starting_from(2));

Now to find a particular prime we need only ask for it:

Original	JavaScript
(stream-ref primes 50) 233	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 3.55figure 3.56.[2] The input stream feeds into an unconser unpairer 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. adjoined to 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.

Original		JavaScript
Figure 3.55 The prime sieve viewed as a signal-processing system. Each solid line represents a stream of values being transmitted. The dashed line from the car to the cons and the filter indicates that this is a single value rather than a stream.		Figure 3.56 The prime sieve viewed as a signal-processing system. Each solid line represents a stream of values being transmitted. The dashed line from the head to the pair and the filter indicates that this is a single value rather than a stream.

Defining streams implicitly

The integers and fibs streams above were defined by specifying generating procedures functions 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 statement defines the stream ones to be an infinite stream of ones:

Original	JavaScript
(define ones (cons-stream 1 ones))	const ones = pair(1, () => ones);

This works much like the declaration of a recursive procedure: function: ones is a pair whose car head is 1 and whose cdr tail is a promise to evaluate ones. Evaluating the cdr tail 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, add_streams, which produces the elementwise sum of two given streams:[3]

Original	JavaScript
(define (add-streams s1 s2) (stream-map + s1 s2))	function add_streams(s1, s2) { return stream_map_2((x1, x2) => x1 + x2, s1, s2); }

Now we can define the integers as follows:

Original	JavaScript
(define integers (cons-stream 1 (add-streams ones integers)))	const integers = pair(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:

Original	JavaScript
(define fibs (cons-stream 0 (cons-stream 1 (add-streams (stream-cdr fibs) fibs))))	const fibs = pair(0, () => pair(1, () => add_streams(stream_tail(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:

Original		JavaScript
		\[ \begin{array}{ccccccccccccl} & & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & \ldots & = & \texttt{stream}\mathtt{\_}\texttt{tail(fibs)} \\ & & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & \ldots & = & \texttt{fibs} \\ \hline 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & \ldots & = & \texttt{fibs} \end{array} \]

Scale-stream is another useful procedure The function scale_stream is also useful in formulating such stream definitions. This multiplies each item in a stream by a given constant:

Original	JavaScript
(define (scale-stream stream factor) (stream-map (lambda (x) (* x factor)) stream))	function scale_stream(stream, factor) { return stream_map(x => x * factor, stream); }

For example,

Original	JavaScript
(define double (cons-stream 1 (scale-stream double 2)))	const double = pair(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:

Original	JavaScript
(define primes (cons-stream 2 (stream-filter prime? (integers-starting-from 3))))	const primes = pair(2, () => stream_filter(is_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 $\sqrt{n}$:

Original	JavaScript
(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))	function is_prime(n) { function iter(ps) { return square(head(ps)) > n ? true : is_divisible(n, head(ps)) ? false : iter(stream_tail(ps)); } return iter(primes); }

This is a recursive definition, since primes is defined in terms of the prime? is_prime predicate, which itself uses the primes stream. The reason this procedure function 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 $\sqrt{n}$).[4]

Exercise 3.56 Without running the program, describe the elements of the stream defined by

Original	JavaScript
(define s (cons-stream 1 (add-streams s s)))	const s = pair(1, () => add_streams(s, s));

Solution

This program defines s to be a stream whose first element is 1 and each next element is the double of the stream's previous element. The elements of s are therefore 1, 2, 4, 8, 16,... .

Exercise 3.57 Define a procedure function mul-streams, mul_streams, analogous to add-streams, 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 $n$th element (counting from 0) is $n+1$ factorial:

Original	JavaScript
(define factorials (cons-stream 1 (mul-streams ?? ??)))	const factorials = pair(1, () => mul_streams($\langle{}$??$\rangle$, $\langle{}$??$\rangle$));

Solution

const factorials = pair(1, () => mul_streams(factorials, integers));

Exercise 3.58 Define a procedure function partial-sums partial_sums that takes as argument a stream $S$ and returns the stream whose elements are $S_0, S_0+S_1, S_0+S_1+S_2,$ …. For example, (partial-sums integers) partial_sums(integers) should be the stream $1, 3, 6, 10, 15,\ldots$.

Solution

Original	JavaScript
(define (partial-sum s) (cons-stream (stream-car s) (add-streams (stream-cdr s) (partial-sum s))))	function partial_sums(s) { return pair(head(s), () => add_streams(stream_tail(s), partial_sums(s))); }

Exercise 3.59 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) scale_stream(S, 2) are also elements of S.
• The same is true for (scale-stream S 3) scale_stream(S, 3) and (scale-stream S 5). scale_stream(S, 5).
• 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 function merge that combines two ordered streams into one ordered result stream, eliminating repetitions:

Original	JavaScript
(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)))))))))	function merge(s1, s2) { if (is_null(s1)) { return s2; } else if (is_null(s2)) { return s1; } else { const s1head = head(s1); const s2head = head(s2); return s1head < s2head ? pair(s1head, () => merge(stream_tail(s1), s2)) : s1head > s2head ? pair(s2head, () => merge(s1, stream_tail(s2))) : pair(s1head, () => merge(stream_tail(s1), stream_tail(s2))); } }

Then the required stream may be constructed with merge, as follows:

Original	JavaScript
(define S (cons-stream 1 (merge ?? ??)))	const S = pair(1, () => merge($\langle{}$??$\rangle$, $\langle{}$??$\rangle$));

Fill in the missing expressions in the places marked $\langle{}$??$\rangle$ above.

Solution

const S = pair(1, () => merge(scale_stream(S, 2), merge(scale_stream(S, 3), scale_stream(S, 5))));

Exercise 3.60 How many additions are performed when we compute the $n$th 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 3.5.1.[5] How many additions are performed when we compute the $n$th Fibonacci number using the declaration of fibs based on the add_streams function? Show that this number is exponentially greater than the number of additions performed if add_streams had used the function stream_map_2_optimized described in exercise 3.53.[6]

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 3.61 Give an interpretation of the stream computed by the following procedure: function

Original	JavaScript
(define (expand num den radix) (cons-stream (quotient (* num radix) den) (expand (remainder (* num radix) den) den radix)))	function expand(num, den, radix) { return pair(math_trunc((num * radix) / den), () => expand((num * radix) % den, den, radix)); }

(Quotient is a primitive that returns the integer quotient of two integers.) where math_trunc discards the fractional part of its argument, here the remainder of the division. What are the successive elements produced by (expand 1 7 10)? expand(1, 7, 10)? What is produced by (expand 3 8 10)? expand(3, 8, 10)?

Solution

This function will produce a infinite stream of numbers which represent the digits of num / den in base-radix system. expand(1, 7, 10) will produce a infinite stream of numbers: 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7... While expand(3, 8, 10) will produce a stream of numbers: 3, 7, 5, 0, 0, 0, 0 ...

Exercise 3.62 In section 2.5.3 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{array}{rll} e^{x} &=& 1+x+\dfrac{x^{2}}{2}+\dfrac{x^{3}}{3\cdot2} +\dfrac{x^{4}}{4\cdot 3\cdot 2}+\cdots, \\[9pt] \cos x &=& 1-\dfrac{x^{2}}{2}+\dfrac{x^{4}}{4\cdot 3\cdot 2}-\cdots, \\[9pt] \sin x &=& x-\dfrac{x^{3}}{3\cdot 2} +\dfrac{x^{5}}{5\cdot 4\cdot 3\cdot 2}- \cdots, \end{array} \] 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_0, a_1, a_2, a_3,$ ….

1. The integral of the series $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$ is the series \[ \begin{array}{l} 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{array} \] where $c$ is any constant. Define a procedure function integrate-series integrate_series that takes as input a stream $a_0, a_1, a_2,\ldots$ representing a power series and returns the stream $a_0, \frac{1}{2}a_1, \frac{1}{3}a_2,\ldots$ of coefficients of the nonconstant 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, integrate_series, we will cons on the appropriate constant.) use pair to adjoin the appropriate constant to the beginning of the stream.)
2. 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^0 = 1$. Accordingly, we can generate the series for $e^x$ as

   Original	JavaScript
   (define exp-series (cons-stream 1 (integrate-series exp-series)))	const exp_series = pair(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:

   Original	JavaScript
   (define cosine-series (cons-stream 1 ??)) (define sine-series (cons-stream 0 ??))	const cosine_series = pair(1, $\langle{}$??$\rangle$); const sine_series = pair(0, $\langle{}$??$\rangle$);

Solution

function integrate_series(s) { function helper(ss, iter) { return pair(head(ss) / iter, () => helper(stream_tail(ss), iter + 1)); } return helper(s, 1); } const cos_series = pair(1, () => integrate_series( pair(0, () => stream_map( (x) => (-x), integrate_series(cos_series))))); const sin_series = pair(0, () => integrate_series( pair(1, () => integrate_series( stream_map(x => -x, sin_series) )) ));

Exercise 3.63 With power series represented as streams of coefficients as in exercise 3.62, adding series is implemented by add-streams. add_streams. Complete the declaration of the following procedure function for multiplying series:

Original	JavaScript
(define (mul-series s1 s2) (cons-stream ?? (add-streams ?? ??)))	function mul_series(s1, s2) { pair($\langle{}$??$\rangle$, () => add_streams($\langle{}$??$\rangle$, $\langle{}$??$\rangle$)); }

You can test your procedure function by verifying that $sin^2 x + cos^2 x = 1$, using the series from exercise 3.62.

Solution

function mul_series(s1, s2) { return pair(head(s1) * head(s2), () => add_streams( mul_series(stream_tail(s1), s2), scale_stream(stream_tail(s2), head(s1)))); }

Exercise 3.64 Let $S$ be a power series (exercise 3.62) 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{array}{rll} S \cdot X &=& 1 \\ (1+S_R)\cdot X &=& 1 \\ X + S_R \cdot X &=& 1 \\ X &=& 1 - S_R \cdot X \end{array} \] 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 function invert-unit-series invert_unit_series that computes $1/S$ for a power series $S$ with constant term 1. You will need to use mul-series mul_series from exercise 3.63.

Solution

function invert_unit_series(s) { return pair(1, () => stream_map(x => -x, mul_series(stream_tail(s), invert_unit_series(s)))); }

Exercise 3.65 Use the results of exercises 3.63 and 3.64 to define a procedure function div-series div_series that divides two power series. Div-series The function 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 div_series should signal an error.) Show how to use div-series div_series together with the result of exercise 3.62 to generate the power series for tangent.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.