27

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!

一方では機能するのに、他方では機能しないのはなぜですか? 非常に単純なものが欠けているように感じます。

4

7 に答える 7

25

flatten2/2あなたが与えた定義は破られています。実際には次のように動作します。

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

Rしたがって、すでに にバインドしている場合を考える[a,b,c,d,e]と、失敗は驚くべきことではありません。

あなたの定義はListTail、3 番目の節でリスト () の末尾を破棄していRetListます。ここに提案があります：

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

これは、リストのすべてのリストを再帰的に 1 つの項目リスト[x]、または破棄する空のリストに減らします[]。次に、それらすべてを蓄積して、出力から 1 つのリストに追加します。

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

于 2012-01-30T05:39:41.833 に答える
8

開始点へのポインターと、終了点に到達したときにインスタンス化できる「終了ホール/フリーポインター」 (つまり、logvar)の両方を使用して、リストを無制限に維持できます。

flatten2( [], Z, Z):- !.                                        % ---> X
flatten2( [Atom|ListTail], [Atom|X], Z) :-                      %      .
    \+is_list(Atom), !,                                         %      .
    flatten2( ListTail, X, Z).                                  %      Y
flatten2( [List|ListTail], X, Z) :-                             %      .
    flatten2( List,     X, Y),       % from X to Y, and then    %      .
    flatten2( ListTail, Y, Z).       % from Y to Z              %      Z --->

次に、それを次のように呼び出します

flatten2( A, B):- flatten2( A, B, []).

reverseそうすれば、どこでも使用する必要はありません。この手法は「差分リスト」として知られていますが、代わりに「制限のないリスト」と考える方がはるかに簡単です。

更新:これは、構文を使用してコーディングする方がはるかに簡単です。単方向なので (最初の引数は完全に接地する必要があります)、結局のところ、カットを使用しない理由は次のとおりです。

flattn([]) --> [], !.
flattn([A|T]) --> {\+is_list(A)}, [A], !, flattn(T).
flattn([A|T]) --> flattn(A), flattn(T).

テスト:

16 ?- phrase(flattn([a,[b,c],[[d],[],[e]]]), [a, b, c, d, e]).
true.

17 ?- phrase(flattn([a,[b,c],[[d],[],[e]]]), R).
R = [a, b, c, d, e].

18 ?- phrase(flattn([a,[b,X],[[d],[],[e]]]), [a, b, c, d, e]).
X = c.

X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ...定義が完全に宣言的である場合、最後のものは;でも成功するはずです。残念ながら、そうではありません。

( edit2 : @ matのコメントのおかげで、両方のバージョンを単純化しました!)

于 2012-01-30T18:57:08.157 に答える
2

完全を期すために、アキュムレータベースのバージョンを次に示します。

% flatten/2
flatten(List, Result) :- flatten(List, [], Result).

% auxiliary predicate flatten/3
flatten([], Result, Result).
flatten([Head| Tail], Part, Result) :- 
    is_list(Head),
    !, 
    flatten(Head, HR),
    append(Part, HR, PR),
    flatten(Tail, PR, Result).
flatten([Head| Tail], Part, Result) :- 
    append(Part, [Head], PR),
    flatten(Tail, PR, Result).
flatten(X, Part, Result) :-
    fail.
于 2014-10-10T11:06:47.000 に答える
1

と に基づいif_//3て、次のようにlist_truth/2実装できます。myflatten/2

myflatten(Xs,Ys) :-
   phrase(myflatten_aux(Xs),Ys).

myflatten_aux([]) --> [].
myflatten_aux([T|Ts]) --> 
   if_(neither_nil_nor_cons_t(T), [T], myflatten_aux(T)),
   myflatten_aux(Ts).

:- use_module(library(dialect/sicstus/block)).

:- block neither_nil_nor_cons(-).
neither_nil_nor_cons(X) :-
   \+nil_or_cons(X).

nil_or_cons([]).
nil_or_cons([_|_]).

neither_nil_nor_cons_t(X,Truth) :-
   (  nonvar(X)
   -> (  neither_nil_nor_cons(X) -> Truth = true
      ;                             Truth = false
      )
   ;  nonvar(Truth) 
   -> (  Truth == true -> neither_nil_nor_cons(X)
      ;  Truth == false,  nil_or_cons(X)
      )
   ;  Truth = true,  neither_nil_nor_cons(X)
   ;  Truth = false, nil_or_cons(X)
   ).

サンプルクエリ（他の回答から取得したもの、および回答へのコメント）：

?- myflatten([[4],[[5,6],[7,[8],[9,[10,11]]]]], Xs).
Xs = [4, 5, 6, 7, 8, 9, 10, 11].

?- myflatten([1,[8,3],[3,[5,6],2],8], Xs).
Xs = [1, 8, 3, 3, 5, 6, 2, 8].

?- myflatten([a,[b,c],[],[[[d]]]], Xs).
Xs = [a, b, c, d].

?- myflatten([a,[b,c],[[d],[],[e]]], Xs).
Xs = [a, b, c, d, e].

neither_nil_nor_cons_tとnot(nil_or_cons_t)describe の解は同じですが、解の順序が異なります。検討：

?- myflatten([A,B,C],Xs), A=a,B=b,C=c.
A = a,
B = b,
C = c,
Xs = [a, b, c] ;                       % does not terminate universally
于 2015-06-13T23:02:42.157 に答える
1

Prolog のリスト表記は、非常に単純な Prolog 用語の上に構文糖衣を加えたものです。プロローグ リストは次のように示されます。

  1. 空のリストはアトムで表され[]ます。なんで？それは空のリストの数学表記のように見えるからです。nil空のリストを示すためにアトムのようなものを使用できたかもしれませんが、そうしませんでした。

  2. 空でないリストは項.\2で表されます。ここで、最初 (左端) の引数はリストの先頭で、2 番目 (右端) の引数はリストの末尾であり、再帰的にそれ自体がリストです。

いくつかの例：

  • 空のリスト:[]はアトムとして表されます。

    []

  • 1 つの要素のリストは、[a]内部的に次のように格納されます。

    .(a,[])

  • 2 つの要素のリスト[a,b]は、内部的に次のように格納されます。

    .(a,.(b,[]))

  • 3 つの要素のリストは、次の[a,b,c]ように内部的に保存されます。

    .(a,.(b,.(c,[])))

同様に、リストの先頭の検査は、同じ表記法に対する構文糖衣です。

  • [X|Xs]と同じです.(X,Xs)

  • [A,B|Xs]と同じです.(A,.(B,Xs))

  • [A,B]は (上記を参照) と同じです.(A,.(B,[]))

私自身、私は次flatten/2のように書きます：

%------------------------
% public : flatten a list
%------------------------
flatten( X , R ) :-
  flatten( X , [] , T ) ,
  reverse( T , R )
  .

%--------------------------------------------
% private : flatten a list into reverse order
%--------------------------------------------
flatten( [] , R , R ) .        % the empty list signals the end of recursion
flatten( [X|Xs] , T , R ) :-   % anything else is flattened by
  flatten_head( X , T , T1 ) , % - flattening the head, and
  flatten( Xs , T1 , R )       % - flattening the tail
  .                            %

%-------------------------------------
% private : flatten the head of a list
%-------------------------------------
flatten_head( X , T , [X|T] ) :- % if the head is a not a list
  \+ list(X) ,                   % - simply prepend it to the accumulator.
  ! .                            %
flatten_head( X , T , R     ) :- % if the head is a list
  flatten( X , T , R )           % - recurse down and flatten it.
  .

%-----------------------
% what's a list, anyway?
%-----------------------
list( X ) :- var(X) , ! , fail .
list( []    ) .
list( [_|_] ) .
于 2012-01-30T18:45:15.547 に答える
0

を使用した解決策が見つからなかったfindallので、追加します。（リストが地面の場合は機能します）

まず、リストをテストする方法を定義します。

list(X) :- var(X), !, fail.
list([]).
list([_|_]).

と の推移閉包をmemberと呼びますmember*:

'member*'(X, Y) :- member(X, Y).
'member*'(X, Y) :- member(Z, Y), 'member*'(X, Z).

フラット化されたリストは、リストmember*ではないすべてのソリューションです。

flatten(X, Y) :- findall(Z, ('member*'(Z, X), \+ list(Z)), Y).

例：

?- flatten([[4],[[5,6],[7,[8],[9,[10,11]]]]],Y).
Y = [4, 5, 6, 7, 8, 9, 10, 11].
于 2015-06-13T15:24:30.470 に答える