2.2.3 公認インターフェースとしての並び(前半)

SICP

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.3
ぼくは、この辺からようやくSICPの面白さ、というか、味がわかって気がします。
それまでは、あんまし目新しいこともなく、どちらかと言うとマゾ性を出さないと乗り切れなかったのですが、
この章から『何だ関数プログラミングって、データストリームじゃん』と言う正しいのか間違っているのかよくわからないself definitionに目覚めました。
とにもかくにも、結構考え方を変えてくれた節です。


と言うことで、問題を解いて行きまする。

問題 2.33

コレって、最初のmap関数が一番むずいよね？
op関数が2引数の関数で、xにはcarした値が、yにはcdrリストをaccumulateした結果(リスト)が、と言うのがわかるとすぐだと思うんだけど。
append, lengthは楽ちん。

(define (map-seq p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))
(define (append-seq seq1 seq2)
  (accumulate cons seq2 seq1))
(define (length-seq sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))
問題 2.34

コレもthis-coeffとhiger-termsが何かがわかれば簡単(ていうか、名前から明らかだけど)。

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higer-terms) 
  			  (+ (* higer-terms x)
			        this-coeff))
			  0
			 coefficient-sequence))
問題2.35

この問題は迷った。とりあえず、最初にフラットなリストにしてやって、数を数えればいんでしょう、と言うことで

  • map使わない版
(define (count-leaves t)
  (accumulate (lambda (x y) (+ 1 y))
			  0 
			  (enumerate-tree t)))

を作ったら、mapを使えとかって。。。

  • map使う版
(define (count-leaves t)
  (accumulate + 0 (map (lambda (x) (if (pair? x) (count-leaves x) 1)) t)))

余計、めんどくさい。

問題2.36

この関数いいね。実際にも使うよね。何だけど、Rubyとかでは、普通にリスト同士の足し算とかでできるもんなぁ。

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

(map car seqs)で先頭要素だけを取り出したリストを作ってやって、それに対してaccumulateを適用する。
何かこの関数好きかも。

問題 2.37

コレはめんど〜なだけ。

(define (matrix-*-vector m v)
  (map (lambda (w) (dot-product w v))
	   m))
  • Transpose
(define (transpose mat)
  (accumulate-n cons '() mat))

ここに、accumulate-n関数を使ってる。各列の先頭要素を取り出してやって、リストにしちゃえば行要素になるよね。

  • Matrix * Matrix
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
	(map (lambda (row)
		   (map (lambda (col)
			     (dot-product row col))
			     cols))
		  m)))
問題2.38
(fold-right / 1 (list 1 2 3))
=> (/ 1 (/ 2 (/ 3 1)))

(fold-left / 1 (list 1 2 3))
=> (/ (/ (/ 1 1) 2) 3)

(fold-right list '() (list 1 2 3))
=> (list 1 (list 2 (list 3 '())))

(fold-left list '() (list 1 2 3))
=> (list (list (list '() 1) 2) 3)

fold-leftとfold-rightがどのような並びに対しても同じ値を生じるためには、opが交換可能な演算子じゃないとだめ、と言うことだよね。

問題2.39
  • fold-left版
(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x))
			 '()
			 sequence))
=> (/ (/ (/ 1 1) 2) 3)
=> (op (op (op init 1) 2) 3)
=> (op 3 (op 2 (op 1 init)))
=> (cons 3 (cons 2 (cons 1 '())))

ぼくみたいな頭かた〜な人間には思考プロセスをちゃんとダンプしておくことが重要だと思うので、少し載せてみた。

  1. 前の問題から展開された式をパクってくる。
  2. 演算子と初期値を書いてみる。
  3. リストを逆にするので、x(生成リスト)とy(即値)を逆にしてみた。
  4. op->cons, init->'()にすると反転リストが生成。

と言うことで、(cons y x)すればいい、と言う結論に。

  • fold-right版
(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x)))
			 '()
		　　  sequence))
=> (/ 1 (/ 2 (/ 3 1)))
=> (op 1 (op 2 (op 3 init)))
=> (op (op (op init 3) 2) 1)
=> (append (append (append '() (list 3)) (list 2)) (list 1))

こちらも同様に(こっちの方がめんどくさいけど)、

  1. 前の問題から展開された式をパクってくる。
  2. 演算子と初期値を書いてみる。
  3. リストを逆にするので、x(即値)とy(生成リスト)を逆にしてみた。
  4. op->append, init->'(), x->(list x)にすると反転リストが生成。

と言うことで、(append y (list x))すればいい、と言う結論に。

ちゃんと思考プロセスを残しておくのは重要、と言うのが、問題2.32から得られたぼくの教訓です。
(コードを見て、すぐわかるほど頭がよくないので。)