2.2.3 公認インターフェースとしての並び(後半)
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.3
後半は、入れ子になっているデータ構造をConventional Interfaceで扱うにはどうするか、と言うお話。
お役に立つflatmapもあるので、合わせて憶えておこう。
(define (flatmap proc seq) (accumulate append '() (map proc seq)))
問題2.40
これは簡単。直前の例題から、リストを作る部分を抜き出すだけ。
(define (unique-pairs n) (flatmap (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n))) (define (prime-sum-pairs n) (map make-pair-sum (filter prime-sum? (unique-pairs n))))
問題2.41
これも簡単。3重ループでデータを作ってやって、それをフィルタに噛ませれば終了。
(define (unique-three-pairs n) (flatmap (lambda (i) (flatmap (lambda (j) (map (lambda (k) (list i j k)) (enumerate-interval 1 j))) (enumerate-interval 1 i))) (enumerate-interval 1 n))) (define (is-equal-three-pairs n s) (filter (lambda (pair) (let ((sum (+ (car pair) (cadr pair) (caddr pair)))) (= sum s))) (unique-three-pairs n)))
問題2.42
エイトクイーン問題。こういうの苦手なんだけど、実は難しく考える必要ないんだなぁ、と最近実感中。
悩んだら、ここを読もう。
http://d.hatena.ne.jp/tkuro/20091019/1255912771
あとは、数学ガールの第1巻もおすすめ。
漸化式の形式にしてやって、もうすでにできているものから、もう一個積み重ねるにはどうすればいいんだ?と言う考えかたでいい。
が、この問題はそもそも全体構造が示されているので、結局、フィルターの部分を書くだけなので、マッチョな人にはつまらない問題だろうなぁ。
; Queen全体 (define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size)) ; 0列までいったときの扱い (define empty-board ()) ; k列目のデータを加えるメソッド (define (adjoin-position row col lst) (cons (list row col) lst)) ; 配置可能かどうかのフィルタ (define (safe? pos) (define (side-exist? row lst) (cond ((null? lst) #t) ((= row (caar lst)) #f) (else (side-exist? row (cdr lst))))) (define (diag-exist? row col lst n) (cond ((null? lst) #t) ((and (= (- row n) (caar lst)) (= (- col n) (cadar lst))) #f) ((and (= (+ row n) (caar lst)) (= (- col n) (cadar lst))) #f) (else (diag-exist? row col (cdr lst) (+ n 1))))) (let ((row (caar pos)) (col (cadar pos)) (res (cdr pos))) (and (side-exist? row res) (diag-exist? row col res 1))))
- 実行例
gosh> (queens 4) (((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))
ま、合ってるっしょ。
問題2.43
queens-colの呼び出しが内側ループか、外側ループかの違い。
内側にすることで、1..7までのqueensを計算し、次に1..6と言うようにムダな計算をしてしまう。
と言うことで、計算を回す場合にはループの内外に注意。
- 余談
最近、2重配列を回す時に、
// (1) for (x = 0; x <= x_max; x++) { for (y = 0; y <= y_max; y++) { data[x][y]; } } // (2) for (y = 0; y <= y_max; y++) { for (x = 0; x <= x_max; x++) { data[x][y]; } }
(2)はなんで遅いの?みたいな話があったが、これはメモリアーキテクチャがデータの局所性を利用してまとめてデータをフェッチするためだと思う。
この辺の感覚って、意外と知らない人が多いのかなぁ、と思いました。
ちなみに、添字でi, jって言うの同種な文字なので、見間違いやすいよね〜。この辺も教科書のレベルから変えてほしいのだが。