SICP 問題 2.36（アキュムレータの拡張）

Scheme SICP

問題

手続き accumulate-n は第3引数として全てが同数の要素からなる並びの並びをとる他は accumulate と同じである。
これはアキュムレーションとして指定した手続きを、並びの全ての第１要素、全ての第2要素と言う風に作用させ、結果の並びを返す。
例えば s が4つの並びを含む並び ((1 2 3) (4 5 6) (7 8 9) (10 11 12)）だとすると、
(accumulate-n + 0 s) の値は並び (22 26 30) になる。
次の accumulate-n の定義の欠けた式を補え。

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init <??>)
	    (accumulate-n op init <??>))))

解答

まずは、問題文で定義されている歯抜けの accumulate-n が何をしようとしているか考えてみよう。

(define (accumulate-n op init seqs)
  ;受け取った seqs の先頭要素が 空リストかどうかチェック
  (if (null? (car seqs))
      ;空リストだった場合はそのまま空リストを返却
      '()
      ;空リストでなかった場合は、
      ;「何か」を accumulate した結果と、
      ;「何か」を accumulate-n した結果を
      ;連結する。
      (cons (accumulate op init <??>)
	    (accumulate-n op init <??>))))

う〜むわからん。。
問題文の実行してみた結果をもう一度考えてみよう。



(accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

(22 26 30)
こんな感じになるわけだ。
これは・・・また正規順序の展開してみないと分からないかなぁ。


いやいや、それは以前やってるんだから今回は正規順序展開しなくても分かるための訓練という位置づけにしなければ！

とりあえず、cons は最終的に (22 26 30) を形成するロジックになるはず。
なので、(accumulate op init ) は、22 を返すような式であるべきか？
そうすると、(accumulate-n op init ) は既に (26 30) を形成していなければならないわけだ。

そうなるには、どのようなデータ変換の過程をイメージすればよいか。。

あ！ accumulate の には、((1 2 3) (4 5 6) (7 8 9) (10 11 12)）内の各リストの先頭を抽出するリストを map 使って返せばいいんでない！？

ちょっと実験。引数として ((1 2 3) (4 5 6) (7 8 9) (10 11 12)）を受け取り、(1 4 7 10) を返すような map 式を作ってみる。
こんな感じか？

(map (lambda (x)
       (car x))
     '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

実験。



gosh> (map (lambda (x)

	     (car x))

           '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

(1 4 7 10)

gosh>
オッケー！！これを使って accumulate を評価してみよう。

(accumulate + 0 (map (lambda (x)
		       (car x))
		     '((1 2 3) (4 5 6) (7 8 9) (10 11 12))))

実験



gosh> (accumulate + 0 (map (lambda (x)

			     (car x))

			   '((1 2 3) (4 5 6) (7 8 9) (10 11 12))))

22

gosh>
いいね〜！！

ここまで来ると、accumulate-n がイメージできてこないか？
各リストの第2要素以下を返すようなリスト、つまりサンプルデータで言うならば、次のようなリストを返すような式を記述すればいけるだろう。



((2 3) (5 6) (8 9) (11 12)）
こんなリストを返すような式を accumulate-n にわたしてやればいいわけだ。
こんな感じになるかな？

(map (lambda (x)
       (cdr x))
     '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

実験してみよう。



gosh> (map (lambda (x)

	     (cdr x))

           '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

((2 3) (5 6) (8 9) (11 12)）

gosh>
よっしゃ！！これでもうできたようなもんだ！
最終的にはこうなる。

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (map (lambda (x)
				       (car x))
				     seqs))
	    (accumulate-n op init (map (lambda (x)
					 (cdr x))
				       seqs)))))

では実験。



gosh> (accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

(22 26 30)

gosh>
おーけー！！ちょっと開発の仕方というか解き方が分かってきたかも。。