理系学生日記

おまえはいつまで学生気分なのか

問題 3-69 (3.5.3 Exploiting the Stream Paradigm)

まずは,三つ組の無限ストリームを作る関数 triples.これであってんのかなー.

(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))
                (pairs t u))
    (triples (stream-cdr s) (stream-cdr t) (stream-cdr u)))))

あとは,i^2+j^2=k^2,つまりピタゴラスの定理を満たす (i, j, k) のみ含む無限ストリームを作るだけだ!

(define pythagorean-triples
  (stream-filter (lambda (x) (= (+ (square (car x))
                                   (square (cadr x)))
                                (square (caddr x))))
                 (triples integers integers integers)))

よしゃ,出力させてみるお!

gosh> (dump-stream pythagorean-triples 5)
(3 4 5), (6 8 10), (5 12 13), (9 12 15), (8 15 17), done

ピタゴラスの定理を満たす数の組み合わせを求めるにはかなり時間がかかるんだけど,一度算出したのはメモされるから,次の呼び出しでは速攻で出力されるようになる.メモ化の威力がよくわかる問題になってる.