sicp/streams.rkt

#lang sicp

(#%require (only racket/trace trace-define))

;; Code from the book
(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-enumerate-interval a b)
  (if (> a b)
      the-empty-stream
      (cons-stream a
                   (stream-enumerate-interval (+ a 1) b))))

(define (display-line x) (newline) (display x))
(define (show x)
  (display-line x)
  x)

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

;; (define (display-stream s)
;;   (stream-for-each display-line s))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

(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 (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

(define (integral integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (add-streams (scale-stream integrand dt)
                              int)))
  int)


;; Racket versions of stream procedures
;; NB lang sicp uses promises for delayed evaluation.  These can be forced
;; directly with force (no evaluation needed).

(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

;; Utility functions
(define (display-n-stream n s)
  (if (and (> n 0) (not (stream-null? s)))
      (begin (display-line (stream-car s))
             (display-n-stream (- n 1) (stream-cdr s)))))

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

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

;; 3.50

(define (stream-map proc . argstreams)
  (if (null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
	      (cons proc (map stream-cdr argstreams))))))

(#%require (only racket/base module+))
(#%require rackunit)
(module+ test
  (define a (cons-stream 1 (cons-stream 2 (cons-stream 3 the-empty-stream))))
  (define b (cons-stream 10 (cons-stream 20 (cons-stream 30 the-empty-stream))))
  (define c (cons-stream 100 (cons-stream 200 (cons-stream 300 the-empty-stream))))

  (define d (stream-map + a b c))
  (check-equal? (stream-car d) 111)
  (check-equal? (stream-car (stream-cdr d)) 222)
  (check-equal? (stream-car (stream-cdr (stream-cdr d))) 333))

(module+ 3_51
  (define x
    (stream-map show
                (stream-enumerate-interval 0 10)))

  (stream-ref x 5)
  ;; Shows 0 1 2 3 4 5 5
  
  (stream-ref x 7)
  ;; Shows 6 7 7
  ;; Because racket's implementation using promises memoises the delayed
  ;; objects.  If this wasn't memoised, it would probably show
  ;; 0 1 2 3 4 5 6 7 7
  )

(module+ 3_52
  (define sum 0)

  (define (accum x)
    (set! sum (+ x sum))
    sum)
  ;; sum shows the value of the element of seq that was last evaluated.

  (define seq (stream-map accum (stream-enumerate-interval 1 20)))
  ;; sum is now 1, because we have evaluated accum on the first
  ;; element of the interval (1)
  (define y (stream-filter even? seq))
  ;; sum is now 6, because we keep applying accum until we get to an
  ;; even number.  The first is 6.
  (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                           seq))
  ;; sum is now 10, because we keep applying accum until we get to a
  ;; multiple of 5.  The first is 10.
  
  (stream-ref y 7)
  ;; Displays 136, which is the 8th even element of seq.  sum is 136,
  ;; because we've evaluated all stream elements up to this one.
  (display-stream z)
  ;; Displays 10, 15, 45, 55, 105, 120, 190, 210, which are all
  ;; elements of seq that are multiples of 5.  sum is 210,
  ;; If delay wasn't memoised, then sum would be 210+136 here, as we
  ;; would have double evaluated the elements of seq required to get
  ;; elements 0 to 7 of y.

)

;; 3.53: the program will output the powers of 2.
(module+ 3_53
  (define s (cons-stream 1 (add-streams s s)))

  (display-n-stream 10 s))

(module+ 3_54
  (define factorials
    (cons-stream 1
                 (mul-streams (integers-starting-from 2)
                              factorials)))

  (display-n-stream 10 factorials))


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

(module+ 3_55
  (display-n-stream 10 (partial-sums integers)))

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

  (display-n-stream 20 S))

;; 3.57: With memoisation, calculating fib(n) needs n-1 additions
;; (fib(0) and fib(1) are predefined, so we have n-2 to get to
;; fib(n-1) and then another addition to do (fib(n-2) + fib(n-1))).
;; So this is O(n).
;; Without memoisation, show that fib(n) takes fib(n+1) additions.
;; Using an exercise 1.13, this implies that calculation of fib(n) is
;; exponential in the number of additions.
;; Proof by induction P(n): TODO base case.
;; fib(4) = fib(3) + fib(2), which requires 2+1 calls to stream-cdr
;; Assume P(n).  fib(n+1) = fib(n) + fib(n-1).  From P(n), this
;; requires fib(n+1) + fib(n) = fib(n+2) additions.

;; 3.58: expand outputs the fraction expansion of num/den in base radix.
(module+ 3_58
  (define (expand num den radix)
    (cons-stream
     (quotient (* num radix) den)
     (expand (remainder (* num radix) den) den radix)))

  (display-n-stream 10 (expand 1 7 10))
  (newline)
  (display-n-stream 10 (expand 3 8 10))

  )

;; 3.59
(define (integrate-series a)
  (div-streams a (integers-starting-from 1)))

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

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

;; 3.60
(define add-series add-streams)
(define scale-series scale-stream)

;; (\Sigma_0^{\infinity} a_ix^i)(\Sigma_0^{\infinity} b_ix^i)
;; = a_0.b_0 + a_0.\Sigma_1^{\infinity} b_ix^i
;;   + (\Sigma_1^{\infinity} a_ix^i)(\Sigma_0^{\infinity} b_ix^i)
;; (hint from https://eli.thegreenplace.net/2007/11/05/sicp-sections-351-352/)
(define (mul-series s1 s2)
  (cons-stream
   (* (stream-car s1) (stream-car s2))
   (add-series (scale-series (stream-cdr s2) (stream-car s1))
               (mul-series (stream-cdr s1) s2))))

(define zeroes (cons-stream 0 zeroes))

(define (make-stream l)
  (cond ((null? l) zeroes)
        (else (cons-stream
               (car l)
               (make-stream (cdr l))))))

(define make-series make-stream)

(define (display-stream s n)
  (define (display-term s n)
    (if (> n 0)
        (begin
          (display (stream-car s))
          (display " ")
          (display-term (stream-cdr s) (- n 1)))))
  (display-term s n))

(define display-series display-stream)

(define (eval-series s x n)
  (define (eval-iter s i sum)
    (if (> i n)
        sum
        (eval-iter
         (stream-cdr s)
         (+ i 1)
         (+ sum (* (stream-car s) (expt x i))))))
  (eval-iter s 0 0))

(module+ test
  ;; (2) * (0 + x) = (0 + 2x)
  (define prod-1
    (mul-series
     (make-series '(2))
     (make-series '(0 1))))
  (check-equal? (stream-ref prod-1 0) 0)
  (check-equal? (stream-ref prod-1 1) 2)

  ;; (1 + x) * (1 + x) = (1 + 2x + x^2)
  (define prod-2
    (mul-series
     (make-series '(1 1))
     (make-series '(1 1))))
  (check-equal? (stream-ref prod-2 0) 1)
  (check-equal? (stream-ref prod-2 1) 2)
  (check-equal? (stream-ref prod-2 2) 1))

(module+ test
  (define s2+c2
    (add-series
     (mul-series cosine-series cosine-series)
     (mul-series sine-series sine-series)))
  (check-equal? (stream-ref s2+c2 0) 1)
  (check-equal? (stream-ref s2+c2 1) 0)
  (check-equal? (stream-ref s2+c2 2) 0))

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

(module+ test
  (define cos-inv (invert-unit-series cosine-series))
  (define one (mul-series cosine-series cos-inv))

  (check-equal? (stream-ref one 0) 1)
  (check-equal? (stream-ref one 1) 0)
  (check-equal? (stream-ref one 2) 0))

;; 3.62
(define (div-series s1 s2)
  (let ((div-constant (stream-car s2)))
    (if (= 0 div-constant)
        (error "DIV-SERIES: divisor has zero constant term" s2)
        (mul-series
         (scale-stream s1 (/ 1 div-constant))
         (invert-unit-series
          (scale-stream s2 (/ 1 div-constant)))))))

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

(module+ test
  (define (close-to x y epsilon)
    (and (< y (+ x epsilon))
         (> y (- x epsilon))))

  (define-simple-check (check-tan? x)
    (close-to (tan x)
              (eval-series tangent-series x 50)
              0.01))

  (check-tan? 0)
  (check-tan? 1)
  (check-tan? -1))


;; 3.63: Without the local variable definition of guesses in
;; sqrt-stream, there is no way for later elements of the stream to
;; refer to the previously calculated elements (that are bound to the
;; local variable guesses in the environment of the first version of
;; the procedure).  As such, the earlier terms have to be recalculated
;; each time.

;; 3.64


(define (stream-limit s tolerance)
  (let ((s0 (stream-car s))
        (s1 (stream-car (stream-cdr s))))
    (if (< (abs (- s0 s1)) tolerance)
        s1
        (stream-limit (stream-cdr s) tolerance))))

(define (convergence-steps s tolerance)
  (define (converge-iter s n)
    (let ((s0 (stream-car s))
          (s1 (stream-car (stream-cdr s))))
      (if (< (abs (- s0 s1)) tolerance)
          n
          (converge-iter (stream-cdr s) (+ n 1)))))
  (converge-iter s 0))

(define (average a b)
  (/ (+ a b) 2))

;; From the book
(define (sqrt-improve guess x)
  (average guess (/ x guess)))

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

(define (square x) (* x x))

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


;; 3.65

(define (ln-summands n)
  (cons-stream
   (/ 1.0 n)
   (stream-map - (ln-summands (+ n 1)))))

;; Takes 9998 steps to converge with tolerance 0.0001
(define ln-stream
  (partial-sums (ln-summands 1)))

;; Takes 11 steps to converge with tolerance 0.0001
(define euler-ln-stream
  (euler-transform ln-stream))

;; Takes 3 steps to converge with tolerance 0.0001
(define accelerated-ln-stream
  (accelerated-sequence euler-transform ln-stream))


;; 3.66

;; From the book
(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))

(define (element-pos s e)
  (define (iter s n)
    (if (equal? (stream-car s) e)
        n
        (iter (stream-cdr s) (+ n 1))))
  (iter s 1))

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

;; By observation of the pattern, the following procedure calculates the
;; position in the stream (pairs integers integers) of (i j).
(module+ 3-66
  (define (pos i j)
    (if (= i j)
        (- (expt 2 j) 1)
        (+ (* (expt 2 i) (- j i))
           (- (expt 2 (- i 1)) 1))))
  
  (define int-pairs (pairs integers integers))
  
  (check-equal? (pos 10 10) (element-pos int-pairs '(10 10)))
  (check-equal? (pos 10 30) (element-pos int-pairs '(10 30)))
  (check-equal? (pos 1 100) (element-pos int-pairs '(1 100)))
  (check-equal? (pos 2 50) (element-pos int-pairs '(2 50))))

;; Positions in the list:
;; (1,100) 198
;; (99,100) 950737950171172051122527404031
;; (100,100) 1267650600228229401496703205375
;;
;; In general, the first row is augmented every 2nd element, the second row every
;; 4th, the third row every 8th, etc.

(module+ 3-67

  ;; Redefine pairs to return all pairs of integers. This needs the extra
  ;; stream of the left column to be mixed in
  (define (pairs 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))))))

(module+ 3-68
  (#%require racket/trace)
  ;; Louis definition of pairs from the book
  (trace-define (pairs s t)
    (interleave
     (stream-map (lambda (x) (list (stream-car s) x))
                 t)
     (pairs (stream-cdr s) (stream-cdr t))))

  ;; 3.68:
  ;; This goes into an infinite loop because interleave is evaluated immediately
  ;; which in turn evaluates pairs on the cdr of streams s and t.
  ;; There is no degenerate case to stop the recursion.  In the previous
  ;; case, this is fine because the recursive call to pairs is only
  ;; evaluated on demand, whereas here, it is evaluated immediately.
  )


;; 3.69
;; triples generates all triples (s_i, t_j, u_k) such that i<=j<=k.
;; Let S(n) = \bigcup_{i=0}^\infty \bigcup_{j=i}^\infty
;; \bigcup_{k=j}^\infty (i,j,k), such that i<=j<=k.
;;
;; Then: S(n) = {(n,n,n) \cup \bigcup_{j=1}^\infty
;; \bigcup_{k=j}^\infty (0,j,k) \cup \bigcup_{k=1}^\infty (0,0,k)
;; \cup S(n+1)}.
;; The set of triples is then S(0)

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

(module+ 3-69
  (define pythag-triples
    (stream-filter
     (lambda (s)
       (let ((i (car s))
             (j (cadr s))
             (k (caddr s)))
         (=
          (+ (* i i) (* j j))
          (* k k))))
     (triples integers integers integers))))

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

(module+ 3-70
  (define int-pairs-by-sum
    (weighted-pairs integers integers
                    (lambda (x)
                      (+ (car x) (cadr x)))))

  ;; any-factors? is a procedure that returns true if any of n are factors
  (define (any-factors? n)
    (define (factors-of-x? factors x)
      (if (null? factors)
          #f
          (or (= (remainder x (car factors)) 0)
              (factors-of-x? (cdr factors) x))))
    (lambda (x) (factors-of-x? n x)))

  ;; Would have been better to map (any-factors? '(2 3 5)) over x,
  ;; but racket's ormap doesn't seem to work here.
  (define int-pairs-235
    (stream-filter
     (lambda (x)
       (not (or ((any-factors? '(2 3 5)) (car x))
                ((any-factors? '(2 3 5)) (cadr x)))))
     (weighted-pairs integers integers
                     (lambda (x)
                       (+ (* (car x) 2)
                          (* (cadr x) 3)
                          (* (car x) (cadr x) 5)))))))

(module+ 3-71-72
  (define (sum-powers p)
    (lambda (x)
      (apply + (map (lambda (y) (expt y p)) x))))

  (define (pairs-by-sum-powers p)
    (weighted-pairs integers integers (sum-powers p)))

  ;; Mask (by #t) those elements of the stream s that have
  ;; n-1 following elements that are equal.
  (define (n-consecutive-equal-mask s n)
    ;; Compare s with (n-1) stream-cdrs.  If they are all equal,
    ;; then s has n consecutive equal elements.
    (define (args s n)
      (if (= n 0) '()
          (cons s (args (stream-cdr s) (- n 1)))))
    (apply stream-map = (args s n)))
  
  (define (sum-powers-n-ways p n)
    (let* ((pairs-stream (pairs-by-sum-powers p))
           (sum-power-stream
            (stream-map (sum-powers p) pairs-stream)))
      ;; If the element has n pairs following it such that each
      ;; pair (i,j) has the property that (i^p + j^p) is equal, then
      ;; the corresponding mask element will be #t.  Pull out all such
      ;; elements of the pairs stream.
      (stream-filter (lambda (x) (number? x))
                     (stream-map (lambda (i x) (if i x #f))
                                 (n-consecutive-equal-mask sum-power-stream n)
                                 sum-power-stream))))
  
  (define (all-pairs sum-of-powers p n)
    (let* ((all-pairs-stream (pairs-by-sum-powers p))
           (pairs-stream
            (stream-filter
             (lambda (x) (= ((sum-powers p) x) sum-of-powers))
             all-pairs-stream)))
      (letrec ((n-pairs (lambda (pairs-stream n)
                          (if (= n 1)
                              (list (stream-car pairs-stream))
                              (cons (stream-car pairs-stream)
                                    (n-pairs (stream-cdr pairs-stream) (- n 1)))))))
        (n-pairs pairs-stream n))))

  (define (sum-powers-n-ways-pairs p n)
    (let* ((powers (sum-powers-n-ways p n))
           (pairs (stream-map
                   (lambda (x) (all-pairs x p n))
                   powers)))
      (stream-map (lambda (power pairs)
                    (list power pairs))
                  powers
                  pairs)))

  (define ramanujan-pairs (sum-powers-n-ways-pairs 3 2))
  ;; First six Ramanujan numbers (and pairs):
  ;; (1729 ((9 10) (1 12))) (4104 ((9 15) (2 16)))
  ;; (13832 ((18 20) (2 24))) (20683 ((19 24) (10 27)))
  ;; (32832 ((18 30) (4 32))) (39312 ((15 33) (2 34))) 

  (define sum-squares-three-ways (sum-powers-n-ways-pairs 2 3))
  ;; First six:
  ;; (325 ((10 15) (6 17) (1 18))) (425 ((13 16) (8 19) (5 20)))
  ;; (650 ((17 19) (11 23) (5 25))) (725 ((14 23) (10 25) (7 26)))
  ;; (845 ((19 22) (13 26) (2 29))) (850 ((15 25) (11 27) (3 29))) 
  )

;; Streams as signals

(module+ 3-73
  (define (RC R C dt)
    (lambda (i v0)
      (add-streams
       (scale-stream i R)
       (scale-stream (integral i v0 dt)
                     (/ 1 C))))))


(define (sign-change-detector x1 x2)
    (cond ((and (< x1 0) (> x2 0)) 1)
          ((and (> x1 0) (< x2 0)) -1)
          (else 0)))

(module+ 3-74
  ;; From the book
  (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 sense-data
    (make-stream '(1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4)))
  
  ;; This is equivalent to (make-zero-crossings sense-data 0)
  (define zero-crossings
    (stream-map sign-change-detector
                sense-data
                (cons-stream 0 sense-data))))

(module+ 3-75
  (define sense-data
    (make-stream '(1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4)))

  ;; Updated from the book.  It is necessary to calculate the
  ;; current and last point from the stream and then to compare
  ;; this average with the last average.  This requires passing
  ;; in both the last value and the last average to make-zero-crossings.
  (define (make-zero-crossings input-stream last-value last-avpt)
    (let* ((current-value (stream-car input-stream))
           (avpt (/ (+ current-value last-value) 2)))
      (cons-stream (sign-change-detector last-avpt avpt)
                   (make-zero-crossings (stream-cdr input-stream)
                                        current-value
                                        avpt))))

  )

(module+ 3-76
  (define sense-data
    (make-stream '(1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4)))

  (define (smooth input-stream)
    (scale-stream
     (add-streams input-stream
                  (cons-stream 0 input-stream))
     1/2))

  ;; Apply condition to input before finding zero crossings
  (define (zero-crossings condition input)
    (stream-map sign-change-detector
                (cons-stream 0 (condition input))
                (smooth sense-data))))

;; Modified for delayed integrand
(define (integral-delayed delayed-integrand initial-value dt)
  (cons-stream initial-value
               (let ((integrand (force delayed-integrand)))
                 (if (stream-null? integrand)
                     the-empty-stream
                     (integral-delayed (delay (stream-cdr integrand))
                                       (+ (* dt (stream-car integrand))
                                          initial-value)
                                       dt)))))

;; Implicit-style from the book
(define (integral-implicit delayed-integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (let ((integrand (force delayed-integrand)))
                   (add-streams (scale-stream integrand dt)
                                int))))
  int)

(module+ 3-77
  ;; From the book but modified to use racket/local
  (#%require racket/local)
  (define (solve f y0 dt)
    (local ((define y (integral-delayed (delay dy) y0 dt))
            (define dy (stream-map f y)))
      y)))

(module+ 3-78
  (#%require racket/local)
  (define (solve-2nd a b dt y0 dy0)
    (local
        ((define y (integral-delayed (delay dy) y0 dt))
         (define dy (integral-delayed (delay ddy) dy0 dt))
         (define ddy (add-streams
                      (scale-stream dy a)
                      (scale-stream y b))))
      y)))

;; (module+ test
;;   ;; Test: a=0, b=-1, y0=1, dy0=0: d^2/dx(cos(x)) = -cos(x).  Evaluate at pi -> -1
;;   ;;       a=0, b=-1, y0=0, dy0=1: d^2/dx(sin(x)) = -sin(x).  Evaluate at pi -> 0

;;   (check (close-to (stream-ref (solve-2nd 0 -1 (/ 3.1415 1000) 1 0) 1000)
;;                    -1
;;                    0.01))
  
;;   (check (close-to (stream-ref (solve-2nd 0 -1 (/ 3.1415 1000) 0 1) 1000)
;;                    0
;;                    0.01)))

(module+ 3-79
  (#%require racket/local)
  (define (solve-2nd f dt y0 dy0)
    (local
        ((define y (integral-delayed (delay dy) y0 dt))
         (define dy (integral-delayed (delay ddy) dy0 dt))
         (define ddy (stream-map f dy y)))
      y)))

(module+ 3-80
  (#%require racket/local)
  (define (RLC R L C dt)
    (lambda (vC0 iL0)
      (local
          ((define vC (integral-delayed (delay dvC) vC0 dt))
           (define iL (integral-delayed (delay diL) iL0 dt))
           (define dvC (scale-stream iL (/ -1 C)))
           (define diL (add-streams
                        (scale-stream iL (/ (* -1 R) L))
                        (scale-stream vC (/ 1 L)))))
        (cons vC iL)))))

(module+ 3-81
  (define random-init 7)

  ;; From ch3support.scm:
  ;;For Section 3.1.2 -- written as suggested in footnote,
  ;; though the values of a, b, m may not be very "appropriately chosen"
  (define (rand-update x)
    (let ((a 27) (b 26) (m 127))
      (modulo (+ (* a x) b) m)))

  (define (rand-stream requests)
    (define (next request val)
      (if (and (pair? val)
               (eq? (car request) 'reset))
          (cadr request)
          (rand-update val)))
    (define rand
      (cons-stream random-init
                   (stream-map next requests rand)))
    rand)

  ;; Test with (define req (make-stream  '(generate generate (reset 19) generate)))

  ;; 3.82
  ;; Accumulate stream to give a running total
  (define (stream-acc input)
    (define acc
      (cons-stream (stream-car input)
                   (add-streams acc
                                (stream-cdr input))))
    acc)

  ;; Scale stream of random numbers to lie in [low,high]
  (define (random-stream-in-range low high)
    (define ones (cons-stream 1 ones))
    (define (random-stream)
      (cons-stream (random (- high low))
                   (random-stream)))
    (add-streams (scale-stream ones low)
                 (random-stream)))

  ;; A procedure that generates a stream of booleans:
  ;; Does a random element from [-1,1]x[-1,1] lie in the cirle
  ;; of radius 1 centred at (0, 0).
  ;; P(in circle) = pi*1^2 / 4 = pi/4
  (define in-circle-test
    (lambda ()
      (define (in-circle? radius)
        (lambda (x y)
          (<= (+ (* x x) (* y y))
              (* radius radius))))
      (let ((radius 1)
            (x (random-stream-in-range -1.0 1.0))
            (y (random-stream-in-range -1.0 1.0)))
        (stream-map (in-circle? radius) x y))))
  
  (define (monte-carlo experiment-stream)
    (define num-trials integers)
    (define num-trials-passed
      (stream-acc (stream-map (lambda (x) (if x 1 0)) experiment-stream)))
    (div-streams num-trials-passed num-trials))
  
  ;; Area of circle is pi/r^2.  Area of square is 2*2 = 4
  ;; So calculated probability is pi/4.
  (define estimate-pi
    (scale-stream (monte-carlo (in-circle-test)) 4.0))

  )