3

PROLOG の入れ子になったリストでディープ リバースを生成するための述語を作成しようとしています。

現在、私はこの述語を取得しました

reverse(L,A) :- rev(L,[], A).
rev([],A,A).
rev([H|L],R,A) :- rev(L,[H|R],A).

結果は次のようになります。

reverse([1,2,3],A).
A = [3, 2, 1].

reverse([[0,1],2,3],A).
A = [3, 2, [0, 1]].

問題は、内側の List が反転されていないことです。次のようになります。

reverse([[0,1],2,3],A).
A = [3, 2, [1, 0]].

reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],A).
A = [12,11,[10,9],[8,[7,6],5,4,3],2,1].

助けてくれてありがとう。

4

3 に答える 3

4

データを表現する方法はdefaultyと呼ばれます。これは、推論するときにデフォルトのケースが必要なためです。

  • それはリストですか？→何とかなる
  • そうでなければ→ 別の何かが成り立ちます。

そのような表現は、トラブルの豊富な原因です。たとえばmy_reverse/2、他の回答から考えてみてください。主な問題は、どちらのケースも可能ですが、時期尚早に誤っ ていずれかのケースにコミットすることです。

?- my_reverse([X], Ls).
Ls = [X]。

Xしかし、この答えはリストではない場合にのみ当てはまります! この問題により、次のような述語の奇妙な動作が発生します。

?- my_reverse([X], Ls), X = [1,2,3].
Ls = [[1, 2, 3]],
X = [1、2、3]。

これXは、リストであっても、その要素が逆になっていないことを意味します!

発生する可能性のあるケースを区別するために、常により明確な表現を目指す必要があります。

たとえば、データを表す次の方法についてはどう思いますか。

  • list(Ls)リストを表します Ls
  • n(N)は数 を表しNます。

このような表現により、ケースを象徴的に区別することができます。これを、より宣言的なソリューションの出発点として残します。

于 2016-07-28T09:17:07.623 に答える
1

できるだけ単純にするために、現在チェックされている要素がリストかどうかのテストを追加できます。それが実際にリストである場合、その要素も逆にする必要があります。コードでは：

my_reverse(L,R) :- rev(L,[],R).

rev([],A,A).
rev([H|T],A,R) :-
    ( is_list(H) ->        % If H is a list
      rev(H,[],X),         %   then reverse H as well
      rev(T,[X|A],R)
    ;
      rev(T,[H|A],R)
    ).

また、それは本当に重要なことではなく、混乱を避けるために、AとRをそれぞれAccumulatorとに使用した方法に注意してくださいResult。あなたのコードでは、それらは現在交換されています。これは、特に述語が長く複雑になると、個人的には少し混乱する可能性があります。

とにかく、あなたが提供したクエリを見てみましょう：

?- my_reverse([[0,1],2,3],R).
R = [3, 2, [1, 0]].

?- my_reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],R).
R = [12, 11, [10, 9], [8, [7, 6], 5, 4, 3], 2, 1].

そして、いくつかの一般的なクエリ:

?- my_reverse(L,R).
L = R, R = [] ;
L = R, R = [_G2437] ;
L = [_G2437, _G2443],
R = [_G2443, _G2437] ;
L = [_G2437, _G2443, _G2449],
R = [_G2449, _G2443, _G2437] ;
L = [_G2437, _G2443, _G2449, _G2455],
R = [_G2455, _G2449, _G2443, _G2437] 
...

?- my_reverse([[X,Y]|T],R), member(a,T), length(X,2).
X = [_G2588, _G2591],
T = [a],
R = [a, [Y, [_G2588, _G2591]]]
;
X = [_G2594, _G2597],
T = [a, _G2588],
R = [_G2588, a, [Y, [_G2594, _G2597]]]
;
X = [_G2594, _G2597],
T = [_G2582, a],
R = [a, _G2582, [Y, [_G2594, _G2597]]]
...

ただし、この述語を使用すると、クエリに対する最初の回答が見つかった後に終了が発生しないことに注意してください。

?- my_reverse(X,[X]).
X = [X] ;
...

しかし、これはOPの質問の要件/要求ではなかったので、大丈夫だと思いました.

編集：

この問題のフォローアップとして@mat の回答をお読みください。

于 2016-07-28T07:10:59.990 に答える
0

問題の追加の解決策は、カットと組み込みの述語「is_list/1」を使用して、現在の呼び出しで単純な用語またはリストを扱うかどうかを確認することです。コードは次のとおりです。

deepReverse(List,R):-deepReverseTail(List,[],R).

deepReverseTail([],Acc,Acc).

deepReverseTail([H|T],Acc,R):-             % when H is a list
     is_list(H),                           % check if it's a list.
     !,                                    % cut the process if not. 
     deepReverseTail(H,[],Hrev),           % reverse this current list
     deepReverseTail(T,[Hrev|Acc],R).      % continue the general recursion

deepReverseTail([H|T],Acc,R):- deepReverseTail(T,[H|Acc],R). % when H is a simple term

3行目の「カット」は、この定義ではリストのみを扱い、単純な用語は次の定義で扱うようにしてください。

出力例:

7 ?- deepReverse([a,[d,f],[],[[k],g]],R)
R = [[g, [k]], [], [f, d], a].
于 2018-05-08T11:57:41.247 に答える