Aizu SICP 第 16 ~ 19 回
10/6 に第 16 回、 10/18 に第 17 回、 11/17 に第 18 回、 12/6 に第 19 回を行った。各回が短かめだったのと、18 日は過去の問題に関して改めて議論して終わった (この分は 15 回の記事に書いた) ので、新しくやった分は少なかったこともありまとめました。
P 121 2.2.3 標準インターフェイスとしての列 ~ P123 列の演算 終わりまでと、その後の 練習問題 2.33 ~ 2.39 までです。
2.2.3 標準インターフェイスとしての列
ここでは主に、プログラムを列に対する演算の連鎖として表現することによる利点が述べられている。列に対する処理の連鎖というのは関数型プログラミングをするにあたっての基本となる操作であると思うので、この辺りを読み、実際のプログラミングを通して確認しながら他のプログラミング手法と比較して実際のところどうなのかを考えたい。
プログラミングをしているとまず最初にオブジェクト指向的な書き方が頭に浮かび、それを関数型的に書き直すということがよくある。これは単にこれまでのプログラミングの習慣によって起こることなのか、それとも実はオブジェクト指向的な書き方の方が人間の脳に優しいということが (もしかしたら) あるのかもしれない、など考えている。この辺りは今後考えていくとして、ここではまず関数型プログラミングの手法の利点についてしっかりと理解しておきたい。
ひとまず言えることは、関数型プログラミングをサポートしているとしている言語では、それを援助する様々な汎用的で高速化されている関数や機能 (例えば遅延評価など) が提供されているので、そういったものを使えるように言語にあったプログラミングするべきだろう。
信号の流れという構造が⼿続きの中で明確に⾒て取れるようにプログラムを構成できれば、結果となるコードの概念的な明確さを⾼めることができるでしょう。
(Page 123).
列の演算
プログラムを列の演算として表すことの利点は、モジュール化された形でのプログラムの設計がやりやすくなるということにあります。モジュール化とは、⽐較的独⽴した部品を組み⽴ててプログラムを構築する設計のことです。標準コンポーネントのライブラリとともに、コンポーネントを柔軟に接続できる標準インターフェイスを提供することで、モジュール化された設計を促すことができます。モジュールによる設計は、⼯学の設計において複雑性をコントロールする強⼒な戦略です。例えば、実際の信号処理の応⽤では、標準化されたフィルタや変換器から要素を選び、それを直列につなぐことによってシステムを構築するということを、設計者は⽇常的に⾏っています。同じように、列の演算は⾃由に組み合わせられる標準的なプログラムの要素のライブラリを提供します。
(Page 126).
練習問題 2.33
これ以降の問題では accumulate が右結合であることに注意する。右結合であるというのは、例えば (accumulate + 0 '(1 2 3)) というのは (+ 1 (+ 2 (+ 3 0))) というように展開さることを意味する。また初期値は列の一番右端に配置される。中置記法の場合 1 + 2 + 3 + 4 が 1 + (2 + (3 + 4)) となることを指して右結合と呼ぶが、これと同じことを意味する。
以下では Gauche で使われている名前であるため関数名に my- を付けた。
(define (my-map p sequence) (accumulate (lambda (x y) (cons (p x) y)) nil sequence)) (test-section "ex 2.33") (test* "my-map1" '(2 4 6) (my-map (^[x] (* x 2)) '(1 2 3))) (test* "my-map1" '(1 1 1) (my-map (^[x] 1) '(3 9 28))) (define (my-append seq1 seq2) (accumulate cons seq2 seq1)) (test* "my-append1" '(1 2 3 4 5 6) (my-append '(1 2 3) '(4 5 6))) (test* "my-append2" '(1 2 3) (my-append nil '(1 2 3))) (test* "my-append3" '(1 2 3) (my-append '(1 2 3) nil)) (define (my-length sequence) (accumulate (^[x y] (+ 1 y)) 0 sequence)) (test* "my-length1" 3 (my-length '(1 2 3))) (test* "my-length2" 0 (my-length nil)) (test* "my-length3" 5 (my-length '(3 6 9 12 15)))
練習問題 2.34
数式は のように
の添字は
から始まるが、入力は
からなので注意する。
(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* higher-terms x))) 0 coefficient-sequence))
練習問題 2.35
count-leaves を集積として再定義せよという問題だが、map の使い方におうじて解答がいろいろ出た。
;; 私 ;; P125 で実装されている enumerate-tree を使った (define (count-leaves-acc t) (accumulate + 0 (map (^[x] 1) (enumerate-tree t)))) (test-section "ex 2.35") (test* "count-leaves1" 4 (count-leaves-acc (cons (list 1 2) (list 3 4)))) (test* "count-leaves2" 8 (count-leaves-acc (list (cons (list 1 2) (list 3 4)) (cons (list 1 2) (list 3 4))))) ;; @sux2mfgj (define (depth l) (if (null? l) 0 (if (number? l) 1 (+ (depth (car l)) (depth (cdr l)))))) (define (count-leaves-acc t) (accumulate + 0 (map depth t))) (test* "count-leaves1" 4 (count-leaves-acc (cons (list 1 2) (list 3 4)))) (test* "count-leaves2" 8 (count-leaves-acc (list (cons (list 1 2) (list 3 4)) (test* "count-leaves3" 14 (count-leaves-acc (list (list (list 1 2) (list 1 2) (list 1 2) (list 1 2)) (list 1 2) (list 1 2) (list 1 2))))
あとで気が付いたが下の例は depth という関数が既に count-leaves の役割を果たしてしまっていた。
gosh> (test* "count-leaves3" 14 (depth (list (list (list 1 2) (list 1 2) (list 1 2) (list 1 2)) (list 1 2) (list 1 2) (list 1 2)))) test count-leaves3, expects 14 ==> ok #<undef>
練習問題 2.36
(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init (map car seqs)) (accumulate-n op init (map cdr seqs))))) (test* "accumulate-n" '(22 26 30) (accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12))))
各列の先頭を取り出し、それに対して accumulate をしていき結果でリストを構築する。
練習問題 2.37
それぞれ、ひとつ前で定義した手続きを使ってうまく使えるようになっている。
(define (dot-product v w) (accumulate + 0 (map * v w))) (test-section "ex 2.37") (test* "dot-product" 26 (dot-product '(1 2 3) '(3 4 5))) (define (matrix-*-vector m v) (map (^[mc] (dot-product mc v)) m)) (test* "matrix-*-vector" '(14 32 50) (matrix-*-vector '((1 2 3) (4 5 6) (7 8 9)) '(1 2 3))) (define (transpose mat) (accumulate-n cons nil mat)) (test* "transpose" '((1 4 7) (2 5 8) (3 6 9)) (transpose '((1 2 3) (4 5 6) (7 8 9)))) (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map (^[mc] (matrix-*-vector cols mc)) m))) (test* "matrix-*-matrix" '((9 12) (24 33)) (matrix-*-matrix '((1 2) (4 5)) '((1 2) (4 5))))
練習問題 2.38
前述した通り accumulate は右結合であるので fold-right と呼ばれる。 Gauche では fold-left と fold-right という手続きが実装されているので Haskell にならって foldl, foldr とした。
(define (foldl op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence)) (define foldr accumulate) (test-section "ex 2.37") (test* "foldr1" 3/2 (foldr / 1 (list 1 2 3))) (test* "foldl1" 1/6 (foldl / 1 (list 1 2 3))) ;; '(1 (2 (3 nil))) (test* "foldr2" (list 1 (list 2 (list 3 nil))) (foldr list nil (list 1 2 3))) ;; '(((nil 1) 2) 3) (test* "foldl2" (list (list (list nil 1) 2) 3) (foldl list nil (list 1 2 3)))
また Gauche では fold という手続きも実装されている。fold-left は左結合かつ初期値と畳み込まれていく値が二項演算の第一項 (左側) だが、fold は第二項 (右側) になる。
gosh> (foldl cons '() '(1 2 3)) (((() . 1) . 2) . 3) ;; (cons (cons (cons '() 1) 2) 3) gosh> (fold cons '() '(1 2 3)) (3 2 1) ;; (cons 3 (cons 2 (cons 1 '()))) gosh> (fold-right cons '() '(1 2 3)) (1 2 3) ;; (cons 1 (cons 2 (cons 3 '())))
fold-right と fold-left が任意の列に対して同じ値を返すこと を保証するために、op が満たさなければならない性質を答えよ。
(Page 130).
op は交換法則を満す必要がある。
練習問題 2.39
結合法則と初期値の位置を意識すること。
(define (reverse-r sequence) (foldr (lambda (x y) (append y (list x))) nil sequence)) (define (reverse-l sequence) (foldl (lambda (x y) (cons y x)) nil sequence)) (test-section "ex 2.38") (test* "reverse-r" '(3 2 1) (reverse-r '(1 2 3))) (test* "reverse-l" '(3 2 1) (reverse-l '(1 2 3)))