[Back]

3.5 流

3.50

(define (stream-map proc . argstreams)
    (if (stream-empty? (car argstreams))
        `()
        (stream-cons (apply proc (map stream-first argstreams))
                    (apply stream-map (cons proc (map stream-second argstreams))))))

3.51

由于使用了记忆化过程的原因,我们求值第一个得到的12345序列并不会在第二个出现

3.52

第一个表达式后sum的值为136,第二个之后的值为210

求值第一个给出136,第二个给出10 15 45 55 105 120 190 210

每次定义化流都只会求出第一个值。

会,因为记忆化的存在,我们可以确保accum在每一个数上只求值了一遍。

3.53

这个stream同样会生产出2的各个幂

3.54

(define (mul-streams s1 s2)
    (stream-map * s1 s2))
(define factorials (stream-cons 1 (mul-streams integers factorials)))

3.55

(define (partial-sum stream)
(define (iter argstream result)
    (stream-cons result
        (iter (stream-rest argstream) (+ result (stream-first argstream)))))
    (iter (stream-rest stream) (stream-first stream)))

3.56

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

3.57

需要调用n-1次

如果不使用记忆化优化,那么显然计算过程可以画成二叉树形式,复杂度也就是指数级了。

3.58

这个序列产生的是num/den的radix进制小数

0.1428571228……

0.3750000000……

3.59

(define (integrate-series stream)
    (define (iter s n)
        (stream-cons (* (/ 1 n) (stream-first s))
            (iter (stream-rest s) (+ n 1))))
    (iter stream 1))
(define cosine-series
(stream-cons 1 (integrate-series (stream-cons 1 (integrate-series (stream-cons 1 (integrate-series (stream-cons 1 (integrate-series cosine-series)))))))))

3.60

(define (mul-series s1 s2)
    (stream-cons (* (stream-first s1) (stream-first s2))
    (add-streams (mul-series (stream-rest s1) (scale-stream (stream-first s1) s2)) (mul-series (scale-stream (stream-first s2) s1) (stream-rest s2)))))

3.61

(define (inv-series s)
	(stream-cons 1 (mul-series (stream-map (lambda (x) (- x)) (stream-rest s)) (inv-series s))))

3.62

(define (div-series r s)
(add-streams r (mul-series (stream-map (lambda (x) (- x)) (stream-rest s)) (div-series r s))))

3.63

这样带来的一个问题是,我们每次stream-map的都是从头开始的序列,也就是,我们对之前的数做了多余的优化,带来了冗余的计算。

会,这样所带来的是我们不需要实际的去improve每一项值。

3.64

(define (stream-limit s tolerance)
    (let ((s0 (stream-ref s 0))
          (s1 (stream-ref s 1)))
        (cond ((< (abs (- s1 s0)) tolerance) s1)
              (else (stream-limit (stream-rest s) tolerance)))))

3.65

(define (ln2-summands n)
    (stream-cons (/ 1.0 n)
        (stream-map - (ln2-summands (+ n 1)))))
(define ln2
    (partial-sum (ln2-summands 1)))

3.66

在(1 n)前会有2*(n-1)个序列

在(n m)前会有(n+3)n(m-1)/2个序列

3.67

(define (pairs s t)
    (stream-cons
        (list (stream-first s) (stream-first t))
        (interleave
            (interleave
                (stream-map (lambda (x) (list x (stream-first t))) (stream-rest s))
                (stream-map (lambda (x) (list (stream-first s) x)) (stream-rest t)))
            (pairs (stream-rest s) (stream-rest t)))))

3.68

这样会让程序无限运行下去而无法输出结果,因为它并没有用stream-cons来对后续部分做求值允诺。

3.69

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

3.70

(define (weighted-pairs s t weight)
    (stream-cons
        (list (stream-first s) (stream-first t))
            (merge-weighted
                (stream-map (lambda (x) (list (stream-first s) x)) (stream-rest t))
                (weighted-pairs (stream-rest s) (stream-rest t) weight)
                weight)))
(define (sum-weight pair)
    (+ (car pair) (car (cdr pair))))
(define (weight235 pair)
    (+ (* 2 (car pair)) (* 3 (car (cdr pair))) (* 5 (car pair) (car (cdr pair)))))
(define (can-divide-235? x)
    (or (= (remainder x 2) 0) (= (remainder x 3) 0) (= (remainder x 5) 0)))
(display-stream (stream-filter 
                (lambda (pair) (and (can-divide-235? (car pair)) (can-divide-235? (car (cdr pair))))) 
                (weighted-pairs integers integers weight235)))

3.71

(define (cubic x)
(* x x x))
(define (weight-cubic pair)
    (let ((x (car pair))
          (y (car (cdr pair))))
        (+ (cubic x) (cubic y))))
(define (iter s)
    (let ((s0 (stream-ref s 0))
          (s1 (stream-ref s 1)))
        (cond ((= (weight-cubic s0) (weight-cubic s1))
                (stream-cons (weight-cubic s0)
                (iter (stream-rest (stream-rest s)))))
              (else (iter (stream-rest s))))))
(define Ramanujan-number
    (iter (weighted-pairs integers integers weight-cubic)))

分别是

4104 13832 20683 32832 39312

3.72

修改iter即可

(define (iter s)
    (let ((s0 (stream-ref s 0))
          (s1 (stream-ref s 1))
          (s2 (stream-ref s 2)))
        (cond ((= (weight-cubic s0) (weight-cubic s1) (weight-cubic s2))
                (stream-cons (list (weight-cubic s0) s0 s1 s2)
                (iter (stream-rest (stream-rest (stream-rest s))))))
              (else (iter (stream-rest s))))))

3.73

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

3.74

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

3.75

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

3.76

(define (smooth stream)
    (let ((s0 (stream-ref stream 0))
          (s1 (stream-ref stream 1)))
        (stream-cons (average s0 s1)
        (smooth (stream-rest stream)))))
(define zero-crossings
    (stream-map sign-change-detector (smooth sense-data) (stream-cons 0 (smooth sense-data))))

3.77

(define (integral delayed-intergrand initial-value dt)
    (stream-cons initial-value
        (let ((intergrand (force delayed-intergrand)))
            (if (stream-empty? intergrand)
                `()
                (integral (delay (stream-rest intergrand))
            (+ (* dt (stream-first intergrand))
                initial-value)
                dt)))))

3.78

(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-stream (scale-stream dy a) (scale-stream y b)))
    y)

3.79

(define (solve-2nd a b dt y0 dy0 f)
    (define y (integral (delay dy) y0 dt))
    (define dy (integral (delay ddy) dy0 dt))
    (define ddy (stream-map f dy y))
    y)

3.80

(define (RLC R L C dt)
    (lambda (vc0 il0)
        ((define il (integral (delay dil) il0 dt))
        (define vc (integral (delay dvc) vc0 dt))
        (define dil (add-stream (scale-stream il (/ (- R) L)) (scale-stream vc (/ 1 L))))
        (define dvc (scale-stream il (/ (- 1) C)))
            (cons il vc))))

3.81

(define (reset)
    (lambda (n)
        (rand n)))
(define (rand seed)
    (define (generate stream)
        (stream-rest stream))
    (let ((stream (stream-cons seed
          (stream-map random-update random-stream))))
        (define (dispatch m)
            (cond ((eq? m generate) (generate stream))
                  ((eq? m reset) (reset))))
        dispatch))

3.82

(define (estimate-integral p x1 x2 y1 y2)
    (define random-numbers-in-range
        (merge (stream-filter (ranged x1 x2) random-numbers) (stream-filter (ranged y1 y2) random-numbers)))
    (stream-map (lambda (x) (* x (- x2 x1) (- y2 y1)))
        (monte-carlo (map-successive-pairs p random-numbers-in-range) 0 0)))