SICP 練習問題 1.12 （Pascal三角形）

今度は１日で解けた～。（マイペースマイペース。。）
思ったんだけど、１つの問題につき１エントリの方がいいかもなぁ。
さて、Pascal三角形です。


【問題】
次の数のパターンをPascal三角形と言う。

0:      1
1:     1 1
2:    1 2 1
3:   1 3 3 1
4:  1 4 6 4 1

三角形の返上の数は全て 1、三角形の内部の数はその上の２つの数の和である。
再帰的プロセスの方法でPascal三角形の要素を計算する手続きを書け。



【解答】
リストで考えると楽かもと思い、要素が数のリストを受け取ったら、
それに対して上記の条件（その上の２つの数の和）を満たすリストを生成して返す、
という方針でまずは問題の核を解く。

登場人物は、元になるリスト「src」、計算して生成されるリスト「dst」の２つ。
こいつらを渡してどうするか。

(define (calc src dst)
  (if (null? src) ;;srcがnullならdstを返却。
      dst
      (calc                              ;;そうでなければ、
        (cdr src)                        ;;srcの残りと、
        (cons (+ 更に前の要素 (car src)) ;;「更に前の要素」とsrcの先頭要素の和を
              dst))))                    ;;dstに連結したものを引数としてcalcに渡す。

さて、ここで「更に前の要素」なるものが登場しましたが、これはsrcのcarよりも一つ前に格納されていた数値です。つまり、上記のソースではもはやアクセスできない要素になっています。
従って、引数として渡しちゃいます。

(define (calc v src dst) ;「v」として、srcのcarよりも一つ前の情報を渡しちゃう。
  (if (null? src) ;;srcがnullならdstを返却。
      dst
      (calc
        (car src) ; 今のsrcのcarを次の「v」としてcalcに渡す。
        (cdr src)
        (cons (+ v (car src)) ;「v」とsrcのcarを加算する。
              dst))))

ここで一回実行してみましょう。

gosh> (calc 0 '(1) '())
(1)
gosh> (calc 0 '(1 1) '())
(2 1)
gosh> (calc 0 '(1 2 1) '())
(3 3 1)
gosh> (calc 0 '(1 3 3 1) '())
(4 6 4 1)
gosh> (calc 0 '(1 4 6 4 1) '())
(5 10 10 5 1)
gosh> 

・・・最後に連結されるべき要素が連結されていない？
一つ前のコードを良く見ると、確かに終了判定された際にそのままdstを返してますね。
これじゃあ最後のsrcリストの要素が無視されてしまう。。
なので、終了前に「v」をdstに連結してしまおう。

(define (calc v src dst)
  (if (null? src)
      (cons v dst) ; 終了時に「v」を「dst」に連結してから返却
      (calc
        (car src)
        (cdr src)
        (cons (+ v (car src))
              dst))))

これでどうだ！

gosh> (calc 0 '(1) '())
(1 1)
gosh> (calc 0 '(1 1) '())
(1 2 1)
gosh> (calc 0 '(1 2 1) '())
(1 3 3 1)
gosh> (calc 0 '(1 5 1) '())
(1 6 6 1)
gosh> 

おお～、できた。

さて、今度はこのイテレータを呼び出す関数を考える。
呼び出す側は、何番目の行を表示させるか、を引数として渡してあげたい感じなので、インターフェースとして行番号を渡してみる。

(define (f row)
  どうにかしてcalcを呼び出す)

こんな感じ。とりあえずcalcを呼び出してみる。

(define (f row)
  (calc 0 元ネタのリスト '()))

元ネタのリストは、calcが返却するリストです。こいつは元をたどれば「f」が渡してやるべきリストなので、初期値は「'(1)」になります。なので、letを使って、

(define (f row)
  (let ((src '(1)))
    (calc 0 src '())))

さて、これだと一発呼んで終わっちまうので、calcが返却してくるリストを使って、更にcalcを呼び出す必要があり、それはrowで指定された回数だけ呼び出す必要があるので、名前付きletを使って再帰してみる。

(define (f row)
  (let loop ((src '(1)))
    (loop (calc 0 src '()))))

これだと終了条件がないので、終了条件を考えると、row回やったら終わるので、
letにcount変数を指定してやって、初期値をrow、loop呼び出すたびに１づつ減らしていって0になったら終了する。

(define (f row)
  (let loop ((count row)
      (src '(1)))
    (if (= count 0)
 src
 (loop (- count 1) (calc 0 src '())))))

これでいける？

gosh> (f 0)
(1)
gosh> (f 1)
(1 1)
gosh> (f 2)
(1 2 1)
gosh> (f 3)
(1 3 3 1)
gosh> (f 4)
(1 4 6 4 1)
gosh> (f 5)
(1 5 10 10 5 1)
gosh> (f 6)
(1 6 15 20 15 6 1)
gosh> 

できた。

で、ブログに書いてて気づいたが、俺の解答は再帰的プロセスじゃなくて反復（末尾再帰）か？
てか、そもそもリスト使ったやり方って、問題の意図をくんでいるかどうかかなり怪しい気がしてきた。

他の人の解答を見てみよっと。

－