12

[0, 0, 0, 1, 2, 0, 3] のように、先頭にゼロの数が不明なリストがあります。[1, 2, 0 , 3] のように見えるように、このリストから先頭のゼロを削除する必要があります。

ここに私が持っているものがあります:

lead([Head | _], _) :- Head =\= 0.
lead([0 | Tail], _) :- 
  lead(Tail, Tail).

その出力は単純に True です。トレースを読み取ると、先行ゼロのないリストができるまで実行されていることが示されますが、その後、回答はスタックに反映されません。私はPrologにかなり慣れていないので、それを行う方法がわかりません。

4

6 に答える 6

11

これは、すべての方向で機能するソリューションです。

lead([],[]).
lead([H|T],[H|T]) :-
    dif(H,0).
lead([0|T],T2) :-
    lead(T,T2).

いくつかのクエリ:

?- lead([0,0,0,1,2,0,3], L).
L = [1, 2, 0, 3] ;
false.


?- lead(L, []).
L = [] ;
L = [0] ;
L = [0, 0] ;
L = [0, 0, 0] ;
...


?- lead(L0, L).
L0 = L, L = [] ;
L0 = L, L = [_G489|_G490],
dif(_G489, 0) ;
L0 = [0],
L = [] ;
L0 = [0, _G495|_G496],
L = [_G495|_G496],
dif(_G495, 0) ;
L0 = [0, 0],
L = [] ;
L0 = [0, 0, _G501|_G502],
L = [_G501|_G502],
dif(_G501, 0) ;
L0 = [0, 0, 0],
L = [] ;
...

編集この述語は実際には機能しませんlead(L0, [0,1,2])。

于 2016-10-01T08:29:40.370 に答える
9

ライブラリ（reif）を使用：

:- use_module(reif).

remove_leading_zeros([], []).
remove_leading_zeros([H|T], Rest) :-
        if_(    H = 0,
                remove_leading_zeros(T, Rest),
                Rest = [H|T]).

それで：

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

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

?- remove_leading_zeros(L, R).
L = R, R = [] ;
L = [0],
R = [] ;
L = [0, 0],
R = [] ;
L = [0, 0, 0],
R = [] . % and so on
于 2016-10-03T15:45:00.093 に答える
6

これは、可能なすべての入力に対して実際に機能し、不要な選択ポイントを残さないソリューションです。

lead(L0, L) :-
    (   nonvar(L),
        L = [H|_] ->
        dif(H,0)
        ;
        true
    ),
    lead_(L0, L).

lead_([], []).
lead_([H|T], L) :-
    if_(H \= 0,
        L = [H|T],
        lead_(T,L)).

の最初のチェックは、他のすべての状況で述語の動作を保持しながら、nonvar(L)たとえば の問題を防ぐために私が思いついた唯一の解決策です。lead(L0, [0,1,2,3])

これはif_/3、の一部を使用しますlibrary(reif)

if_(If_1, Then_0, Else_0) :-
    call(If_1, T),
    (  T == true -> Then_0
    ;  T == false -> Else_0
    ;  nonvar(T) -> throw(error(type_error(boolean,T),
                                type_error(call(If_1,T),2,boolean,T)))
    ;  throw(error(instantiation_error,instantiation_error(call(If_1,T),2)))
    ).

これも、 in を簡単に変更して思いついた を使用して(\=)/3います。(=)/3library(reif)

\=(X, Y, T) :-
    (   X \= Y -> T = true
    ;   X == Y -> T = false
    ;   T = true, dif(X, Y)
    ;   T = false,
        X = Y
    ).

いくつかのクエリ

?- lead([0,0,0,1,2,0,3],L).              % No choice point
L = [1, 2, 0, 3].


?- lead([1,2,0,3],L).
L = [1, 2, 0, 3].


?- lead([0,0,0,0],L).
L = [].


?- lead([],L).
L = [].


?- lead(L0,[0,1,2,0,3]).                 % Correctly fails
false.


?- lead(L0,[1,2,0,3]).
L0 = [1, 2, 0, 3] ;
L0 = [0, 1, 2, 0, 3] ;
L0 = [0, 0, 1, 2, 0, 3] ;
…


?- lead(L0,L).                           % Exhaustively enumerates all cases:  
L0 = L, L = [] ;                         %   - LO empty
L0 = L, L = [_G2611|_G2612],             %   - L0 contains no leading 0
dif(_G2611, 0) ;
L0 = [0],                                %   - L0 = [0]
L = [] ;
L0 = [0, _G2629|_G2630],                 %   - L0 contains one leading 0
L = [_G2629|_G2630],
dif(_G2629, 0) ;
L0 = [0, 0],                             %   - L0 = [0, 0]
L = [] ;
L0 = [0, 0, _G2647|_G2648],              %   - L0 contains two leading 0s
L = [_G2647|_G2648],
dif(_G2647, 0) ;
…                                        %   etc.
于 2016-10-04T07:20:10.533 に答える
5

これは、選択ポイントを生成しないソリューションです。dif/2 では想定されていない方法で、freeze/2 を使用しています。しかし、freeze/2 の 1 つの経験則は次のとおりであるため、ここで freeze/2 を使用することは非常に適切です。

freeze/2 の経験則:述語がインスタンス化されていないソリューションと多くの選択ポイントを生成する場合は、freeze/2 を使用します。後続の目標が解決策をさらに特定し、freeze/2 が起こされることを期待しています。残念ながら、CLP(FD) や dif/2 では動作しません。freeze/2 は CLP(FD) または dif/2 によって暗示された改良に反応しないため、統合のみがそれを起こします。

したがって、コードは次のとおりです。

lead(X, Y) :- var(X), !, freeze(X, lead(X,Y)).
lead([X|Y], Z) :- var(X), !, freeze(X, lead([X|Y],Z)).
lead([0|X], Y) :- !, lead(X, Y).
lead(X, X).

以下にいくつかの実行例を示します (インポートなしのSWI-Prolog 、Jekejeke Prolog はMinlog 拡張機能と ?- use_module(library(term/suspend)) を使用):

?- lead([0,0,0,1,2,3], X).
X = [1, 2, 3].

?- lead([0,0|X], Y).
freeze(X, lead(X, Y)).

?- lead([0,0|X], Y), X = [0,1,2,3].
X = [0, 1, 2, 3],
Y = [1, 2, 3].

?- lead([Z,0|X], Y), X = [0,1,2,3].
X = [0, 1, 2, 3],
freeze(Z, lead([Z, 0, 0, 1, 2, 3], Y)).

?- lead([Z,0|X], Y), X = [0,1,2,3], Z = 0.
Z = 0,
X = [0, 1, 2, 3],
Y = [1, 2, 3].

上記の Lead/2 実装では、最初の引数のみが処理されます。複数の引数を同時に処理するには、述語 when/2 を使用できます。ただし、簡単にするために、ここでは示していません。

また、中断されたゴールを使用する場合、中断されたゴールはそれらの間の矛盾を検出できないため、最後に述語のようなラベル付けが必要になる場合があります。

于 2016-10-02T21:49:10.627 に答える
2

これが私がそれを表現する方法です。まず、制約を確立します。X または Y のいずれかをリストにバインドする必要があります。それ以外は失敗します。

  • X が束縛されている場合、Y は気にしません。束縛されていても束縛されていなくてもかまいません。X から先頭のゼロをすべて取り除き、結果を Y と統合するだけです。このパスには、可能な解が 1 つあります。

  • X が束縛されておらず、Y が束縛されている場合、生成モードに移行します。このパスには無限の数の可能なソリューションがあります。

コード：

strip_leading_zeros(X,Y) :- listish(X), !, rmv0( X , Y ) .
strip_leading_zeros(X,Y) :- listish(Y), !, add0( Y , X ) .

rmv0( []     , [] ) .
rmv0( [D|Ds] , R  ) :- D \= 0 -> R = [D|Ds] ; rmv0(Ds,R) .

add0( X , X ) .
add0( X , Y ) :- add0([0|X],Y ) .

listish/1listish-ness の単純な浅いテストです。is_list/1物事について衒学的になりたい場合に使用します。

listish( L     ) :- var(L), !, fail.
listish( []    ) .
listish( [_|_] ) .

注記:リスト全体is_list/1をトラバースして、テストが適切に構築されたリスト、つまり、右側の子自体が別の用語またはアトム(空のリストを示す) のいずれかである用語であることを確認します。リストが長い場合、これはコストのかかる操作になる可能性があります。./2./2[]

したがって、次のようなもの[a,b,c]は適切なリストであり、実際にはこの用語です: .(a,.(b,.(c,[])))。のようなもの[a,b|32]は適切なリストではありません。それは用語.(a,.(b,32))です。

于 2016-10-05T00:50:47.970 に答える