ながーい。
Formulating iterations as stream processes
3.63
以下のコードは何故効率が悪いのか？という問題。
(define (sqrt-stream x)
(cons-stream 1.0
(stream-map (lambda (guess)
(sqrt-improve guess x))
(sqrt-stream x))))メモ化してないから。
3.64
ストリームで前の値との差が許容値未満になったらその値を返すようなstream-limitを定義する。
(define stream-cadr (compose stream-car stream-cdr))
(define (stream-limit stream tolerance)
(let loop ((stream stream))
(let ((x1 (stream-car stream))
(x2 (stream-cadr stream)))
(if (< (abs (- x1 x2)) tolerance)
x2
(loop (stream-cdr stream)))
)))
(define (%sqrt x tolerance)
(stream-limit (sqrt-stream x) tolerance))
3.65
(define (div-streams s1 s2) (stream-map / s1 s2)) (define alt-signs (cons-stream 1 (cons-stream -1 alt-signs))) (define ln2-summands (div-streams alt-signs integers)) (define ln2-stream (partial-sums ln2-summands)) (log 2) ; => 0.6931471805599453 (stream-take ln2-stream 10) ; => (1 0.5 0.8333333333333333 0.5833333333333333 0.7833333333333332 0.6166666666666666 0.7595238095238095 0.6345238095238095 0.7456349206349207 0.6456349206349207) (stream-take (euler-transform ln2-stream) 10) ; => (0.7 0.6904761904761905 0.6944444444444444 0.6924242424242424 0.6935897435897436 0.6928571428571428 0.6933473389355742 0.6930033416875522 0.6932539682539683 0.6930657506744464) (stream-take (accelerated-sequence euler-transform ln2-stream) 10) ; => (1 0.7 0.6932773109243697 0.6931488693329254 0.6931471960735491 0.6931471806635636 0.6931471805604039 0.6931471805599445 0.6931471805599427 0.6931471805599454)
Infinite streams of pairs
複数のストリームを組み合わせて1本のストリームにする、という話題。
3.66
interleaveの中に入れられたストリームは、次のエントリを取り出すのに2倍待たなければならない。ので、(pairs integers integers)で生成される(n m)は、だいたい2^n * m番目になる。
3.67
(define (all-pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(stream-map (lambda (y) (list (stream-car s) y)) (stream-cdr t))
(all-pairs (stream-cdr s) t))))
3.68
以下のコードは何故うまくいかないか。
(define (pairs s t)
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
t)
(pairs (stream-cdr s) (stream-cdr t))))interleaveは遅延評価しないので、pair中で自分自身を評価してしまい無限ループに陥るおそれがあるから。
3.69 (3つのストリームをタプルにするtriples, ピタゴラス数)
(define (triples s t u)
(cons-stream
(list (stream-car s) (stream-car t) (stream-car u))
(interleave
(stream-map (lambda (yz) (cons (stream-car s) yz))
(stream-cdr (pairs t u)))
(triples (stream-cdr s) (stream-cdr t) (stream-cdr u)))))
(define pythagorean
(stream-filter (lambda (t) (= (+ (square (car t)) (square (cadr t))) (square (caddr t))))
(triples integers integers integers)))
(stream-take pythagorean 4)
; => ((3 4 5) (6 8 10) (5 12 13) (9 12 15))
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)))
(define a
(weighted-pairs integers integers (lambda (p) (+ (car p) (cadr p)))))
(define b
(stream-filter
(lambda (p)
(fold (lambda (a b) (and a b)) #t
(apply append
(map (lambda (x)
(map (lambda (d) (not (zero? (remainder x d))))
'(2 3 5)))
p))))
(weighted-pairs integers integers
(lambda (p) (+ (* 2 (car p))
(* 3 (cadr p))
(* 5 (car p) (cadr p)))))
))
3.71 (Ramanujan numbers)
Ramanujan numbersとは、なる
nらしい。
(define (cube x) (* x x x))
(define (sum-of-cubes ns) (apply + (map cube ns)))
(define pairs/sum-of-cubes
(weighted-pairs integers integers sum-of-cubes))
(define ramanujan-numbers
(stream-map (compose sum-of-cubes car)
(stream-filter (lambda (p) (= (sum-of-cubes (car p)) (sum-of-cubes (cdr p))))
(stream-map cons pairs/sum-of-cubes
(stream-cdr pairs/sum-of-cubes)))))
(stream-take ramanujan-numbers 6)
; => (1729 4104 13832 20683 32832 39312)
3.72
(define (sum-of-squares ns) (apply + (map square ns)))
(define pairs/sum-of-squares
(weighted-pairs integers integers sum-of-squares))
(define sum-square-in-3
(stream-filter (lambda (l)
(let ((a (sum-of-squares (list-ref l 0)))
(b (sum-of-squares (list-ref l 1)))
(c (sum-of-squares (list-ref l 2))))
(and (= a b) (= b c))))
(stream-map list pairs/sum-of-squares
(stream-cdr pairs/sum-of-squares)
(stream-cdr (stream-cdr pairs/sum-of-squares)))))
(define (display-sum-square-in-3 n)
(define (display-sum-square p)
(apply format #t "~d^2 + ~d^2 = " p))
(for-each
(lambda (p)
(for-each display-sum-square p)
(display (sum-of-squares (car p)))
(newline))
(stream-take sum-square-in-3 n)
))
(display-sum-square-in-3 5)
; => 10^2 + 15^2 = 6^2 + 17^2 = 1^2 + 18^2 = 325
; => 13^2 + 16^2 = 8^2 + 19^2 = 5^2 + 20^2 = 425
; => 17^2 + 19^2 = 11^2 + 23^2 = 5^2 + 25^2 = 650
; => 14^2 + 23^2 = 10^2 + 25^2 = 7^2 + 26^2 = 725
; => 19^2 + 22^2 = 13^2 + 26^2 = 2^2 + 29^2 = 845
Streams as signals
信号も遅延・無限ストリームでできるよね、という話。答えの確認のしようがないので適当に。
3.73 (RC回路)
(define (RC R C dt)
(lambda (i v0)
(stream-map (lambda (x) (+ v0 x))
(add-streams
(scale-stream (/ C) (integral i 0 dt))
(scale-stream R i)))))
3.74
(define zero-crossings (stream-map sign-change-detector sense-data (stream-cdr sense-data)))
3.75
(define (make-zero-crossings input-stream last-value num-entries)
(let ((avpt (/ (+ (stream-car input-stream) (* last-value num-entries)) (+ num-entries 1))))
(cons-stream (sign-change-detector avpt last-value)
(make-zero-crossings (stream-cdr input-stream)
avpt
(+ num-entries 1)))))
3.76
(define (smooth s)
(stream-map (lambda (x y) (/ (+ x y) 2)) s (stream-cdr s)))
(define (make-zero-crossings+ input-stream)
(let ((smooth-input (smooth input-stream)))
(stream-map sign-change-detector smooth-input (stream-cdr smooth-input))))
