Prolog 写経記 その 10 flatten/2

今日は flatten/2 を写経します．
っていうか，いつも 1 ページ (ほぼ) 丸ごと写経しているのに元ネタの紹介がないのはいかがなものか？
そんなわけで (どんなわけで？)，これを写経しています．

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

書影がないって寂しいなぁ．

解説

flatten(List2, List2) は入れ子になったリスト List1 中の要素を単一レベル (入れ子になっていない) のリスト List2 に組み入れる．

ふむ．

モード

flatten(+, ?)

ふむふむ．

定義

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

flatten([], []).
flatten([X|L], List) :-
	flatten_element(X, Y),
	flatten(L, M),
	conc(Y, M, List), !.

flatten_element(X, [X]) :-
	var(X), !.
flatten_element(X, [X]) :-
	\+ list(X), !.
flatten_element(X, Y) :-
	flatten(X, Y).

うーみゅ，これは手強そうだ．．．
順番に見ていきますか．
flatten/2 には二つの節があります．
最初の節はどうということもないので，まずは 2 番目の節．

flatten([X|L], List) :-
	flatten_element(X, Y),
	flatten(L, M),
	conc(Y, M, List), !.

第一引数で渡されたリストの最初の要素 X をフラットにして，残りの要素 L をフラットにして，それをつないだものが結果ですよ，と．ふむ．これは問題なし．
っていうか，このくらいだと宣言的とか手続き的とかって差を感じませんね．なんか普通．

続いて下請けの述語 flatten_element/2．
説明がないけど，第 1 引数で渡されたものをフラットにして第 2 引数で返してくれるのでしょう．

flatten_element(X, [X]) :-
	var(X), !.

var/1 は Prolog 標準の述語で，写経本によると引数が「未具体化変数」の場合に成功するそうな．
なるほど，昨日写経した list/1 の注記に書かれていたのはこのことですね．未具体化変数は空リストとして list/1 にマッチしちゃうから，それをガードするのがこの節の役割で，だからカットが付いている，と．
で，2番目の節

flatten_element(X, [X]) :-
	\+ list(X), !.

ここでその list/1 を使う，と．
しかし．．．
list/1 の前にある "\+" って？？
写経本の巻末にある「付録 C 標準的 Prolog 組み込み述語」を眺めてみたところ，/+ G というのがありました．スラッシュか．．． バックスラッシュじゃないのか．．．
ともあれ (JW)，参考までに．

/+ G

ゴール G が失敗 (成功) したとき成功 (失敗) する．

ほほー．
ものは試しと思い，2 番目の節を

flatten_element(X, [X]) :-
	/+ list(X), !.

にしてみたところ，文法エラーだと怒られました．もしかしてもしかすると，付録 C の /+ G は \+ G の間違い？
もしそうだとすると，2 番目の節は簡単に説明できます．
X がリストでなければ結果は X を要素とするリストってことです．つじつまが合うなぁ．
要するに，フィジカルネタで愛用していた not/1 と同じ？ 後で確認することにしよう．
そんなわけで (どんなわけで？)，ここでは間違い説を採用して次行きますよ！！

flatten_element(X, Y) :-
	flatten(X, Y).

ここまで来たということは，X はリストに具体化されているということです．間違いない．
そんなわけで (どんなわけで？)，flatten/2 でリストをフラットに展開するというわけですね．

flatten/2 って再帰がダブルですね．リストの要素を一つずつ展開するための再帰と，要素がリストだった場合にそれを (まさに) 再帰的に展開するための再帰．
これを何とも思わずに眺められるのは，フィジカルネタで鍛えられたおかげ？

例

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

2 ?- flatten([a, [[[b]]], [c, [d, []], e]], L).

L = [a, b, c, d, e] ;

No
3 ?- flatten([1, [2, [3]]], [1, 2, 3]).

Yes

ふむ．
これだけじゃアレなんで，ちょっと実験．

4 ?- flatten(L1, L2).

L1 = []
L2 = [] ;

L1 = [_G349]
L2 = [_G349] ;

No

また出たな！！ 謎のアトム！！

次に，flat_element/2 の 2 番目の節を not/1 を使うように書き換えます．

flatten_element(X, [X]) :-
	not(list(X)), !.

そして再び例を写経．

6 ?- flatten([a, [[[b]]], [c, [d, []], e]], L).

L = [a, b, c, d, e] ;

No
28 ?- flatten([1, [2, [3]]], [1, 2, 3]).

Yes

うむ．やはり \+ G は not/1 と同じ意味っぽい．
どっちを使うのが一般的な書き方なのかなぁ？
「Prolog への入門 (isbn:476490165X)」には not/1 は出てくるけど \+ G は見あたらない感じ．うーみゅ．．．

っていうか，やっぱり ISO 標準な Prolog のリファレンスっぽい本を買っておくべきか．

Prolog: The Standard: Reference Manual

あたりか？
あるいは

Programming in Prolog: Using The Iso Standard

だろうか？
っていうか，大人買い発動！！
やってしまった．．． Prolog および Logic Programming な洋書計 10 冊あまり．．．
積むだけなのに．心より恥じる．