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的具体化版本(#=<)/2，基于bool01_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.

我们将失去 8 个解决方案中的 7 个，因为partition/4不是单调的！

于 2015-05-05T17:02:20.380 回答