EoPL reading (79) 2.2 An Abstraction for Inductive Data Type

lisp と将棋エンジンに取り組んでいるヒトの記事を見た。具体的なアウトプットって良いなぁ。

Exercise 2.10

とりあえず以下をでっち上げてみました。

(add-load-path ".")
(load "define-datatype")

(define all-ids
  (lambda (exp)
    (cases expression exp
           (var-exp (id) (list id))
           (lambda-exp (id body)
                       (append (list id)
			       (all-ids body)))
           (app-exp (rator rand)
                    (append (all-ids rator)
			    (all-ids rand))))))

で、順に試験を追加していきつつ、挫折。

(use gauche.test)

(add-load-path ".")
(load "define-datatype")
(load "expression")
(load "all-ids")

(test-start "all-ids")
(test-section "all-ids")
(test* "all-ids (1)"
       '(w2 w1 w0 w3)
       (all-ids '(app-exp
		  (lambda-exp w2
			      (app-exp (var-exp w1) (var-exp w0)))
		  (var-exp w3))))
(test* "all-ids (2)"
       '(w0)
       (all-ids '(var-exp w0)))
(test* "all-ids (3)"
       '(w2 w0)
       (all-ids '(lambda-exp w2 (var-exp w0))))
(test* "all-ids (4)"
       '(w0 w1)
       (all-ids '(app-exp (lambda-exp w0 (var-exp w0))
			  (var-exp w1))))

(test-end)

最後の試験は (w0 w0 w1) が戻る。戻りに重複があるかどうかを確認してないので当たり前の話。これは繰り返しで書かないとどうにもならんか。
で、試行錯誤の後に以下がでっち上がる。上記試験にはパス。勘違いの痕跡も含め。

(add-load-path ".")
(load "define-datatype")

(define all-ids
  (lambda (exp)
    (let f ((rslt '()) (exp exp))
      (cases expression exp
	     (var-exp (id) (if (memv id rslt)
			       rslt
			       (append rslt (list id))))
;;	     (var-exp (id) (append rslt (list id)))
;;	     (var-exp (id) (list id))
	     (lambda-exp (id body)
			 (f (append rslt (list id)) body))
	     (app-exp (rator rand)
;;		      (f (append rslt (f rslt rator)) rand))))))
		      (f (f rslt rator) rand))))))

で、以下の試験を書きました。

(use gauche.test)

(add-load-path ".")
(load "define-datatype")
(load "expression")
(load "fresh-id")

(test-start "fresh-id")
(test-section "fresh-id")
(test* "fresh-id (1)"
       'w4
       (fresh-id
	(app-exp
	 (lambda-exp 'w2
		     (app-exp (var-exp 'w1) (var-exp 'w0)))
	 (var-exp 'w3))
	"w"))

(test-end)

試験パス、な土曜 1300 昼メシはこれから。