一週間間が空いたせいでペースがつかめなくなってしまって SICP に手を伸ばすまでにものすごく時間がかかるようになってしまいました。
ここで辞めてしまうと本当にやらなくなっちゃうのでちょいと踏ん張り所です。一日一問でも進めて徐々にペースを戻さないと。
問題解答
問2.42
とっかかりが掴めない。というか、どういうデータ構造で格納されるのか?が想像つかない。
しかたがないので empty-board をカンニング。
(define empty-board '())
ん?これでいいのか?
クィーンの置く場所を数値として表すらしい。 サンプルだと (3 7 2 8 5 1 4 6) となるということか。
それを踏まえて元のコードをじっと眺める。
。。。だがダメ。ダメ。全く頭が動かない。一週間空くとここまでダメなのか(もともとダメという話は無かったことに)。
仕方ないから全部カンニングしてきちんと把握することにします。
(define (flatmap proc seq)
(accumulate append '() (map proc seq)))
map で作成したリストを展開する
seq に (1 2) のような値が入力され、各値に proc を施すことで
((1 1) (2 2)) のようなリストのリストになる場合、リストに変換する。
この場合は (1 1 2 2) になる。
(define (adjoin-position new-row k rest-of-queens)
(cons new-row rest-of-queens))
既存のクィーンの並びに新しいクィーン new-row を加える
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
初期値を initial として、返り値に対して sequence の各値を op で処理していく。sequence が (1 2 3) だった場合、(op 1 (op 2 (op 3 initial))) という処理になる。
(define (enumerate-interval low high)
(if (> low high)
'()
(cons low (enumerate-interval (+ low 1) high))))
low から high まで値を数え上げ、リストにして返す
(define (filter predicate sequence)
(cond ((null? sequence) '())
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
predicate で評価されて true になるもののリストを返す
(define (safe? k positions)
(define (safe1 x n)
(or (= n k)
(let ((y (list-ref positions n)))
(and (not (= x y))
(not (= (- x y) n))
(not (= (- y x) n))
(safe1 x (+ n 1))))))
(safe1 (car positions) 1))
list-ref なる未知の関数が使われている。Gauche のマニュアルを見ると
listのk番目の要素を返します。
ということのようで。これ、もっと早めに教えてよっ!!(涙。
LISP の文法関係は、SICP だけじゃ足りないのか、、、、
ということで、safe1 では一番頭にある値とそれ以降の値を比較して許容できる配置かどうかをチェックしている。
(not (= x y) ; 同じ行にクィーンが配置されていないか
(not (= (- x y) n)) ; 斜め方向にクィーンが配置されていないか
(not (= (- y x) n)) ; 斜め方向にクィーンが配置されていないか
(safe1 x (+ n 1)))))) ; 次のアイテムをチェック
(define empty-board '())
空のリストを作成
ここまで来て本体の確認をします。
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k 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))
(enumerate-interval 1 board-size) で 1 から board-size までの値を数え上げ。board-size が 3 なら (1 2 3)。
まず、k=1 の場合を考える。 (queen-cols (-k 1)) は (()) になる。
この値を使用して flatmap 内の動作確認。rest-of-queens は (()) から要素が一つづつ取り出されるので、()。
(map (lambda (new-row)
(adjoin-position
new-row
k
rest-of-queens))
(enumerate-interval 1 board-size)))
この部分は (1 2 3) のアイテムに対して adjoin-position を適用したリストを返す。
rest-of-queens は () 、new-row は 1,2,3 が繰り返し毎に入るので結果は
((1) (2) (3))。
flatmap の実態は map なので、まずは map で考える。
(map
(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)))
やっていることは rest-of-queens を取り替えながら map を実行して、その結果をリストにしていることなので (((1) (2) (3)))。
flatmap リストを一つ解除するので ((1) (2) (3))。この、(1),(2),(3) それぞれに対してsafe? で評価して取捨選択するのが filter。結果は ((1) (2) (3))。これが k=1 のときの結果。
k=2 の時は
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position
new-row
2
rest-of-queens))
(enumerate-interval 1 board-size)))
'((1) (2) (3))')
という処理になる(k-1 の時の結果をわかりやすいようにシングルクォーテーションで囲っている)。
rest-of-queens の最初の値は (1) なので、map の結果は ((1 1) (2 1) (3 1))。flatmap 内の map まで処理が終ると
(((1 1) (2 1) (3 1))
((1 2) (2 2) (3 2))
((1 3) (2 3) (3 3)))
になるので、flatmap されて ((1 1) (2 1) (3 1) (1 2) (2 2) (3 2) (1 3) (2 3) (3 3))。
ここから filter されて ((3 1) (1 3)) が残る。以下同様に処理をおこなう。
こんな感じでしょうかね。map がネストすると途端に処理を追いかけられなくなってしまいます。何となく、map の処理が自分の中でキチンとモデル化できていない感じです。
問2.43
外側のループの数が増えるのが原因? flatmap 内で処理がおこなわれる回数は変わらないきがするけれども。。。
→ queens-cols の呼ばれる回数が増えると、その下で再帰される分が増える。
board-size を s とする。
最初の実装だと queens-cols が呼ばれると s 回再帰で呼ばれる。
Louis の実装だと enumerate-interval 毎に s 回呼ばれ、それぞれの中で再帰されていく。
そのため、quessn-cols の呼ばれる回数は
k = s のとき 1
k = s-1 のとき s
k = s-2 のとき s^2
:
:
k = 1 のとき s^(s-1)
これは等比数列なので合計で呼び出される回数は初項 a、公比 r、項数 n で a(r^n-1)/(r-1) から (s^s-1)/(s-1)。
最初のものと比較すると (s^s-1)/(s-1)/s は大体 s^(s-2) 倍処理がおこなわれていることになる。
結局カンニングして何とか流れを追うことができました。でも、自分で一から回答できるかというとできる自信がないですね、、、、
ちょっと気にはなるものの、次に進むことにします。