# 3.5 Streams
# 3.5.1 Streams Are Delayed Lists
(define (stream-ref s n)
(if (zero? n)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
(define (stream-map f s)
(if (stream-null? s)
the-empty-stream
(cons-stream (f (stream-car s))
(stream-map f (stream-cdr s)))))
(define (stream-for-each f s)
(unless (stream-null? s)
(f (stream-car s))
(stream-for-each f (stream-cdr s))))
(define (display-stream s) (stream-for-each display-line s))
(define (display-line x) (newline) (display x))cons-stream is defined in src/lang/sicp.ss.
(define the-empty-stream '())
(define stream-null? null?)
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))# 3.5.1.1 The stream implementation in action
(define (stream-enumerate-interval low high)
(if (> low high)
the-empty-stream
(cons-stream low (stream-enumerate-interval (+ low 1) high))))
(define (stream-filter pred s)
(cond ((stream-null? s) the-empty-stream)
((pred (stream-car s))
(cons-stream (stream-car s)
(stream-filter pred (stream-cdr s))))
(else (stream-filter pred (stream-cdr s)))))Abbreviations to save space below.
(define a stream-car)
(define d stream-cdr)
(define i stream-enumerate-interval)
(define f stream-filter)
(define p? prime?)
(a (d (f p? (i 10000 1000000))))
=> (a (d (f p? (cons 10000 (delay (i 10001 1000000))))))… 10001 through 10006 …
=> (a (d (f p? (cons 10007 (delay (i 10008 1000000))))))
=> (a (d (cons 10007 (delay (f p? (cons 10008 (delay (i 10009 1000000))))))))
=> (a (f p? (cons 10008 (delay (i 10009 1000000)))))
=> (a (f p? (cons 10009 (delay (i 10010 1000000)))))
=> (a (cons 10009 (delay (f p? (cons 10010 (delay (i 10011 1000000)))))))
=> 10009
# 3.5.1.2 Implementing delay and force
delay is a special form such that (delay EXPR) is syntactic sugar for (lambda () EXPR). force can be implemented as procedure, as done below. However, outside this section we use the Scheme implementation’s versions.
(define (force delayed-object) (delayed-object))
(define (memo-proc proc)
(let ((already-run? #f)
(result #f))
(lambda ()
(unless already-run?
(set! result (proc))
(set! already-run? #t))
result)))We would then define (delay EXPR) to be (memo-proc (lambda () EXPR)).
# Exercise 3.50
(define (stream-map f . ss)
(if (stream-null? (car ss))
the-empty-stream
(cons-stream (apply f (map stream-car ss))
(apply stream-map f (map stream-cdr ss)))))# Exercise 3.51
(define (show x) (display-line x) x)
(define x)
(set! x (stream-map show (stream-enumerate-interval 0 10)))
=$> ["0"]
(stream-ref x 5) =$> ["1" "2" "3" "4" "5"]
(stream-ref x 5) => 5
(stream-ref x 7) =$> ["6" "7"]
(stream-ref x 7) => 7# Exercise 3.52
(define sum 0)
(define (accum x) (set! sum (+ x sum)) sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
sum => 1
(define y (stream-filter even? seq))
sum => 6
(define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq))
sum => 10
(stream-ref y 7) => 136
sum => 136
(display-stream z) =$> ["10" "15" "45" "55" "105" "120" "190" "210"]Yes, responses would differ if delay did not use memoization. The stream seq would get its cdr evaluated multiple times, and it would be different each time because sum keeps increasing. Instead of 1, 6, 10, 120, it would be 1, 6, 15, 162. Displaying z would only show 15. The rest of seq gets generated using a much higher sum, none of which are divisible by 5.
# 3.5.2 Infinite Streams
(define (stream-take s n)
(cond ((zero? n) '())
(else (cons (stream-car s) (stream-take (stream-cdr s) (- n 1))))))
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ 1 n))))
(define integers (integers-starting-from 1))
(define (divisible? x y) (= (remainder x y) 0))
(define no-sevens
(stream-filter (lambda (x) (not (divisible? x 7))) integers))
(stream-ref no-sevens 100) => 117
(define (fibgen a b) (cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))
(stream-take fibs 10) => '(0 1 1 2 3 5 8 13 21 34)
(define (sieve s)
(cons-stream
(stream-car s)
(sieve (stream-filter
(lambda (x)
(not (divisible? x (stream-car s))))
(stream-cdr s)))))
(define primes (sieve (integers-starting-from 2)))
(stream-ref primes 50) => 233# 3.5.2.1 Defining streams implicitly
(define ones (cons-stream 1 ones))
(define (add-streams s1 s2) (stream-map + s1 s2))
(define integers
(cons-stream 1 (add-streams ones integers)))
(stream-take integers 10) => '(1 2 3 4 5 6 7 8 9 10)
(define fibs
(cons-stream 0 (cons-stream 1 (add-streams (stream-cdr fibs) fibs))))
(stream-take fibs 10) => '(0 1 1 2 3 5 8 13 21 34)
(define (scale-stream stream factor)
(stream-map (lambda (x) (* x factor)) stream))
(define (negate-stream stream) (scale-stream stream -1))
(define double
(cons-stream 1 (scale-stream double 2)))
(stream-take double 10) => '(1 2 4 8 16 32 64 128 256 512)
(define primes
(cons-stream 2 (stream-filter prime? (integers-starting-from 3))))
(define (prime? n)
(define (iter ps)
(or (> (square (stream-car ps)) n)
(and (not (divisible? n (stream-car ps)))
(iter (stream-cdr ps)))))
(iter primes))
(stream-ref primes 50) => 233# Exercise 3.53
(define s (cons-stream 1 (add-streams s s)))It produces all powers of two, just like double in Section 3.5.2.1. This can be seen from the fact that x * 2 (scaling a stream by 2) is the same as x + x (adding a stream to itself).
(stream-take s 10) => '(1 2 4 8 16 32 64 128 256 512)# Exercise 3.54
(define (mul-streams s1 s2) (stream-map * s1 s2))
(define factorials
(cons-stream 1 (mul-streams factorials (integers-starting-from 2))))
(stream-take factorials 5) => '(1 2 6 24 120)# Exercise 3.55
(define (partial-sums s)
(define self (cons-stream (stream-car s) (add-streams self (stream-cdr s))))
self)
(stream-take (partial-sums integers) 10) => '(1 3 6 10 15 21 28 36 45 55)# Exercise 3.56
(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else (let ((x1 (stream-car s1))
(x2 (stream-car s2)))
(cond ((< x1 x2) (cons-stream x1 (merge (stream-cdr s1) s2)))
((> x1 x2) (cons-stream x2 (merge s1 (stream-cdr s2))))
(else (cons-stream
x1
(merge (stream-cdr s1) (stream-cdr s2)))))))))
(define S
(cons-stream 1 (merge (scale-stream S 2)
(merge (scale-stream S 3)
(scale-stream S 5)))))
(stream-take S 10) => '(1 2 3 4 5 6 8 9 10 12)# Exercise 3.57
See proofs.pdf for the proof that the number of additions when computing the nth Fibonacci number using fibs from Section 3.5.2.1 would be exponentially greater if delay is implemented without memoization.
# Exercise 3.58
(define (expand num den radix)
(cons-stream
(quotient (* num radix) den)
(expand (remainder (* num radix) den) den radix)))This procedure produces the stream of digits in the base given by radix that represent the quotient of num and den. It does it without using floating-point operations.
(stream-take (expand 1 7 10) 10) => '(1 4 2 8 5 7 1 4 2 8)
(inexact (/ 1 7)) ~> 0.14285714285714285
(stream-take (expand 3 8 10) 10) => '(3 7 5 0 0 0 0 0 0 0)
(inexact (/ 3 8)) ~> 0.375# Exercise 3.59
Integration
(define (integrate-series power-series) (stream-map / power-series (integers-starting-from 1)))Exponential, sine, cosine
(define exp-series (cons-stream 1 (integrate-series exp-series))) (define cosine-series (cons-stream 1 (negate-stream (integrate-series sine-series)))) (define sine-series (cons-stream 0 (integrate-series cosine-series)))
Evaluating series
(define (eval-series s x n)
(let ((terms (stream-map (lambda (c k) (* c (expt x k)))
s
(integers-starting-from 0))))
(accumulate + 0.0 (stream-take terms n))))
(eval-series exp-series 1.0 15) ~> 2.7182818285# Exercise 3.60
(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))))Verifying that sin^2(x) + cos^2(x) = 1. We can rely on the result being exactly 1, not just approximately 1, because the identity is satisfied all the way in the partial sums, not just in the limit.
(eval-series (add-streams (mul-series sine-series sine-series)
(mul-series cosine-series cosine-series))
(random 100)
15)
=> 1.0# Exercise 3.61
(define (invert-unit-series s)
(cons-stream
1
(negate-stream (mul-series (stream-cdr s)
(invert-unit-series s)))))Note: invert-series requires a nonzero constant term.
(define (invert-series s)
(let ((constant (stream-car s)))
(cond ((= constant 0) (error 'invert-series "division by zero" s))
((= constant 1) (invert-unit-series s))
(else (scale-stream
(invert-unit-series (scale-stream s (/ constant)))
(/ constant))))))# Exercise 3.62
(define (div-series s1 s2)
(let ((den-constant (stream-car s2)))
(cond ((zero? den-constant) (error 'div-series "division by zero" s1 s2))
(else (mul-series s1 (invert-series s2))))))
(define tangent-series (div-series sine-series cosine-series))
(eval-series tangent-series (atan 0.123) 10) ~> 0.123# 3.5.3 Exploiting the Stream Paradigm
# 3.5.3.1 Formulating iterations as stream processes
(define (sqrt-stream x)
(define guesses
(cons-stream
1.0
(stream-map (lambda (guess) (improve guess x))
guesses)))
guesses)
(define (pi-summands n)
(cons-stream (/ 1.0 n) (stream-map - (pi-summands (+ n 2)))))
(define pi-stream
(scale-stream (partial-sums (pi-summands 1)) 4))
(define (euler-transform s)
(let ((s0 (stream-ref s 0))
(s1 (stream-ref s 1))
(s2 (stream-ref s 2)))
(cons-stream (- s2 (/ (square (- s2 s1))
(+ s0 (* -2 s1) s2)))
(euler-transform (stream-cdr s)))))
(define (make-tableau transform s)
(cons-stream s (make-tableau transform (transform s))))
(define (accelerated-sequence transform s)
(stream-map stream-car (make-tableau transform s)))
(stream-ref (sqrt-stream 2) 10)
~> 1.414213562373095
(stream-ref pi-stream 10)
~> 3.232315809405594
(stream-ref (euler-transform pi-stream) 10)
~> 3.1417360992606667
(stream-ref (accelerated-sequence euler-transform pi-stream) 8)
~> 3.141592653589793The 11th term is NaN, probably because a denominator becomes extremely tiny.
(stream-ref (accelerated-sequence euler-transform pi-stream) 10)
=> +nan.0# Exercise 3.63
(define (sqrt-stream x)
(cons-stream
1.0
(stream-map (lambda (guess) (improve guess x))
(sqrt-stream x))))This implementation is less efficient because it doesn’t take advantage of memoization. It improves the first guess to get the second item, but then it must do that all over again in the recursive call to improve the second gues when it calls (sqrt-stream x). If our implementation of delay didn’t use the optimization provided by memo-proc, then there would be no difference in efficiency between the original procedure and this one.
# Exercise 3.64
(define (stream-limit s tolerance)
(define (iter prev s)
(let ((next (stream-car s)))
(if (< (abs (- prev next)) tolerance)
next
(iter next (stream-cdr s)))))
(iter (stream-car s) (stream-cdr s)))
(define (sqrt x tolerance)
(stream-limit (sqrt-stream x) tolerance))
(sqrt 2 0.1) ~> 1.4166666666666665
(sqrt 2 0.0001) ~> 1.4142135623746899# Exercise 3.65
(define (ln-2-summands n)
(cons-stream (/ 1.0 n) (negate-stream (ln-2-summands (+ n 1)))))
(define ln-2-stream
(partial-sums (ln-2-summands 1)))This converges fairly slowly on its own:
(stream-ref ln-2-stream 10) ~> 0.7365440115440116The accelerated sequence converges much faster:
(define accel-ln-2-stream (accelerated-sequence euler-transform ln-2-stream))
(stream-ref accel-ln-2-stream 8) ~> (log 2)# 3.5.3.2 Infinite streams of pairs
(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(pairs (stream-cdr s) (stream-cdr t)))))
(define (interleave s1 s2)
(cond ((stream-null? s1) s2)
(else (cons-stream (stream-car s1)
(interleave s2 (stream-cdr s1))))))
(define integer-pairs (pairs integers integers))
(define first-10-pairs (stream-take integer-pairs 10))
first-10-pairs => '((1 1) (1 2) (2 2) (1 3) (2 3) (1 4) (3 3) (1 5) (2 4) (1 6))# Exercise 3.66
Let f(n) be the nth pair in the stream, starting at 0.
;;;;; [TODO: Rendering these lines as code trips schemehl assertion]
;;;;; f(0) = (1,1); f(n) = (1,_) when n = 1 + 2k
;;;;; f(2) = (2,2); f(n) = (2,_) when n = 4 + 4k
;;;;; f(6) = (3,3); f(n) = (3,_) when n = 10 + 8k
;;;;; f(14) = (4,4); f(n) = (4,_) when n = 22 + 16k
;;;;; ...The next row (where the first number in the pair is incremented once) always gets updated half as often as the previous row. In general,
;;;;; [TODO: Rendering these lines as code trips schemehl assertion]
;;;;; f(2^x - 2) = (x,x);
;;;;; f(2^x - 2 + 2^(x-1) + (k - 1)2^x) = (x,x+k), k > 0.We can write a function to find the index of a given pair:
(define (pair->index pair)
(let* ((x (car pair))
(k (- (cadr pair) x)))
(cond ((zero? k) (- (expt 2 x) 2))
(else (- (* (expt 2 (- x 1))
(+ (* 2 k) 1))
2)))))
(pair->index '(1 100)) => 197
(pair->index '(99 100)) => 950737950171172051122527404030
(pair->index '(100 100)) => (- (expt 2 100) 2)We can confirm that it’s correct for small indices:
(map pair->index first-10-pairs) => (enumerate-interval 0 9)
(stream-ref integer-pairs 197) => '(1 100)
(define random-pair-fst (+ 1 (random 5)))
(define random-pair (list random-pair-fst (+ random-pair-fst (random 46))))
(define random-index (pair->index random-pair))
(>= random-index 0) => #t ; sanity check
(<= random-index 1454) => #t ; ensure it's not too large
(stream-ref integer-pairs random-index) => random-pairGoing the other way, from index to pair, is possible without generating the stream. But there is no simple closed form solution. For an index n, the first element of the pair (from which we can easily solve for the second) is given by https://oeis.org/A091090.
(define (index->pair n)
;; Maintains the invariants a = 2^x, b = 3*2^(x-1).
(define (iter x a b)
(cond ((divisible? (- n (- b 2)) a)
(list x (+ x (/ (+ n 2 (* -3/2 a)) a) 1)))
(else (iter (+ x 1) (* a 2) (* b 2)))))
(let ((x (log (+ n 2) 2)))
(cond ((integer? x) (list (exact x) (exact x)))
(else (iter 1 2 3)))))
(map index->pair (enumerate-interval 0 9)) => first-10-pairs
(index->pair 197) => '(1 100)
(index->pair random-index) => random-pair# Exercise 3.67
(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(interleave
(stream-map (lambda (x) (list x (stream-car t)))
(stream-cdr s))
(pairs (stream-cdr s) (stream-cdr t))))))
(stream-take (pairs integers integers) 10)
=> '((1 1) (1 2) (2 1) (1 3) (2 2) (1 4) (3 1) (1 5) (2 3) (1 6))# Exercise 3.68
(define (pairs s t)
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
t)
(pairs (stream-cdr s) (stream-cdr t))))No, this will not work: there will be an infinite loop. The recursive call (pairs (stream-cdr s) (stream-cdr t)) is not delayed by a cons-stream, so the procedure will never return.
# Exercise 3.69
(define (triples 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)))
(triples (stream-cdr s)
(stream-cdr t)
(stream-cdr u)))))
(define pythagorean-triples
(stream-filter
(lambda (x)
(= (+ (square (car x)) (square (cadr x))) (square (caddr x))))
(triples integers integers integers)))
(stream-car pythagorean-triples) => '(3 4 5)# Exercise 3.70
(define (merge-weighted s1 s2 weight)
(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else (let ((x1 (stream-car s1))
(x2 (stream-car s2)))
(if (<= (weight x1) (weight x2))
(cons-stream x1 (merge (stream-cdr s1) s2))
(cons-stream x2 (merge s1 (stream-cdr s2))))))))
(merge s1 s2))
(define (weighted-pairs s t weight)
(cons-stream
(list (stream-car s) (stream-car s))
(merge-weighted
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(weighted-pairs (stream-cdr s) (stream-cdr t) weight)
weight)))Pairs of positive integers (i, j) with i <= j ordered by i + j.
(define (a-weight p) (apply + p)) (define a-stream (weighted-pairs integers integers a-weight)) (define a-10 (stream-take a-stream 10)) a-10 => '((1 1) (1 2) (1 3) (2 2) (1 4) (2 3) (1 5) (2 4) (3 3) (1 6)) (map a-weight a-10) => '(2 3 4 4 5 5 6 6 6 7)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 by 2i + 3j + 5ij.
(define (b-weight p) (+ (* 2 (car p)) (* 3 (cadr p)) (* 5 (car p) (cadr p)))) (define b-stream (let ((filtered (stream-filter (lambda (x) (not (or (divisible? x 2) (divisible? x 3) (divisible? x 5)))) integers))) (weighted-pairs filtered filtered b-weight))) (define b-10 (stream-take b-stream 10)) b-10 => '((1 1) (1 7) (1 11) (1 13) (1 17) (1 19) (1 23) (1 29) (1 31) (7 7)) (map b-weight b-10) => '(10 58 90 106 138 154 186 234 250 280)
# Exercise 3.71
(define (weight p) (+ (cube (car p)) (cube (cadr p))))
(define (analyze pairs)
(let* ((w1 (weight (stream-car pairs)))
(w2 (weight (stream-car (stream-cdr pairs)))))
(if (= w1 w2)
(cons-stream w1 (analyze (stream-cdr (stream-cdr pairs))))
(analyze (stream-cdr pairs)))))
(define ramanujan-numbers
(analyze (weighted-pairs integers integers weight)))
(stream-take ramanujan-numbers 6) => '(1729 4104 13832 20683 32832 39312)# Exercise 3.72
(define (weight p) (+ (square (car p)) (square (cadr p))))
(define (analyze pairs)
(let* ((x1 (stream-car pairs))
(x2 (stream-car (stream-cdr pairs)))
(x3 (stream-car (stream-cdr (stream-cdr pairs))))
(w1 (weight x1)))
(if (= w1 (weight x2) (weight x3))
(cons-stream (list w1 x1 x2 x3)
(analyze (stream-cdr (stream-cdr (stream-cdr pairs)))))
(analyze (stream-cdr pairs)))))
(define thrice-square-sums
(analyze (weighted-pairs integers integers weight)))
(stream-take thrice-square-sums 3)
=> '((325 (1 18) (6 17) (10 15))
(425 (5 20) (8 19) (13 16))
(650 (5 25) (11 23) (17 19)))# 3.5.3.3 Streams as signals
(define (integral integrand initial-value dt)
(define int
(cons-stream initial-value
(add-streams (scale-stream integrand dt)
int)))
int)# Exercise 3.73
(define (RC R C dt)
(lambda (i v0)
(add-streams (scale-stream i R)
(integral (scale-stream i (/ C)) v0 dt))))RC circuit with R = 5 ohms, C = 1 farad, and dt = 0.5 s.
(define RC1 (RC 5 1 0.5))Calculate the stream of voltages given a constant i = 1 amp and v0 = 0 V.
(stream-take (RC1 ones 0) 10)
=> '(5 5.5 6.0 6.5 7.0 7.5 8.0 8.5 9.0 9.5)# Exercise 3.74
(define (cycle original)
(define (iter xs)
(cond ((null? xs) (iter original))
(else (cons-stream (car xs) (iter (cdr xs))))))
(iter original))Alyssa’s original implementation
(define (sign-change-detector new old)
(cond ((and (< old 0) (>= new 0)) 1)
((and (>= old 0) (< new 0)) -1)
(else 0)))
(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 sense-data) (make-zero-crossings sense-data 0))
(define test-data (cycle '(1 2 -1 -2 0 -1 0 2 4 5)))
(define test-result '(0 0 -1 0 1 -1 1 0 0 0))
(stream-take (zero-crossings test-data) 10) => test-resultMy implementation based on Eva Lu Ator’s suggestion
(define (zero-crossings sense-data)
(stream-map sign-change-detector
sense-data
(cons-stream 0 sense-data)))
(stream-take (zero-crossings test-data) 10) => test-result# Exercise 3.75
(define (make-zero-crossings input-stream last-value last-avpt)
(let* ((value (stream-car input-stream))
(avpt (/ (+ value last-value) 2)))
(cons-stream
(sign-change-detector avpt last-avpt)
(make-zero-crossings (stream-cdr input-stream) value avpt))))
(define (zero-crossings sense-data) (make-zero-crossings sense-data 0 0))
(define test-result '(0 0 0 -1 0 0 0 1 0 0))
(stream-take (zero-crossings test-data) 10) => test-result# Exercise 3.76
(define (smooth s) (stream-map average s (cons-stream 0 s)))
(define (smooth-zero-crossings sense-data) (zero-crossings (smooth sense-data)))
(stream-take (smooth-zero-crossings test-data) 10) => test-result# 3.5.4 Streams and Delayed Evaluation
(define (integral delayed-integrand initial-value dt)
(define int
(cons-stream
initial-value
(let ((integrand (force delayed-integrand)))
(add-streams (scale-stream integrand dt) int))))
int)Solves y’ = f(y).
(define (solve f y0 dt)
(define y (integral (delay dy) y0 dt))
(define dy (stream-map f y))
y)When f(y) = y and y0 = 1, the solution is e.
(stream-ref (solve (lambda (y) y) 1 0.001) 1000) ~> 2.716923932235896# Exercise 3.77
(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)))))
(paste (:3.5.4 solve))
(stream-ref (solve (lambda (y) y) 1 0.001) 1000) ~> 2.716923932235896# Exercise 3.78
Solves y’’ - ay’ - by = 0.
(define (solve-2nd a b y0 dy0 dt)
(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
Solves y’’ = f(y’, y).
(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
(define (RLC R L C dt)
(lambda (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 vC (/ L))
(scale-stream iL (/ (- R) L))))
(cons vC iL)))
(define (three-decimals x)
(let-values (((a b) (div-and-mod (round (* (abs x) 1000)) 1000)))
(format "~a~a.~a~a~a"
(if (negative? x) "-" "")
(exact a)
(if (< b 10) 0 "")
(if (< b 100) 0 "")
(exact b))))RLC circuit with R = 1 ohm, C = 0.2 farad, L = 1 henry, and dt = 0.1 s.
(define RLC1 (RLC 1 1 0.2 0.1))Calculate the stream of vC (capacitor voltage) and iL (inductor current) given initial values iL0 = 0 amps and vC0 = 10 volts.
(define v-and-i (RLC1 10 0))
(map three-decimals (stream-take (car v-and-i) 9))
=> '("10.000" "10.000" "9.500" "8.550" "7.220" "5.596" "3.772" "1.852" "-0.065")
(map three-decimals (stream-take (cdr v-and-i) 9))
=> '("0.000" "1.000" "1.900" "2.660" "3.249" "3.646" "3.841" "3.834" "3.636")# 3.5.5 Modularity of Functional Programs and Modularity of Objects
(define (map-successive-pairs f s)
(cons-stream
(f (stream-car s) (stream-car (stream-cdr s)))
(map-successive-pairs f (stream-cdr (stream-cdr s)))))
(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 random-numbers
(cons-stream
;; Start at `(rand-update random-init)` rather than `random-init` to match
;; the behavior in Section 3.1.2. This ensures the same estimate of pi.
(rand-update random-init)
(stream-map rand-update random-numbers)))
(define cesaro-stream
(map-successive-pairs
(lambda (r1 r2) (= (gcd r1 r2) 1))
random-numbers))
(define pi
(stream-map
(lambda (p) (sqrt (/ 6 p)))
(monte-carlo cesaro-stream 0 0)))This is deterministic because the random-init seed is fixed.
(stream-ref pi 999) ~> 3.149183286488868# Exercise 3.81
(define (random-numbers request-stream)
(define (iter s prev)
(if (stream-null? s)
the-empty-stream
(let* ((request (stream-car s))
(operation (car request))
(value (cond ((eq? operation 'reset) (cadr request))
((eq? operation 'generate) (rand-update prev))
(else (error 'random-numbers
"unknown request"
request)))))
(cons-stream value (iter (stream-cdr s) value)))))
(iter request-stream random-init))
(define reqs (cycle '((generate) (reset 7) (generate) (generate) (reset 0))))
(stream-take (random-numbers reqs) 5) => '(262145 7 1835015 58720487 0)# Exercise 3.82
(define (estimate-integral pred x1 x2 y1 y2)
(let* ((dx (- x2 x1))
(dy (- y2 y1))
(experiment-stream
(map-successive-pairs
(lambda (r1 r2)
(pred (+ x1 (* dx (/ r1 random-max)))
(+ y1 (* dy (/ r2 random-max)))))
random-numbers)))
(stream-map (lambda (p) (* p dx dy))
(monte-carlo experiment-stream 0 0))))
(define pi
(let ((pred (lambda (x y)
(<= (+ (square x) (square y)) 1))))
(estimate-integral pred -1.0 1.0 -1.0 1.0)))
(stream-ref pi 999) ~> 3.092