SICP Section 3.5 Streams

Exercise 3.50. Complete the following definition, which generalizes stream-map to allow procedures that take multiple arguments, analogous to map in section 2.2.3, footnote 12.
(define (stream-map proc . argstreams) (if (<??> (car argstreams)) the-empty-stream (<??> (apply proc (map <??> argstreams)) (apply stream-map (cons proc (map <??> argstreams))))))
Answer:
(define (stream-map proc . argstreams) (if (stream-null? (car argstreams)) the-empty-stream (cons-stream (apply proc (map stream-car argstreams)) (apply stream-map (cons proc (map stream-cdr argstreams))))))
Exercise 3.51. In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it:
(define (show x) (display-line x) x)
What does the interpreter print in response to evaluating each expression in the following sequence?
(define x (stream-map show (stream-enumerate-interval 0 10))) (stream-ref x 5) (stream-ref x 7)
Answer:
(define x (stream-map show (stream-enumerate-interval 0 10))) ;; prints 0 (stream-ref x 5) ;; Prints 1, 2, 3, 4 and 5 separated by newlines. (stream-ref x 7) ;; Prints 6, 7
(stream-ref x 7) does not print 1 through 5 as show is not invoked thanks to memo-proc. Instead the stored results from previous invocations is reused.

Exercise 3.52. Consider the sequence of expressions
(define sum 0) (define (accum x) (set! sum (+ x sum)) sum) (define seq (stream-map accum (stream-enumerate-interval 1 20))) (define y (stream-filter even? seq)) (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) (stream-ref y 7) (display-stream z)
What is the value of sum after each of the above expressions is evaluated? What is the printed response to evaluating the stream-ref and display-stream expressions? Would these responses differ if we had implemented (delay <exp>) simply as (lambda () <exp>) without using the optimization provided by memo-proc ? Explain.

Answer:
(define seq (stream-map accum (stream-enumerate-interval 1 20))) ;; Sum becomes 1 (define y (stream-filter even? seq)) ;; Sum becomes 6 (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ;; Sum becomes 10 (stream-ref y 7) ;; Prints 136 ;; Sum becomes 136 (display-stream z) ;; Prints 10, 15, 45, 55, 105, 120, 190, 210 ;; Sum becomes 210
Without memo-proc:
;; (define y (stream-filter even? seq)) Sum becomes 6 (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) ;; Sum becomes 15 (6 +2 +3 +4) (stream-ref y 7) ;; Prints 162 ;; Sum becomes 162 (15 +4 +5 +6 +... +17) (display-stream z) ;; Prints 15, 180, 230, 305 ;; Sum becomes 362
Exercise 3.53. Without running the program, describe the elements of the stream defined by
(define s (cons-stream 1 (add-streams s s)))
Answer: This is the stream 1, 2, 4, 8, 16, 32, 64 etc. It represents the powers of 2: 2⁰, 2¹, 2², 2³, 2⁴ etc.

The very first value is 1, the hard-coded start value for s. Subsequent elements are created by invoking add-streams. Add-streams creates a new stream whose car is the result of adding the car of its argument streams. The very first time around this yields 1 + 1 = 2. As the stream is defined self-referentially, the car of s becomes 2 following the first call to add-streams. subsequent calls to add-streams causes addition of 2 and 2, yielding 4; 4 and 4 yielding 8 and so on.

Exercise 3.54. 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 <??> <??>)))
Answer:
(define (mul-streams s1 s2) (stream-map * s1 s2)) (define factorials (cons-stream 1 (mul-streams factorials (integers-starting-from 2))))
Exercise 3.55. Define a procedure partial-sums that takes as argument a stream S and returns the stream whose elements are S0, S0 + S1, S0 + S1 + S2, .... For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15, ....

Answer: This is an interesting exercise. As with many other exercises related to Streams it becomes easier if the solution is initially worked out on paper. In this case, the key to the solution is realizing that partial sum at any point is the sum of the partial sum up to that point and the element at the point. This yields the following self-referential definition:
(define (partial-sums stream) (cons-stream (stream-car stream) (add-streams (partial-sums stream) (stream-cdr stream))))
Exercise 3.56. 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.

Answer:
(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))))))))) (define S (cons-stream 1 (merge (merge (scale-stream S 2) (scale-stream S 3)) (scale-stream S 5))))
Exercise 3.57. 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 ) simply as (lambda () ), without using the optimization provided by the memo-proc procedure described in section 3.5.1.64

Answer: First, let us define the Fibonacci series as a stream.
(define fibs (cons-stream 0 (cons-stream 1 (add-streams (stream-cdr fibs) fibs))))
Tracing the flow on paper reveals that n-2 additions are required to calculate the nth Fibonacci number (counting n from 1).

Without memo-proc, each call to (stream-cdr fibs) would calculate the series from the beginning up to that point. This would exponentially increase the number of additions performed.

Exercise 3.58. 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) ?

Answer: This procedure produces the series of digits after the decimal point from the result of long division of the numerator (num) by the denominator (den) using the given radix base.

(expand 1 7 10) produces a series whose first six elements are 1, 4, 2, 8, 5 and 7. The rest of the elements is a repetition of these six. (1/7 = 0.1428571428...)

(expand 3 8 10) produces a series whose first three elements are 3, 7 and 5. The rest of the elements are all 0. (3/8 = 0.3750000...)

Exercise 3.59. 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







represented as infinite streams. We will represent the series a0 + a1 x + a2 x² + a3 x³ + ··· as the stream whose elements are the coefficients a0, a1, a2, a3, ....

a. The integral of the series a0 + a1 x + a2 x² + a3 x³ + ··· is the series



where c is any constant. Define a procedure integrate-series that takes as input a stream a0, a1, a2, ... representing a power series and returns the stream a0, (1/2)a1, (1/3)a2, ... 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 |--> e^x is its own derivative. This implies that ex and the integral of ex are the same series, except for the constant term, which is e0 = 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 <??>))
Answer:
;; a. (define (integrate-series s) (stream-map / s integers)) ;; b. (define exp-series (cons-stream 1 (integrate-series exp-series))) (define cosine-series (cons-stream 1 (integrate-series (scale-stream sine-series -1)))) (define sine-series (cons-stream 0 (integrate-series cosine-series)))
Exercise 3.60. With power series represented as streams of coefficients as in exercise 3.59, 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 sin2 x + cos2 x = 1, using the series from exercise 3.59.

Answer:
(define (mul-series s1 s2) (cons-stream (* (stream-car s1) (stream-car s2)) (add-streams (scale-stream (stream-cdr s2) (stream-car s1)) (mul-series (stream-cdr s1) s2)))) (define S (add-streams (mul-series sine-series sine-series) (mul-series cosine-series cosine-series))) (map (lambda (x) (stream-ref S x)) (enumerate-interval 0 10)) (1 0 0 0 0 0 0 0 0 0 0)
Exercise 3.61. Let S be a power series (exercise 3.59) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that S · X = 1. Write S = 1 + SR where SR is the part of S after the constant term. Then we can solve for X as follows:



In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of SR 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 3.60.

Answer:
(define (invert-unit-series s) (cons-stream 1 (mul-series (scale-stream (stream-cdr s) -1) (invert-unit-series s))))
Exercise 3.62. Use the results of exercises 3.60 and 3.61 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 3.59 to generate the power series for tangent.

Answer:
(define (div-series s1 s2) (let ((constant2 (stream-car s2))) (if (= constant2 0) (error "Constant term of denominator is 0 -- DIV-SERIES" s2) (scale-stream (mul-series s1 (invert-unit-series (scale-stream s2 (/ 1 constant2)))) (/ 1 constant2))))) (define tangent-series (div-series sine-series cosine-series))
Exercise 3.63. Louis Reasoner asks why the sqrt-stream procedure was not written in the following more straightforward way, without the local variable guesses:
(define (sqrt-stream x) (cons-stream 1.0 (stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-stream x))))
Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa's answer. Would the two versions still differ in efficiency if our implementation of delay used only (lambda () <exp>) without using the optimization provided by memo-proc (section 3.5.1)?

Answer: In Louis' version all stream-cdr calls to a given square root stream executes the procedure sqrt-stream. This in turn creates a new stream object each time. Calls to sqrt-stream and subsequent creation of new stream objects are avoided by using the local variable.

The two versions would still differ in efficiency as the difference is not dependent on the use of memo-proc.

Exercise 3.64. Write a procedure stream-limit that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements that differ in absolute value by less than the tolerance, and return the second of the two elements. Using this, we could compute square roots up to a given tolerance by
(define (sqrt x tolerance) (stream-limit (sqrt-stream x) tolerance))
Answer:
(define (stream-limit stream tolerance) (define (iter stream v1) (let ((v2 (stream-car stream))) (if (<= (abs (- v2 v1)) tolerance) v2 (iter (stream-cdr stream) v2)))) (iter (stream-cdr stream) (stream-car stream)))
Exercise 3.65. Use the series



to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for . How rapidly do these sequences converge?

Answer: We'll start by defining the summands of the log2 stream.
(define (log2-summands n) (cons-stream (/ 1.0 n) (stream-map - (log2-summands (+ n 1)))))
1. Straightforward summation using partial-sums. The value of log2 oscillates between 0.6687714031754279 and 0.7163904507944756 after 20 iterations.
(define log2-stream (partial-sums (log2-summands 1)))
2. Log2 using Euler Transformation. Value converges to 0.6932106782106783 after 10 iterations.
(define log2-stream-euler (euler-transform log2-stream))
3. Accelerated summation. Value converges to 0.6931488693329254 in 4 iterations.
(define log2-stream-accelerated (accelerated-sequence euler-transform log2-stream))
Exercise 3.66. Examine the stream (pairs integers integers). Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.)

Answer: (1, 100) will be preceded by 197 pairs. (1, n) will be preceded by 2n-3 pairs.

(99, 100) will be preceded by 1 + 3(2^98 - 1) pairs. (n, n+1) preceded by 1 + 3(2^(n - 1) - 1) pairs.

(100, 100) will be preceded by 6 + (2^96 - 1) pairs. (n, n) will be preceded by 6 + (2^(n - 4) - 1) pairs.

Exercise 3.67. Modify the pairs procedure so that (pairs integers integers) will produce the stream of all pairs of integers (i,j) (without the condition i <= j). Hint: You will need to mix in an additional stream.

Answer:
(define (pairs-all s t) (cons-stream (list (stream-car s) (stream-car t)) (interleave (interleave (stream-map (lambda (x) (list (stream-car s) x)) (stream-cdr t)) (stream-map (lambda (x) (list x (stream-car t))) (stream-cdr s))) (pairs (stream-cdr s) (stream-cdr t)))))
Exercise 3.68. Louis Reasoner thinks that building a stream of pairs from three parts is unnecessarily complicated. Instead of separating the pair (S0,T0) from the rest of the pairs in the first row, he proposes to work with the whole first row, as follows:
(define (pairs s t) (interleave (stream-map (lambda (x) (list (stream-car s) x)) t) (pairs (stream-cdr s) (stream-cdr t))))
Does this work? Consider what happens if we evaluate (pairs integers integers) using Louis's definition of pairs.

Answer: When (pairs s t) is evaluated a call is made to stream-map and pairs (arguments for interleave). The call to pairs in turn spawns another call to pairs and so on, causing an infinite loop.

Exercise 3.69. Write a procedure triples that takes three infinite streams, S, T, and U, and produces the stream of triples (Si,Tj,Uk) such that i <= j <= k. Use triples to generate the stream of all Pythagorean triples of positive integers, i.e., the triples (i,j,k) such that i <= j and i² + j² = k².

Answer:
(define (triple s t u) (cons-stream (list (stream-car s) (stream-car t) (stream-car u)) (interleave (stream-map (lambda (x) (cons (stream-car s) x)) (stream-cdr (pairs t u))) (triple (stream-cdr s) (stream-cdr t) (stream-cdr u))))) (define py-triples (stream-filter (lambda (t) (= (+ (square (car t)) (square (cadr t))) (square (caddr t)))) (triple integers integers integers)))
Exercise 3.70. It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an ad hoc interleaving process. We can use a technique similar to the merge procedure of exercise 3.56, if we define a way to say that one pair of integers is ``less than'' another. One way to do this is to define a ``weighting function'' W(i,j) and stipulate that (i1,j1) is less than (i2,j2) if W(i1,j1) < W(i2,j2). Write a procedure merge-weighted that is like merge, except that merge-weighted takes an additional argument weight, which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream.69 Using this, generalize pairs to a procedure weighted-pairs that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs, ordered according to weight. Use your procedure to generate

a. the stream of all pairs of positive integers (i,j) with i <= j ordered according to the sum i + j

b. the stream of all pairs of positive integers (i,j) with i <= j, where neither i nor j is divisible by 2, 3, or 5, and the pairs are ordered according to the sum 2 i + 3 j + 5 i j.

Answer:
(define (merge-weighted s1 s2 weight) (cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else (let ((s1car (stream-car s1)) (s2car (stream-car s2))) (let ((w1 (weight (car s1car) (cadr s1car))) (w2 (weight (car s2car) (cadr s2car)))) (cond ((<= w1 w2) (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight))) (else (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))) (define (weighted-pairs s t weight) (cons-stream (list (stream-car s) (stream-car t)) (merge-weighted (stream-map (lambda (x) (list (stream-car s) x)) (stream-cdr t)) (weighted-pairs (stream-cdr s) (stream-cdr t) weight) weight))) ;; a (define S1 (weighted-pairs integers integers (lambda (i j) (+ i j)))) ;; b. (define S2 (stream-filter (lambda (pair) (let ((ij (* (car pair) (cadr pair)))) (and (not (= (remainder ij 2) 0)) (not (= (remainder ij 3) 0)) (not (= (remainder ij 5) 0))))) (weighted-pairs integers integers (lambda (i j) (+ (* 2 i) (* 3 j) (* 5 i j))))))
Exercise 3.71. Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called Ramanujan numbers, in honor of the mathematician Srinivasa Ramanujan.70 Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i,j) weighted according to the sum i³ + j³ (see exercise 3.70), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five?

Answer:
(define (cube-weight . pair) (+ (expt (car pair) 3) (expt (cadr pair) 3))) (define ramanujan-stream (weighted-pairs integers integers cube-weight)) (define (ramanujan-numbers stream) (define (iter s1 s2) (let ((w1 (apply cube-weight (stream-car s1))) (w2 (apply cube-weight (stream-car s2)))) (if (= w1 w2) (begin (newline) (display w1))) (iter s2 (stream-cdr s2)))) (iter stream (stream-cdr stream)))
Next five after 1729 are 4104, 13832, 20683, 32832, 39312.

Exercise 3.72. In a similar way to exercise 3.71 generate a stream of all numbers that can be written as the sum of two squares in three different ways (showing how they can be so written).

Answer:
(define (square-weight . pair) (+ (square (car pair)) (square (cadr pair)))) (define square-stream (weighted-pairs integers integers square-weight)) (define (display-sum-of-squares sum . pairs) (define (display-iter pair) (display (car pair)) (display "^2") (display " + ") (display (cadr pair)) (display "^2") (display ", ")) (newline) (display sum) (display " = ") (for-each display-iter pairs)) (define (sum-of-squares stream) (define (iter s1 s2 s3) (let ((w1 (apply square-weight (stream-car s1))) (w2 (apply square-weight (stream-car s2))) (w3 (apply square-weight (stream-car s3)))) (if (= w1 w2 w3) (display-sum-of-squares w1 (stream-car s1) (stream-car s2) (stream-car s3))) (iter s2 (stream-cdr s2) (stream-cdr (stream-cdr s2))))) (iter stream (stream-cdr stream) (stream-cdr (stream-cdr stream)))) (sum-of-squares square-stream) 325 = 1^2 + 18^2, 6^2 + 17^2, 10^2 + 15^2, 425 = 5^2 + 20^2, 8^2 + 19^2, 13^2 + 16^2, ...
Exercise 3.73. v = v₀ + (1/C)₀^ti dt + R i





Figure 3.33: An RC circuit and the associated signal-flow diagram.

We can model electrical circuits using streams to represent the values of currents or voltages at a sequence of times. For instance, suppose we have an RC circuit consisting of a resistor of resistance R and a capacitor of capacitance C in series. The voltage response v of the circuit to an injected current i is determined by the formula in figure 3.33, whose structure is shown by the accompanying signal-flow diagram.

Write a procedure RC that models this circuit. RC should take as inputs the values of R, C, and dt and should return a procedure that takes as inputs a stream representing the current i and an initial value for the capacitor voltage v0 and produces as output the stream of voltages v. For example, you should be able to use RC to model an RC circuit with R = 5 ohms, C = 1 farad, and a 0.5-second time step by evaluating (define RC1 (RC 5 1 0.5)). This defines RC1 as a procedure that takes a stream representing the time sequence of currents and an initial capacitor voltage and produces the output stream of voltages.

Answer:
(define (RC R C dt) (define (proc i v0) (add-streams (scale-stream (integral i v0 dt) (/ 1 C)) (scale-stream i R))) proc)
Exercise 3.74. Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the zero crossings of the input signal. That is, the resulting signal should be + 1 whenever the input signal changes from negative to positive, - 1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be

...1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4 ...... 0 0 0 0 0 -1 0 0 0 0 1 0 0 ...

In Alyssa's system, the signal from the sensor is represented as a stream sense-data and the stream zero-crossings is the corresponding stream of zero crossings. Alyssa first writes a procedure sign-change-detector that takes two values as arguments and compares the signs of the values to produce an appropriate 0, 1, or - 1. She then constructs her zero-crossing stream as follows:
(define (make-zero-crossings input-stream last-value) (cons-stream (sign-change-detector (stream-car input-stream) last-value) (make-zero-crossings (stream-cdr input-stream) (stream-car input-stream)))) (define zero-crossings (make-zero-crossings sense-data 0))
Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is approximately equivalent to the following one, which uses the generalized version of stream-map from exercise 3.50:
(define zero-crossings (stream-map sign-change-detector sense-data <expression>))
Complete the program by supplying the indicated <expression>.

Answer:
(define zero-crossings (stream-map sign-change-detector sense-data (stream-cdr sense-data)))
Exercise 3.75. Unfortunately, Alyssa's zero-crossing detector in exercise 3.74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows:
(define (make-zero-crossings input-stream last-value) (let ((avpt (/ (+ (stream-car input-stream) last-value) 2))) (cons-stream (sign-change-detector avpt last-value) (make-zero-crossings (stream-cdr input-stream) avpt))))
This does not correctly implement Alyssa's plan. Find the bug that Louis has installed and fix it without changing the structure of the program. (Hint: You will need to increase the number of arguments to make-zero-crossings.)

Answer: I couldn't come up with an answer. If you know the answer and can explain it, do let me know.

Exercise 3.76. Eva Lu Ator has a criticism of Louis's approach in exercise 3.75. The program he wrote is not modular, because it intermixes the operation of smoothing with the zero-crossing extraction. For example, the extractor should not have to be changed if Alyssa finds a better way to condition her input signal. Help Louis by writing a procedure smooth that takes a stream as input and produces a stream in which each element is the average of two successive input stream elements. Then use smooth as a component to implement the zero-crossing detector in a more modular style.

Answer:
(define (smooth stream) (stream-map (lambda (x y) (average x y)) (cons-stream 0 stream) stream)) (define (make-zero-crossings smoothened-stream last-avpt) (cons-stream (sign-change-detector (stream-car smoothened-stream) last-avpt) (make-zero-crossings (stream-cdr smoothened-stream) (stream-car smoothened-stream))))
Exercise 3.77. The integral procedure used above was analogous to the ``implicit'' definition of the infinite stream of integers in section 3.5.2. Alternatively, we can give a definition of integral that is more like integers-starting-from (also in section 3.5.2):
(define (integral integrand initial-value dt) (cons-stream initial-value (if (stream-null? integrand) the-empty-stream (integral (stream-cdr integrand) (+ (* dt (stream-car integrand)) initial-value) dt))))
When used in systems with loops, this procedure has the same problem as does our original version of integral. Modify the procedure so that it expects the integrand as a delayed argument and hence can be used in the solve procedure shown above.

Answer:
(define (integral delayed-integrand initial-value dt) (cons-stream initial-value (let ((integrand (force delayed-integrand))) (if (stream-null? integrand) the-empty-stream (integral (delay (stream-cdr integrand)) (+ (* dt (stream-car integrand)) initial-value) dt))))) (define (solve f y0 dt) (define y (integral (delay dy) y0 dt)) (define dy (stream-map f y)) y)
Exercise 3.78.



Figure 3.35: Signal-flow diagram for the solution to a second-order linear differential equation.

Consider the problem of designing a signal-processing system to study the homogeneous second-order linear differential equation



The output stream, modeling y, is generated by a network that contains a loop. This is because the value of d²y/dt² depends upon the values of y and dy/dt and both of these are determined by integrating d²y/dt². The diagram we would like to encode is shown in figure 3.35. Write a procedure solve-2nd that takes as arguments the constants a, b, and dt and the initial values y₀ and dy₀ for y and dy/dt and generates the stream of successive values of y.

Answer:
(define (solve-2nd a b dt y0 dy0) (define y (integral (delay dy) y0 dt)) (define dy (integral (delay ddy) dy0 dt)) (define ddy (add-streams (scale-stream dy a) (scale-stream y b))) y)
Exercise 3.79. Generalize the solve-2nd procedure of exercise 3.78 so that it can be used to solve general second-order differential equations d² y/dt² = f(dy/dt, y).

Answer:
(define (solve-2nd f y0 dy0 dt) (define y (integral (delay dy) y0 dt)) (define dy (integral (delay ddy) dy0 dt)) (define ddy (stream-map f dy y)) y)
Exercise 3.80. A series RLC circuit consists of a resistor, a capacitor, and an inductor connected in series, as shown in figure 3.36. If R, L, and C are the resistance, inductance, and capacitance, then the relations between voltage (v) and current (i) for the three components are described by the equations



and the circuit connections dictate the relations



Combining these equations shows that the state of the circuit (summarized by vC, the voltage across the capacitor, and iL, the current in the inductor) is described by the pair of differential equations



The signal-flow diagram representing this system of differential equations is shown in figure 3.37.



Figure 3.36: A series RLC circuit.



Figure 3.37: A signal-flow diagram for the solution to a series RLC circuit.

Write a procedure RLC that takes as arguments the parameters R, L, and C of the circuit and the time increment dt. In a manner similar to that of the RC procedure of exercise 3.73, RLC should produce a procedure that takes the initial values of the state variables, vC0 and iL0, and produces a pair (using cons) of the streams of states vC and iL. Using RLC, generate the pair of streams that models the behavior of a series RLC circuit with R = 1 ohm, C = 0.2 farad, L = 1 henry, dt = 0.1 second, and initial values iL0 = 0 amps and vC0 = 10 volts.

Answer:
(define (RLC R L C dt) (define (proc vC0 iL0) (define vC (integral (delay dvC) vC0 dt)) (define iL (integral (delay diL) iL0 dt)) (define dvC (scale-stream iL (- (/ 1 C)))) (define diL (add-streams (scale-stream iL (- (/ R L))) (scale-stream vC (/ 1 L)))) (cons vC iL)) proc) (define RLC1 ((RLC 1 1 0.2 0.1) 10 0))
Exercise 3.81. Exercise 3.6 discussed generalizing the random-number generator to allow one to reset the random-number sequence so as to produce repeatable sequences of ``random'' numbers. Produce a stream formulation of this same generator that operates on an input stream of requests to generate a new random number or to reset the sequence to a specified value and that produces the desired stream of random numbers. Don't use assignment in your solution.

Answer:
(define (rand m) (define (generate-random-stream initial-value) (define random-numbers (cons-stream initial-value (stream-map rand-update random-numbers))) random-numbers) (cond ((eq? m 'generate) (lambda () (generate-random-stream random-init))) ((eq? m 'reset) (lambda (new-value) (generate-random-stream new-value)))))
Exercise 3.82. Redo exercise 3.5 on Monte Carlo integration in terms of streams. The stream version of estimate-integral will not have an argument telling how many trials to perform. Instead, it will produce a stream of estimates based on successively more trials.

Answer:
(define (random-in-range low high) (let ((range (- high low))) (+ low (random range)))) (define (rect-area x1 x2 y1 y2) (abs (* (- x2 x1) (- y2 y1)))) (define (monte-carlo experiment-stream passed failed) (define (next passed failed) (cons-stream (/ passed (+ passed failed)) (monte-carlo (stream-cdr experiment-stream) passed failed))) (if (stream-car experiment-stream) (next (+ passed 1) failed) (next passed (+ failed 1)))) (define (estimate-integral P x1 x2 y1 y2) (define (experiment) (P (random-in-range x1 x2) (random-in-range y1 y2))) (define (make-experiment-stream) (cons-stream (experiment) (make-experiment-stream))) (define ratio-stream (monte-carlo (make-experiment-stream) 0 0)) (define area (rect-area x1 x2 y1 y2)) (stream-map (lambda (r) (* area r 1.0)) ratio-stream)) (define (in-unit-circle? x y) (<= (+ (square x) (square y)) 1)) (define pi (estimate-integral in-unit-circle? -1 1 -1 1))