adrianwong programmer · retired coal miner

SICP section 3.5 - streams

Loved this section. Lengthy, but well worth the time and effort. Here’s an excerpt which quite adequately summarises what I’ve learnt:

We can model a changing quantity, such as the local state of some object, using a stream that represents the time history of successive states. In essence, we represent time explicitly, using streams, so that we decouple time in our simulated world from the sequence of events that take place during evaluation.

:seedling:.

Selected exercises

Exercise 3.50

Recall the text in section 2.2.1, footnote 12:

Scheme standardly provides a map procedure that is more general than the one described here. This more general map takes a procedure of n arguments, together with n lists, and applies the procedure to all the first elements of the lists, all the second elements of the lists, and so on, returning a list of the results.

Generalising stream-map so it is analogous to Scheme’s map:

(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

(define x
  (stream-map show
              (stream-enumerate-interval 0 10)))
; 0

(stream-ref x 5)
; 1
; 2
; 3
; 4
; 5

(stream-ref x 7)
; 6
; 7

Exercise 3.52

(define sum 0)
; sum: 0

(define (accum x) (set! sum (+ x sum)) sum)
; sum: 0

(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)
; sum: 136
; stream-ref: 136

(display-stream z)
; sum: 210
; display-stream:
;   10
;   15
;   45
;   55
;   105
;   120
;   190
;   210

Yes, these responses will differ if we do not memoise. Without memoisation, values are recreated, re-mapped over with accum, then re-added to sum.

Exercise 3.53

(define s (cons-stream 1 (add-streams s s))) produces the stream \(2^n, n \geq 0\).

Exercise 3.54

(define (mul-streams s1 s2) (stream-map * s1 s2))

(define ones (cons-stream 1 ones))

(define integers
  (cons-stream 1 (add-streams ones integers)))

(define factorials
  (cons-stream 1 (mul-streams integers factorials)))

Tests:

(stream-ref factorials 0) ; 1
(stream-ref factorials 1) ; 1
(stream-ref factorials 2) ; 2
(stream-ref factorials 3) ; 6
(stream-ref factorials 4) ; 24
(stream-ref factorials 5) ; 120

;   1 2 3  4   5  ...  =  integers
;   1 1 2  6  24  ...  =  factorials
; 1 1 2 6 24 120  ...  =  factorials

Intuition:

Exercise 3.55

(define (partial-sums s)
  (cons-stream (stream-car s)
               (add-streams (stream-cdr s) (partial-sums s))))

Tests:

(stream-ref (partial-sums integers) 0) ; 1
(stream-ref (partial-sums integers) 1) ; 3
(stream-ref (partial-sums integers) 2) ; 6
(stream-ref (partial-sums integers) 3) ; 10
(stream-ref (partial-sums integers) 4) ; 15
(stream-ref (partial-sums integers) 5) ; 21

Exercise 3.56

The hard work has been done by the authors here; all that remains is to merge the three scaled streams:

(define S
  (cons-stream 1 (merge (scale-stream S 2)
                        (merge (scale-stream S 3)
                               (scale-stream S 5)))))

To aid our testing, we can define a helper method display-istream-range, which displays the elements in a given stream between \([x, y]\):

(define (istream-range proc s x y)
  (if (> x y)
      'done
      (begin (proc (stream-ref s x))
             (istream-range proc s (+ x 1) y))))

(define (display-inline x) (display x) (display " "))

(define (display-istream-range s x y)
  (istream-range display-inline s x y))

Test:

(display-istream-range S 0 20)
; 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 'done

Exercise 3.57

With memoisation:

Without memoisation:

For n > 0, each increment of n requires an additional fib(n - 1) additions, which makes the number of additions grow exponentially.

Exercise 3.58

(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) den radix)))

(display-istream-range (expand 1 7 10) 0 10)
; 1 4 2 8 5 7 1 4 2 8 5 'done

(display-istream-range (expand 3 8 10) 0 10)
; 3 7 5 0 0 0 0 0 0 0 0 'done

The numbers in expand are the floating-point representation of (/ num den) in base radix.

Exercise 3.59

Part (a): we can define a helper procedure div-streams, analogous to mul-streams from exercise 3.54:

(define (div-streams s1 s2) (stream-map / s1 s2))

(define (integrate-series s)
  (div-streams s integers))

Test on a stream of ones:

(display-istream-range (integrate-series ones) 0 10)
; 1 1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9 1/10 1/11 'done

Part (b): it’s cool that we can define sine-series and cosine-series in terms of each other so easily:

(define sine-series
  (cons-stream 0 (integrate-series cosine-series)))

(define cosine-series
  (cons-stream 1 (integrate-series (scale-stream sine-series -1))))

Tests, and a quick check of our results against Wolfram MathWorld’s series expansion page:

(display-istream-range sine-series 0 10)
; 0 1 0 -1/6 0 1/120 0 -1/5040 0 1/362880 0 'done

(display-istream-range cosine-series 0 10)
; 1 0 -1/2 0 1/24 0 -1/720 0 1/40320 0 -1/3628800 'done

Exercise 3.60

When observing for patterns in a sequence/series, I adopt a fairly “brute force” approach:

  1. Start off with a (very) small number of terms.
  2. Attempt to find a pattern.
  3. If I suspect a pattern exists, increment the number of terms and check if the pattern still holds true.
  4. If true, repeat #3 once or twice. Else, return to #2 :cry:.
$$\begin{align*} \bigg( \sum\limits_{i=0}^1 a_i \bigg) \bigg( \sum\limits_{i=0}^1 b_i \bigg) &= a_0b_0 + a_0b_1 + a_1b_0 + a_1b_1 \\ \bigg( \sum\limits_{i=0}^2 a_i \bigg) \bigg( \sum\limits_{i=0}^2 b_i \bigg) &= a_0b_0 + (a_0b_1 + a_0b_2) + a_1b_0 + (a_1b_1 + a_1b_2) + a_2b_0 + (a_2b_1 + a_2b_2) \\ \bigg( \sum\limits_{i=0}^n a_i \bigg) \bigg( \sum\limits_{i=0}^n b_i \bigg) &= a_0b_0 + (a_0b_1 + \ldots + a_0b_n) + a_1b_0 + (a_1b_1 + \ldots + a_1b_n) + a_2b_0 + \ldots \\ &= a_0b_0 + a_0(b_1 + \ldots + b_n) + a_1b_0 + a_1(b_1 + \ldots + b_n) + a_2b_0 + \ldots \end{align*}$$

Once we have the pattern, translating it into code is fairly trivial. Note: substituting a for s1 and b for s2 so the procedure is consistent with the math:

(define (mul-series a b)
  (cons-stream (* (stream-car a)
                  (stream-car b))
               (add-streams (scale-stream (stream-cdr b) (stream-car a))
                            (mul-series (stream-cdr a) b))))

Test:

(define mul-series-test
  (add-streams (mul-series sine-series sine-series)
               (mul-series cosine-series cosine-series)))

(display-istream-range mul-series-test 0 10)
; 1 0 0 0 0 0 0 0 0 0 0 'done

Exercise 3.61

(define (invert-unit-series s)
  (cons-stream 1 (scale-stream (mul-series (stream-cdr s)
                                           (invert-unit-series s))
                               -1)))

Exercise 3.62

Now that we’ve implemented mul-series and invert-unit-series, defining div-series is trivial:

(define (div-series s1 s2)
  (if (= (stream-car s2) 0)
      (error "Denominator constant term cannot be 0: DIV-SERIES")
      (mul-series (invert-unit-series s2)
                  s1)))

High school math \(\Big(tan \,\theta = \frac{sin \,\theta}{cos \,\theta}\Big)\) to the rescue:

(define tan-series
  (div-series sine-series cosine-series))

Test, and (again) a quick check of our results against Wolfram MathWorld’s series expansion page:

(display-istream-range tan-series 0 10)
; 0 1 0 1/3 0 2/15 0 17/315 0 62/2835 0 'done

Exercise 3.63

Compare the original:

(define (sqrt-stream x)
  (define guesses
    (cons-stream
     1.0
     (stream-map (lambda (guess) (sqrt-improve guess x))
                 guesses)))
  guesses)

…against Louis’ “more straightforward” version:

(define (sqrt-stream x)
  (cons-stream
   1.0
   (stream-map (lambda (guess) (sqrt-improve guess x))
               (sqrt-stream x))))

With Louis’ version, each recursive call to (sqrt-stream x) produces a new, un-memoised stream, resulting in redundant computation.

Without the memoisation optimisation provided by memo-proc, the two versions will have the same efficiency.

Exercise 3.64

(define (stream-limit s tolerance)
  (let ((current (stream-ref s 0))
        (next (stream-ref s 1)))
    (if (< (abs (- current next))
           tolerance)
        next
        (stream-limit (stream-cdr s) tolerance))))

Tests:

(define (sqrt x tolerance)
  (stream-limit (sqrt-stream x) tolerance))

(sqrt 2 0.3)      ; 1.4166666666666665
(sqrt 2 0.003)    ; 1.4142156862745097
(sqrt 2 0.000003) ; 1.4142135623746899

Exercise 3.65

(define (ln2-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (ln2-summands (inc n)))))

(define ln2-stream
  (partial-sums (ln2-summands 1)))

(Recall that partial-sums is the procedure that takes a stream \(S\) and returns a stream whose elements are \(S_0, S_0 + S_1, S_0 + S_1 + S_2 \ldots\)).

Without a sequence accelerator:

(display-istream-range ln2-stream 0 10)

; 1.0
; 0.5
; 0.8333333333333333
; 0.5833333333333333
; 0.7833333333333332
; 0.6166666666666666
; 0.7595238095238095
; 0.6345238095238095
; 0.7456349206349207
; 0.6456349206349207
; 0.7365440115440116
; 'done

…there is no convergence, even after 100 terms of the sequence.

With a sequence accelerator:

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)))))

(display-istream-range (euler-transform ln2-stream) 0 10)

; 0.7
; 0.6904761904761905
; 0.6944444444444444
; 0.6924242424242424
; 0.6935897435897436
; 0.6928571428571428
; 0.6933473389355742
; 0.6930033416875522
; 0.6932539682539683
; 0.6930657506744464
; 0.6932106782106783
; 'done

With a sequence accelerator accelerator:

(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)))

(display-istream-range (accelerated-sequence euler-transform ln2-stream) 0 10)

; 1.0
; 0.7
; 0.6932773109243697
; 0.6931488693329254
; 0.6931471960735491
; 0.6931471806635636
; 0.6931471805604039
; 0.6931471805599445
; 0.6931471805599427
; 0.6931471805599454
; +nan.0
; 'done

Exercise 3.66

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.

…challenge accepted :muscle:.

(define int-pairs (pairs integers integers))

(display-istream-range int-pairs 0 60)

Let’s observe for patterns where \(i = j\):

Therefore:

$$\begin{align} f(i, j) = 2^i - 1, i = j \end{align}$$

Next, let’s observe for patterns where \(i < j\):

Firstly, let’s look at the sequences:

The differences in position have the pattern \(2^{i - 1}\). Therefore, we can extend \((1)\) such that:

$$\begin{align} f(i, j) = 2^i + 2^{i - 1} - 1, i + 1 = j \end{align}$$

To generalise \((2)\) so it is true for all \(i < j\), let’s look at the next set of sequences:

The differences in position have the pattern \(2^i(j - i)\). Therefore, we can extend \((2)\) such that:

$$\begin{align} f(i, j) = 2^i(j - i) + 2^{i - 1} - 1, i < j \end{align}$$

Exercise 3.67

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) (list x (stream-car t)))
                (stream-cdr s))
    (interleave
     (stream-map (lambda (x) (list (stream-car s) x))
                 (stream-cdr t))
     (pairs (stream-cdr s) (stream-cdr t))))))

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))))

(define int-pairs (pairs integers integers)) ; Infinitely recurses

No, Louis’ solution won’t work. Recall that (cons-stream a b) is a special form equivalent to (cons a (delay b)), i.e. its second argument is wrapped in a “delayed object”, to be evaluated when required.

Louis’ version lacks the call to cons-stream, which means that interleave is evaluated, which means that the recursive call to pairs is evaluated, which results in the procedure infinitely recursing.

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 int-triples (triples integers integers integers))

(define pythagorean-triples
  (stream-filter
   (lambda (triple) (= (+ (square (car triple))
                          (square (cadr triple)))
                       (square (caddr triple))))
   int-triples))

Test:

(display-istream-range pythagorean-triples 0 4)
; (3 4 5) (6 8 10) (5 12 13) (9 12 15) (8 15 17) 'done

Exercise 3.70

(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)))
           (cond ((> (weight s1car) (weight s2car))
                  (cons-stream
                   s2car
                   (merge-weighted s1 (stream-cdr s2) weight)))
                 ; Unlike `merge`, don't remove duplicates
                 (else
                  (cons-stream
                   s1car
                   (merge-weighted (stream-cdr s1) 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)))

Note: unlike merge, merge-weighted should not remove duplicates. Equally-weighted elements are not necessarily identical elements.

Part (a):

(define weighted-int-pairs
  (weighted-pairs integers integers (lambda (x) (+ (car x) (cadr x)))))

(display-istream-range weighted-int-pairs 0 10)
; (1 1) (1 2) (1 3) (2 2) (1 4) (2 3) (1 5) (2 4) (3 3) (1 6) (2 5) 'done

Part (b):

(define (divisible? x n) (= (remainder x n) 0))

(define not-div-235
  (stream-filter
   (lambda (x) (not (or (divisible? x 2)
                        (divisible? x 3)
                        (divisible? x 5))))
   integers))

(define weighted-not-div-235-pairs
  (weighted-pairs not-div-235
                  not-div-235
                  (lambda (x)
                    (+ (* 2 (car x))
                       (* 3 (cadr x))
                       (* 5 (car x) (cadr x))))))

(display-istream-range weighted-not-div-235-pairs 0 10)
; (1 1) (1 7) (1 11) (1 13) (1 17) (1 19) (1 23) (1 29) (1 31) (7 7) (1 37) 'done

Exercise 3.71

(define (stream-cadr stream)
  (stream-car (stream-cdr stream)))

(define (stream-cddr stream)
  (stream-cdr (stream-cdr stream)))

(define (cube n) (* n n n))

(define (sum-cube pair)
  (+ (cube (car pair))
     (cube (cadr pair))))

(define ramanujan-pairs
  (letrec ((weighted-stream
            (lambda (x)
              (if (= (sum-cube (stream-car x))
                     (sum-cube (stream-cadr x)))
                  (cons-stream
                   (list (stream-car x)
                         (stream-cadr x)
                         (sum-cube (stream-car x)))
                   (weighted-stream (stream-cddr x)))
                  (weighted-stream (stream-cdr x))))))
    (weighted-stream (weighted-pairs integers integers sum-cube))))

(display-istream-range ramanujan-pairs 0 5)
; ((1 12) (9 10) 1729)
; ((2 16) (9 15) 4104)
; ((2 24) (18 20) 13832)
; ((10 27) (19 24) 20683)
; ((4 32) (18 30) 32832)
; ((2 34) (15 33) 39312)
; 'done

Exercise 3.72

(define (stream-caddr stream)
  (stream-car (stream-cddr stream)))

(define (stream-cdddr stream)
  (stream-cdr (stream-cddr stream)))

(define (sum-square pair)
  (+ (square (car pair))
     (square (cadr pair))))

(define three-square-pairs
  (letrec ((weighted-stream
            (lambda (x)
              (if (= (sum-square (stream-car x))
                     (sum-square (stream-cadr x))
                     (sum-square (stream-caddr x)))
                  (cons-stream
                   (list (stream-car x)
                         (stream-cadr x)
                         (stream-caddr x)
                         (sum-square (stream-car x)))
                   (weighted-stream (stream-cdddr x)))
                  (weighted-stream (stream-cdr x))))))
    (weighted-stream (weighted-pairs integers integers sum-square))))

(display-istream-range three-square-pairs 0 5)
; ((1 18) (6 17) (10 15) 325)
; ((5 20) (8 19) (13 16) 425)
; ((5 25) (11 23) (17 19) 650)
; ((7 26) (10 25) (14 23) 725)
; ((2 29) (13 26) (19 22) 845)
; ((3 29) (11 27) (15 25) 850)
; 'done

Exercise 3.73

(define (RC R C dt)
  (lambda (i v0)
    (add-streams (scale-stream i R)
                 (integral (scale-stream i (/ 1.0 C)) v0 dt))))

Exercise 3.74

(define zero-crossings
  (stream-map sign-change-detector
              sense-data
              (stream-cdr sense-data)))

Exercise 3.75

(define (make-zero-crossings input-stream last-value last-avpt)
  (let ((avpt (/ (+ (stream-car input-stream)
                    last-value)
                 2)))
    (cons-stream
     (sign-change-detector avpt last-avpt)
     (make-zero-crossings (stream-cdr input-stream)
                          (stream-car input-stream)
                          avpt))))

Louis’ implementation uses the output of the previous averaging as input for the next averaging. This is incorrect - the averaging process should only use values from the input stream.

Exercise 3.76

(define (smooth input-stream)
  (stream-map average
              input-stream
              (stream-cdr input-stream)))

(define (zero-crossings sense-data)
  (stream-map sign-change-detector
              sense-data
              (stream-cdr sense-data)))

(define (smoothed-zero-crossings input-stream)
  (zero-crossings (smooth input-stream)))

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)))))

(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)

Test:

(stream-ref (solve (lambda (y) y)
                   1
                   0.001)
            1000)
; 2.716923932235896

Note: the solve procedure does not work in DrRacket, but works just fine in MIT/GNU Scheme 9.2. The authors do provide fair warning in a footnote:

This procedure is not guaranteed to work in all Scheme implementations, although for any implementation there is a simple variation that will work. The problem has to do with subtle differences in the ways that Scheme implementations handle internal definitions.

Exercise 3.78

(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

Generalising our implementation of solve-2nd from exercise 3.78:

(define (gen-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.0 C))))
    (define diL (add-streams (scale-stream vC (/ 1.0 L))
                             (scale-stream iL (- (/ R L)))))
    (cons vC iL)))

Exercise 3.81

Just like in exercise 3.06, we can provide simple definitions for random-init and rand-update to test our solution.

(define random-init 0)

(define rand-update inc)

(define (handle-request req val)
  (cond ((eq? req 'generate) (rand-update val))
        ((and (pair? req) (eq? (car req) 'reset)) (cadr req))
        (else (error "Unknown request: HANDLE-REQUEST"))))

(define (random-numbers requests)
  (define random-numbers-int
    (cons-stream
     random-init
     (stream-map handle-request requests random-numbers-int)))
  random-numbers-int)

Test:

(define requests
  (cons-stream 'generate
               (cons-stream '(reset 42)
                            (cons-stream 'generate
                                         (cons-stream '(reset 10)
                                                      (cons-stream 'generate requests))))))

(display-istream-range (random-numbers requests) 0 10)
; 0 1 42 43 10 11 12 42 43 10 11 'done

Exercise 3.82

Note: the definitions of random-in-range, square, and P remain unchanged from exercise 3.05.

Recall from section 3.1.2 that the procedure monte-carlo:

…runs the experiment for the designated number of trials and returns a number telling the fraction of the trials in which the experiment was found to be true.

We begin by modifying monte-carlo so that it produces a stream of these fractions instead:

(define (monte-carlo experiment)
  (define monte-carlo-internal
    (cons-stream
     (if (experiment) 1 0)
     (stream-map (lambda (x) (if (experiment) (+ x 1) x))
                 monte-carlo-internal)))
  (div-streams monte-carlo-internal integers))

We can then rewrite estimate-integral to produce a stream of estimates based on successively more trials:

(define (estimate-integral P x1 x2 y1 y2)
  (define (experiment)
    (let ((x (random-in-range (exact->inexact x1)
                              (exact->inexact x2)))
          (y (random-in-range (exact->inexact y1)
                              (exact->inexact y2))))
      (P x y)))
  (let ((area (* (- x2 x1) (- y2 y1))))
    (define area-stream
      (cons-stream area area-stream))
    (cons-stream
     area
     (mul-streams area-stream (monte-carlo experiment)))))

Tests:

(exact->inexact (/ (stream-ref (estimate-integral (P 5 7 3) 2 8 4 10) 100)
                   (square 3)))
; ~3.08

(exact->inexact (/ (stream-ref (estimate-integral (P 5 7 3) 2 8 4 10) 1000000)
                   (square 3)))
; ~3.142