SICP 問題 2.35（アキュムレータを使用して count-leaves を再定義）

Scheme SICP

問題

2.2.2節の count-leaves アキュムレーションとして再定義せよ。

(define (count-leaves t)
  (accumulate <??> <??> (map <??> <??>)))

解答

まずは2.2.2節の count-leaves を再掲しちゃう。

(define (count-leaves x)
  (cond ((null? x) 0)
	((not (pair? x)) 1)
	(else (+ (count-leaves (car x))
		 (count-leaves (cdr x))))))

で、あやふやな記憶を便りにして解いた解答がこれ。

(define (count-leaves tree)
  (accumulate (lambda (element count)
		(cond ((null? element) count)
		      ((not (pair? element) ) (+ 1 count) )
		      (else
		       (+ (count-leaves element) count))))
	      0
	      tree))

埋め込むパターンが違かった。。これも一応正しく動作するんだけどね。
じゃ、改めて解くか。

(define (count-leaves t)
  (accumulate <??> <??> (map <??> <??>)))

このパターンだと、lambda式、初期化値、入力データをそれぞれ指定しなきゃならなくて、かつ入力データは map を使って何かに変換してやる必要があるみたい。一体何に変換するんだ？？
tree 内のあらゆる深さの全要素を全部トップレベルの要素にするのかな。
そうするには map をどう記述すればいいか。。

(map (lambda (x)
       (if (pair? x)
	   (自分 x)
	   x))
     '(1 (2 (3 4) 5) (6 7)))

あ、分かったかも。↑この定義は考え方のヒントになっただけで、解き方としては「tree 内のあらゆる深さの全要素を全部トップレベルの要素にする」って方針は多分間違ってた。
accumulate はあくまでもトップレベルの要素に対してのみ作用させ、map で変換するモノは、各要素が自身の中に持っている要素数だ。
例えば、入力データとして次のデータをサンプルとして考えると、正規順序的？に展開した場合に次のような変化をたどればいいと思う。

(hoge (fuga (moga uga) funga) (ora muda))

(hoge (fuga (1    1  ) funga) (ora muda))

(hoge (1    2          1    ) (1   1   ))

(1    4                       2         )

7

アトムだったら 1 を返し、リストだったらその中の要素は全て数値化されているはずなので、それらの数の合計値を返す感じ。
というわけで、まずは map を使って全アトムを 1 に変換するような手続きを定義してみよう。
こんな感じか？

(define (test tree)
  (map (lambda (x)
	 (if (pair? x)
	     (test x)
	     1))
       tree))

では実験。



gosh> (test '(hoge (fuga (moga uga) funga) (ora muda)))

(1 (1 (1 1) 1) (1 1))

gosh>
いいねぇ〜♪
方針は合ってるので、あとはtestを再帰呼び出ししている箇所を、count-leaves にすればOKだな。

(define (count-leaves t)
  (accumulate <??>
	      <??>
	      (map (lambda (x)
		     (if (pair? x)
			 ;ここを test から count-leavesに変える。
			 (count-leaves x) 
			 1))
		   tree)))

あとはもう初期化値と各要素の加算だけだ。
それぞれ + と 0 かな。つーわけで最終的な結果はこんな感じ。

(define (count-leaves tree)
  (accumulate +
	      0
	      (map (lambda (x)
		     (if (pair? x)
			 (count-leaves x) 
			 1))
		   tree)))


こ・・・これは・・・シンプルで美しい・・・。
そっか〜。このセクションではデータをフィルタする、っていうのも重要な概念だったな。
それを処理側である accumulate の第1引数で指定する手続きでやっちゃダメよということだったのね。
今わかったわ。


さて、では実験。



gosh> (count-leaves '(hoge (fuga (moga uga) funga) (ora muda)))

7

gosh> (count-leaves '(((nippon sou shin tou) niha (ki tai) shite iru) (ga uchi no (senkyo ku) kara ha (dare) mo (shutsu ba) shinai no darou ka)))

24

gosh>
できた〜♪