7

Prolog で、整数のリストを正の整数のリストと負の整数のリストに分割する述語を作成しようとしています。

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

?- split([1,-2,3,4,-8],X,Y).
X = [1,3,4],
Y = [-2,-8].

これは私がこれまでに得たコードです:

split([], [], []).
split([Head|Tail], List1, List2) :- split(Tail, [Head|List1], List2), Head>=0.
split([Head|Tail], List1, List2) :- split(Tail, List1, [Head|List2]), Head<0.

私は自分が間違っていることを理解できないようです。

4

4 に答える 4

9

再帰部分は完全に正しくありません。

split([], [], []).
split([Head|Tail], [Head|List1], List2) :- Head>=0, split(Tail, List1, List2).
split([Head|Tail], List1, [Head|List2]) :- Head<0, split(Tail, List1, List2).

のHead場合はポジティブ リストに追加し、 の場合Head >= 0はネガティブ リストに追加する必要がありますHead < 0。

さらに、不要な再帰呼び出しを防ぐためHead 、最初にの符号を確認することをお勧めします。

于 2012-03-03T15:15:24.850 に答える
6

SWI-Prolog では、述語partition/4(通常はapplyモジュールから自動ロードされます)を使用できます。

?- partition(=<(0), [1,-2,3,4,-8,0], X, Y).
X = [1, 3, 4, 0],
Y = [-2, -8].
于 2012-03-03T15:39:00.100 に答える
3

制約を使用した定義を次に示します。この場合、それはlibrary(clpfd)SWI と YAP (おそらく XSB) のものです。このライブラリは非常に一般的であるため、通常の整数の使用が含まれます。

:- use_module(library(clpfd)).

具体化の使用:

split([], [], []).
split([E|Es], Poss, Negs) :-
   E #>= 0 #<==> B,
   i_split(B, E, Es, Poss, Negs).

i_split(1, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
i_split(0, E, Es, Poss, [E|Negs]) :-
   split(Es, Poss, Negs).

または、 を使用することもできますzcompare/3。私はそのバージョンを好みます:

split([], [], []).
split([E|Es], Poss, Negs) :-
   zcompare(Order, E, 0),
   c_split(Order, E, Es, Poss, Negs).

c_split(>, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
c_split(=, E, Es, [E|Poss], Negs) :-
   split(Es, Poss, Negs).
c_split(<, E, Es, Poss, [E|Negs]) :-
   split(Es, Poss, Negs).

通常のクエリにも、次のようなより一般的なクエリにも使用できます。

?- split(Es,[A],[]).
Es = [A],
A in 1..sup ;
Es = [0],
A = 0 ;
false.
于 2012-03-03T18:45:22.693 に答える
2

論理的に純粋で効率的であること。どのように？メタ述語tpartition/4と(#=<)/3!

まず、に基づいての具体化された(#=<)/3バージョンである を定義しましょう。完全を期すために、 、、およびも定義しましょう。(#=<)/2bool01_t/2
(#<)/3(#>)/3(#>=)/3

#=<(X,Y,Truth) :- X #=< Y #<==> B, bool01_t(B,Truth).

#<( X,Y,Truth) :- X #<  Y #<==> B, bool01_t(B,Truth).

#>( X,Y,Truth) :- X #>  Y #<==> B, bool01_t(B,Truth).

#>=(X,Y,Truth) :- X #>= Y #<==> B, bool01_t(B,Truth).

それでおしまい！それでは、OP が必要とする分割を行いましょう。

?- tpartition(#=<(0),[1,-2,3,4,-8,0],Ts,Fs).
Ts = [1,3,4,0], Fs = [-2,-8].                   % succeeds deterministically

これは単調なので、一般的で根拠のない用語を使用しても適切な答えが得られます。

?- tpartition(#=<(0),[A,B,C],Ts,Fs).
Ts = [     ], Fs = [A,B,C], A in inf.. -1, B in inf.. -1, C in inf.. -1 ;
Ts = [    C], Fs = [A,B  ], A in inf.. -1, B in inf.. -1, C in   0..sup ;
Ts = [  B  ], Fs = [A,  C], A in inf.. -1, B in   0..sup, C in inf.. -1 ;
Ts = [  B,C], Fs = [A    ], A in inf.. -1, B in   0..sup, C in   0..sup ;
Ts = [A    ], Fs = [  B,C], A in   0..sup, B in inf.. -1, C in inf.. -1 ;
Ts = [A,  C], Fs = [  B  ], A in   0..sup, B in inf.. -1, C in   0..sup ;
Ts = [A,B  ], Fs = [    C], A in   0..sup, B in   0..sup, C in inf.. -1 ;
Ts = [A,B,C], Fs = [     ], A in   0..sup, B in   0..sup, C in   0..sup .

編集 2015-06-02

partition/4上記のクエリでSWI-Prolog ライブラリの述語を使用するとどうなるでしょうか。

?- partition(#=<(0),[A,B,C],Ts,Fs).
Ts = [A,B,C], Fs = [], A in 0..sup, B in 0..sup, C in 0..sup.

partition/4単調ではないため、8 つのソリューションのうち 7 つを失うことになります。

于 2015-05-05T17:02:20.380 に答える