Prolog 写経記 その 84 findall/3

(ほぼ) 毎日淡々と Prolog を写経します．元ネタはこちら．

Prologユーティリティライブラリ

今日は findall/3 を写経します．
「9 章 標準述語の導入」へ突入です．

解説

findall(X, G, List) は List を，ゴール G を満足させるすべての X のリストに具体化する．

「標準述語の導入」というくらいなので，当然 SWI-Prolog にも存在する述語です．
たいていの解説書にも出てきます．
でもでも，この述語きらーい．

モード

findall(?, +, -)

久しぶりに ? を見た気がする〜．

定義

では，こいつの定義を写経しませう．

findall2(X, G, _) :-
	asserta(item(no_more)),
	call(G),
	asserta(item(X)),
	fail.
findall2(_, _, List) :-
	collect_item([], L), !,
	List = L.

collect_item(S, L) :-
	next_item(X), !,
	collect_item([X | S], L).
	collect_item(L, L).

next_item(X) :-
	retract(item(X)), !,
	X \== no_more.

標準の述語とかぶるので，名前は findall2 にしちゃいました．
さて，久しぶりに見応えあるっぽいですね．．．

まずは本体から．
いきなり最初の節が怪しい．

findall2(X, G, _) :-
	asserta(item(no_more)),
	call(G),
	asserta(item(X)),
	fail.

asserta/1 は Prolog データベースに述語を登録する述語．
それを使って，item(no_more) という述語 (事実) をデータベースに登録しています．初期化みたいなものかな？
そして引数で渡されたゴール G を実行します．
ゴール G が成功すれば次の assert/1 でその時の X がデータベースの先頭に登録されます．
そして fail/0 で強制失敗．
これがゴール G にマッチする X がなくなるまで繰り返されます．
そしてゴール G にマッチする X がなくなると，この節は失敗に終わります．
つ・ま・り
この節は成功裡に終わることがないわけね．かわいそうに．．．

そんなわけで (どんなわけで？)，2 番目の節へ．

findall2(_, _, List) :-
	collect_item([], L), !,
	List = L.

下請けの collect_item/2 でリストを作成して返します．

その collect_item/2．

collect_item(S, L) :-
	next_item(X), !,
	collect_item([X | S], L).
collect_item(L, L).

さらに下請けの述語 next_item/1 で X を探して，それを第 1 引数のリストに追加しています．
それを X が見つからなくなるまで再帰的に繰り返し，と．

んで，最後．

next_item(X) :-
	retract(item(X)), !,
	X \== no_more.

retract/1 は引数にマッチした述語を Prolog データベースから削除します．
その際に，X が具体化されます．それが no_more でなければ成功となり，呼び出し元に持って帰ります．
X が no_more の場合は失敗となります．これはデータベースの一番下にあるはずなので，これが出てきたら終わり．

そんなわけで (どんなわけで？)，Prolog データベースという書き換え可能なグローバル変数を活用しているというか乱用しているというかとにかくそういう述語です．
こうやって見てみると，やっぱり好きになれそうもないなぁ．
だってだって，すごく卑怯っぽいし手続きっぽいんだもの．

注意

付録 C にある組み込み述語 findall/3，bagof/3 と setof/3 の解説を参照のこと．

らじゃあ，読みますた．

例

では使用例を写経しませう．

2 ?- assert(student(john)),

    

    
    assert(student(mary)),
    
    

    
    assert(student(bob)),
    
    

    
    findall2(X, student(X), List).
    
X = _G782
List = [john, mary, bob] 

Yes

ふむ．
こういう課題を findall/3 を使わずに解くとすると．．．
うーみゅ，再帰しながらリストを集合のように使うくらいしか思いつかないなぁ．
効率悪そう．．．

---