yukimiの成長記

■[SICP] 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って言うの同種な文字なので、見間違いやすいよね〜。この辺も教科書のレベルから変えてほしいのだが。

Permalink | コメント(0) | 13:56