SICP 読み (231) 4.3.3 amb 評価器の実装

帰りのバスで問題 4.51 をニラむ。set! な失敗継続ってどうなるんだろ、と思いつつ an-element-of って手続きは何か、と。全然見覚えが無くてページを遡ってみたら最初らへんで定義を発見。その下で定義されている a-integer-starting-from という手続きをみてびっくり。これって 8queen で使えるじゃんか、と。
ちなみにこれから自分のエントリでどう解決しているかを確認します。
解は以下な模様 (一部のみ

(define (enumerate-seq n)
  (define (enum-seq-iter seq)
    (if (> seq n)
	'()
	(cons seq
	      (enum-seq-iter (+ seq 1)))))
  (enum-seq-iter 1))

(define (n-queens board-size)
  (define (n-queens-iter n ret)
    (cond ((> n board-size) ret)
	  (else
	   (let ((l (append ret (list (list-amb (enumerate-seq board-size))))))
	     (require (distinct? l))
	     (require (safe? n l))
	     (n-queens-iter (+ n 1) l)))))
  (n-queens-iter 1 '()))

(define (list-amb l)
  (if (null? l)
      (amb)
      (amb (car l)
	   (list-amb (cdr l)))))

よく見ると a-integer-starting-from は使えんな。an-element-of を使うとすると解は以下か。

(define (n-queens board-size)
  (define (n-queens-iter n ret)
    (cond ((> n board-size) ret)
	  (else
	   (let ((l (append ret 
			    (list (an-element-of 
				   (enumerate-seq board-size))))))
	     (require (distinct? l))
	     (require (safe? n l))
	     (n-queens-iter (+ n 1) l)))))
  (n-queens-iter 1 '()))

うーむ。一応遅いが動いている模様。

;;; Amb-Eval input:
(n-queens 8)

;;; Starting a new problem 
;;; Amb-Eval value:
(1 5 8 6 3 7 2 4)

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
(1 6 8 3 7 4 2 5)

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
(1 7 4 6 8 2 5 3)

;;; Amb-Eval input:

なんでこんなに読んでないんだ、というか忘れるんだ。(何

問題 4.50

確認中です。ちなみにダウト発見。

(define (analyze-ramb exp)
  (let ((cprocs (map analyze (amb-choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
	(if (null? choices)
	    (fail)
	    (let ((n (mt-random-integer m (length choices))))
	      ((list-ref choices n) 
	       env
	       succeed
	       (lambda () (try-next (remainder choices n)))))))
      (try-next cprocs))))

じゃねぇと駄目っぽい。(length choices) が 0 の場合、mt-random-integer が微妙な模様。がしかし、まだ微妙なニオイがします。
えーと、末端がランダムなだけなんですがこれって良いのでしょうか。仕方無いのかなぁ。ちょっと gdgd っぽい感じなんで別途確認ってコトでご勘弁下さひ。(何