3

P-99: Ninety-Nine Prolog Problems の問題 9 への回答を返すのに問題があります。

リスト要素の連続した複製をサブリストにパックします。リストに繰り返し要素が含まれる場合、それらは別々のサブリストに配置する必要があります。

期待される結果を含むクエリの例:

?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].

サブリストに要素を詰め込むことができましたが、答えを返す方法がわかりません。

これが私のコードです：

pack(X,Y) :- pack(X,[],Y).
pack([H,H|T],Acc,X) :- pack([H|T],[H|Acc],X).
pack([H,H1|T], Acc, X) :- 
    H\=H1, 
    Acc1=[H|Acc],
    append(X, [Acc1], X1),
    pack([H1|T],[],X1).
pack([H], Acc, X) :- 
    Acc1=[H|Acc],
    append(X, [Acc1], X1).

トレース モードで実行されるクエリを次に示します。

?- trace, pack([a,a,a,a,b,c,c],X).
   Call: (6) pack([a, a, a, a, b, c, c], _G986) ? creep
   Call: (7) pack([a, a, a, a, b, c, c], [], _G986) ? creep
   Call: (8) pack([a, a, a, b, c, c], [a], _G986) ? creep
   Call: (9) pack([a, a, b, c, c], [a, a], _G986) ? creep
   Call: (10) pack([a, b, c, c], [a, a, a], _G986) ? creep
   Call: (11) a\=b ? creep
   Exit: (11) a\=b ? creep
   Call: (11) _G1100=[a, a, a, a] ? creep
   Exit: (11) [a, a, a, a]=[a, a, a, a] ? creep
   Call: (11) lists:append(_G986, [[a, a, a, a]], _G1105) ? creep
   Exit: (11) lists:append([], [[a, a, a, a]], [[a, a, a, a]]) ? creep
   Call: (11) pack([b, c, c], [], [[a, a, a, a]]) ? creep
   Call: (12) b\=c ? creep
   Exit: (12) b\=c ? creep
   Call: (12) _G1109=[b] ? creep
   Exit: (12) [b]=[b] ? creep
   Call: (12) lists:append([[a, a, a, a]], [[b]], _G1114) ? creep
   Exit: (12) lists:append([[a, a, a, a]], [[b]], [[a, a, a, a], [b]]) ? creep
   Call: (12) pack([c, c], [], [[a, a, a, a], [b]]) ? creep
   Call: (13) pack([c], [c], [[a, a, a, a], [b]]) ? creep
   Call: (14) _G1127=[c, c] ? creep
   Exit: (14) [c, c]=[c, c] ? creep
   Call: (14) lists:append([[a, a, a, a], [b]], [[c, c]], _G1132) ? creep
   Exit: (14) lists:append([[a, a, a, a], [b]], [[c, c]], [[a, a, a, a], [b], [c, c]]) ? creep
   Exit: (13) pack([c], [c], [[a, a, a, a], [b]]) ? creep
   Exit: (12) pack([c, c], [], [[a, a, a, a], [b]]) ? creep
   Exit: (11) pack([b, c, c], [], [[a, a, a, a]]) ? creep
   Exit: (10) pack([a, b, c, c], [a, a, a], []) ? creep
   Exit: (9) pack([a, a, b, c, c], [a, a], []) ? creep
   Exit: (8) pack([a, a, a, b, c, c], [a], []) ? creep
   Exit: (7) pack([a, a, a, a, b, c, c], [], []) ? creep
   Exit: (6) pack([a, a, a, a, b, c, c], []) ? creep
X = [] .

結果を何らかの方法で入力にバインドするために、最後のルールの最後に追加の行が必要だと思いますが、その方法がわかりません。

4

7 に答える 7

2

論理的に純粋な方法でそれを行う方法は次のとおりです。メタ述語を、 の具体化されたバリアントとsplitlistIfAdj/3組み合わせて使用​​します。さっそくクエリを実行してみましょう。dif/3

?- Xs = [a], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a ],
Pss = [[a]].                                    % succeeds deterministically

?- Xs = [a,a,a,a,b,c,c], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a,a,a,a,  b,  c,c ],
Pss = [[a,a,a,a],[b],[c,c]].                    % succeeds deterministically

?- Xs = [a,a,a,a,b,c,c,a,a,d,e,e,e,e], splitlistIfAdj(dif,Xs,Pss).
Xs  = [ a,a,a,a,  b,  c,c,  a,a,  d,  e,e,e,e ],
Pss = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]].% succeeds deterministically

不純なコードとは異なり、実装は単調であり、根拠のない用語で使用できます。

?- Xs = [A,B], splitlistIfAdj(dif,Xs,Pss), A=1 , B=2 .
Xs = [1,2]、A = 1、B = 2、Pss = [[1]、[2]]。

?- Xs = [A,B], A=1 , B=2 , splitlistIfAdj(dif,Xs,Pss). % 論理的に同等
Xs = [1,2]、A = 1、B = 2、Pss = [[1]、[2]]。

次のようなより一般的なクエリでも、論理的に正しい答えが得られることに注意してください。

?- Xs = [A,B,C,D], splitlistIfAdj(dif,Xs,Pss).
Xs = [D,D,D,D], Pss = [[D,D,D,D]],           A=B ,     B=C ,     C=D  ;
Xs = [C,C,C,D], Pss = [[C,C,C],[D]],         A=B ,     B=C , dif(C,D) ;
Xs = [B,B,D,D], Pss = [[B,B],[D,D]],         A=B , dif(B,C),     C=D  ;
Xs = [B,B,C,D], Pss = [[B,B],[C],[D]],       A=B , dif(B,C), dif(C,D) ;
Xs = [A,D,D,D], Pss = [[A],[D,D,D]],     dif(A,B),     B=C ,     C=D  ;
Xs = [A,C,C,D], Pss = [[A],[C,C],[D]],   dif(A,B),     B=C , dif(C,D) ;
Xs = [A,B,D,D], Pss = [[A],[B],[D,D]],   dif(A,B), dif(B,C),     C=D  ;
Xs = [A,B,C,D], Pss = [[A],[B],[C],[D]], dif(A,B), dif(B,C), dif(C,D).
于 2015-05-05T11:43:24.463 に答える
2

コードを機能させるために必要な最小限の変更は次のとおりです。「戻り値のみ」変数を追加して、内部作業追加からの結果をトップレベルに「出現」させます。

pack(X,Y) :- pack(X,[],_,Y).
pack([H,H|T],Acc,X,R) :- pack([H|T],[H|Acc],X,R).

pack([H,H1|T], Acc, X,R) :-
    H\=H1,
    Acc1=[H|Acc],
    append(X, [Acc1], X1),
    pack([H1|T],[],X1,R).

pack([H], Acc, X,R) :-
    Acc1=[H|Acc],
    append(X, [Acc1], X1),
    R = X1.

テスト：

?- pack([a,a,a,a,b,c,c],X).
X = [[a, a, a, a], [b], [c, c]] .

あなたが見たように、利用可能な代替アルゴリズムがたくさんあります: これが私のものです。

pack(L, P) :- pack(L, [], P).

pack([X|Xs], R, P) :-
    add_pack(X, R, R1), pack(Xs, R1, P).
pack([], R, P) :-
    reverse(R, P).

add_pack(X, [[X|Xs]|R], [[X,X|Xs]|R]).
add_pack(X, [R|Rs], [[X],R|Rs]).
add_pack(X, [], [[X]]).

その動作は「単純な挿入ソート」に最も似ています。先頭要素を取得して、適切な場所に配置します。要素の追加を避けるために、アキュムレータを使用して、最後に逆にします（ここでの他のほとんどの回答と同様）。

編集他の回答を読んで、他の誰か (私のような人) があなたのコードを理解するのが難しいと思ったと思います。原因は、「入力/出力」引数が混在している可能性があります。文体上の選択として、プロロガーは通常、「最初に入力し、最後に出力する」ことに固執します。これは常に意味があるとは限りません (結局のところ、Prolog は関係に関するものであり、関数ではありません) が、多くの場合、従うべき便利で単純なテクニックです。

HTH

于 2013-09-18T08:13:09.407 に答える
1

module(library(lambda)) と foldl で SWI-Prolog を使用する場合は、次のように記述できます。

:- use_module(library(lambda)).

pack(L, PL) :-
L = [A | B],
foldl(\X^Y^Z^(Y = [LY | RY],
          (   member(X, LY)
          ->  Z = [[X | LY]|RY]
          ;   Z = [[X]| [LY | RY]])),
      B, [[A]], RPL),
reverse(RPL, PL).

モジュール lambda.pl はそこにあります: http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl

于 2013-09-18T07:36:22.890 に答える