1. ホーム
  2. list

[解決済み] Prologでリストを平坦にする

2022-02-16 01:56:01

質問

Prologを使い始めてまだ数日しか経っていません。 いくつかのことは理解していますが、これは本当に私を混乱させるものです。

リストを受け取って平坦化する関数を書けということですね。

?- flatten([a,[b,c],[[d],[],[e]]],Xs).  
Xs = [a,b,c,d,e].                           % expected result

この関数は,リストの内部構造を取り出します.

今のところ、こんな感じです。

flatten2([],[]).
flatten2([Atom|ListTail],[Atom|RetList]) :-
      atom(Atom), flatten2(ListTail,RetList).
flatten2([List|ListTail],RetList) :-
      flatten2(List,RetList).

さて、これで電話をかけると動作するようになりました。

?- flatten2([a,[b,c],[[d],[],[e]]], R).
R = [a,b,c,d,e].                         % works as expected!

しかし、入力したリストがすでにフラット化されているかどうかを確認するために呼び出すと、次のような結果が返されます。 false ではなく true :

?- flatten2([a,[b,c],[[d],[],[e]]], [a,b,c,d,e]).
false.                                   % BAD result!

なぜ片方ではうまくいくのにもう片方ではうまくいかないのでしょうか? 何かとても単純なことを見逃しているような気がするのですが。

解決方法は?

の定義は flatten2/2 のような挙動をします。

?- flatten2([a, [b,c], [[d],[],[e]]], R).
R = [a, b, c] ;
false. 

ということは、すでに R[a,b,c,d,e] ということであれば、失敗しても不思議ではありません。

あなたの定義は、リストの末尾を捨てている( ListTail を経由して返すリストに接続する必要があります。 RetList . 以下はその提案である。

flatten2([], []) :- !.
flatten2([L|Ls], FlatL) :-
    !,
    flatten2(L, NewL),
    flatten2(Ls, NewLs),
    append(NewL, NewLs, FlatL).
flatten2(L, [L]).

これは、すべてのリストのリストを再帰的に単一アイテムリストに変換するものです。 [x] または空のリスト [] を捨てます。そして、それらを蓄積し、再び1つのリストに追加して出力します。

ほとんどのPrologの実装では、空のリストである [] はアトム の呼び出しはリストなので atom([])is_list([]) は両方ともtrueと評価されます。これは、文字アトムとは対照的に、空のリストを捨てるのには役立ちません。