ぱいそんにっき

The limits of my language are the limits of my world.

計算機プログラムの構造と解釈と闘う:: 対の無限ストリーム編(後)[3.69-3.72]

残り解いていくよ!

前回中途半端で終わったので, 対の無限ストリームの節, 続きを考えてきます. [1]

ex-3.69

三つの無限ストリーム S, T および U を取り, i ≤ j ≤ k なる三つ組 (Si, Tj, Uk) のストリームを生じる手続き triples を書け. triples を使い, 正の整数の Pythagoras 三つ組, つまり i ≤ j で i2 + j2 = k2 である, すべての三つ組 (i, j, k) のストリームを生成せよ.

解答見ながらの理解. pairs を更に拡張して 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)))))

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

Pythagoras という組のストリームも書いてみる.

(define triples-integers
  (triples integers integers integers))

(define pythagoras
  (stream-filter
    (lambda (n)
      (= (+ (square (car n)) (square (cadr n))) (square (caddr n))))
    triples-integers))

テストした結果は github [2] にもあげていますが, すごい... こうやって求められるのに感動. pythagoras の組 4 つだけ求めました. (3 4 5) (6 8 10) (5 12 13) (9 12 15) ですって. 美しいよこのやろう!

ex-3.70

アドホックな混合せの結果の順でなく, 対がある有用な順で現れるようにストリームが出来ると嬉しい. 整数の一つの対が, 他の対「より小さい」という方法が定義出来れば, ex3.56 の merge 手続きに似た技法を使うことが出来る. その一つの方法は「重み関数」W(i, j)を定義し, W(i1, j1) < W(i2, j2)なら, (i1, j1)は(i2, j2)より小さいと規定することである. merge-weighted はもう一つの引数 weight を取る他は, merge に似た手続き merge-weighted を書け. weight は対の重みを計算する手続きで, 要素が結果の混ぜ合せたストリームに現れる順を決めるのに使う これを使い, pairsを, 二つのストリームと重み関数を計算する手続きをとり, 重みに従って順序づけられた対のストリームを生成する手続き weighted-pairs に一般化し, その手続きを使って
a. 和 i + j に従って順序づけられた, i ≤ j なる正の整数の対 (i, j) のすべてのストリーム
b. 和 2i + 3j + 5ij に従って順序づけられた, i ≤ j で, i も j も 2, 3, 5 で割り切れない正の整数の対 (i, j) のすべてのストリーム
を生成せよ.

ex3.56 で解いたやつをもう一度見る.

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

(< s1car s2car) や (> s1car s2car) みたいな条件自体を抽象化すればいいみたい.

(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)))
         (if (< (weight s1car) (weight s2car))
             (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight))
             (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)))

抽象化するのたのしいね! これを使って a. b. を考えます.

  1. 和 i + j に従って順序づけられた, i ≤ j なる正の整数の対 (i, j) のすべてのストリーム
(define (weight-sum-a pairs)
  (+ (car pairs) (cadr pairs)))
(define sum-ij-a
        (weighted-pairs integers integers weight-sum-a))
  1. 和 2i + 3j + 5ij に従って順序づけられた, i ≤ j で, i も j も 2, 3, 5 で割り切れない正の整数の対 (i, j) のすべてのストリーム
(define (weight-sum-b pairs)
  (+ (* 2 (car pairs)) (* 3 (cadr pairs)) (* 5 (car pairs) (cadr pairs))))
(define integers-235
  (stream-filter
    (lambda (x)
      (and (not (= (remainder x 2) 0))
           (not (= (remainder x 3) 0))
           (not (= (remainder x 5) 0))))
    integers))
(define sum-ij-b
        (weighted-pairs integers-235 integers-235 weight-sum-b))

素晴らしすぎる... 抽象化たのしい(2 回目)

ex-3.71

二通り以上の二つの立方数の和で表される数を, 数学者 Srinivasa Ramanujan を記念し Ramanujan 数 (Ramanujan number) という.対の順序づけられたストリームは, こういう数を計算する問題に対する優美な解を提供する. 二通りの方法で二つの立方数の和として書ける数を見つけるには, 和 i3 + j3 に従って順序づけられた整数の対 (i, j)のストリームを生成するだけでよい. そして同じ重みで二つ連続する対をストリームから探す. Ramanujan 数を生成する手続きを書け. 最初のそういう数は1729である. 次の5個は何か.

Ramanujan number というのがあるのか〜と流し読みしたところで考えていきます. [3] 言われたとおりに素直に解いていきますよっ.

; 順序づけられた整数の対 (i, j)のストリームを生成する
(define (weight-cube pairs)
  (let
    ((i (car pairs))
     (j (cadr pairs)))
    (+ (* i i i) (* j j j))))

; 同じ重みで二つ連続する対をストリームから探す
(define (ramanujan-number s)
  (let
    ((s1 (weight-cube (stream-car s)))
     (s2 (weight-cube (stream-car (stream-cdr s)))))
    (if (= s1 s2)
        (cons-stream
          s1
          (ramanujan-number (stream-cdr s)))
        (ramanujan-number (stream-cdr s)))))

; Ramanujan 数を生成する手続き
(define ramanujan-stream
  (ramanujan-number (weighted-pairs integers integers weight-cube)))

出力結果は, 1729, 4104, 13832, 20683, 32832, 39312, 40033, 46683, 64232, 65728... となりました. [4] すごい!すごいよストリーム!!!

ex-3.72

ex-3.71と似た方法で, 三通りの異る方法で二つの平方数の和として書けるすべての数のストリームを生成せよ.

前問と同じ要領で書けばいいのかしら.

(define (weight-square pairs)
  (let
    ((i (car pairs))
     (j (cadr pairs)))
    (+ (* i i) (* j j))))

(define (ramanujan-number-square s)
  (let
    ((s1 (weight-square (stream-car s)))
     (s2 (weight-square (stream-car (stream-cdr s))))
     (s3 (weight-square (stream-car (stream-cdr (stream-cdr s))))))
    (if (= s1 s2 s3)
        (cons-stream
          s1
          (ramanujan-number-square (stream-cdr s)))
        (ramanujan-number-square (stream-cdr s)))))

(define ramanujan-stream
  (ramanujan-number-square (weighted-pairs integers integers weight-square)))

う〜ん... 共通部分をまとめて更に抽象化したいけどひとまずここで 対の無限ストリーム編おわり.

無限個の数の並びからなるストリームを組み合わせてうまく計算することで, ストリームを使わなかったらステップ数がものすごく肥大してしまうような計算量の計算をよりスマートに解けることが分かりました.

ありがとう SICP 先生(^^) 1 つもらった材料を使って 2 つ, 3 つと料理のレパートリーを増やしていくこの感覚... ピースひとつひとつには力がないけど, 揃えて組み合わせて巨大なパズルを埋めていくこの感覚.. プログラミング楽しいです.