将一个整数列表分成正整数列表和负整数列表

Question

我一直在尝试在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.

我似乎无法弄清我错在哪里。

- Martin

---

如果输入列表包含零，应该发生什么？ - Kaarel

它应该放在正整数列表中。 - Martin

Answer 1

递归部分不太正确。

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 >= 0，则应将 Head 添加到正列表中；如果 Head < 0，则应将其添加到负列表中。

此外，在 开始时 检查 Head 的符号更好，因为它可以防止不必要的递归调用。

- Sufian Latif

---

非常感谢！感谢您解释了优化。 - Martin

@MizaCoroda 使用 trace 来理解递归 :) - Sufian Latif

@FlopCode：你的解决方案很好，但在当前的Prolog实现中，它会消耗与非负元素数量成比例的额外辅助空间。最好在这里使用compare/3。 - false

你能否请说明一下所给解答的推导树？那将是一个很大的帮助。 - Samitha Chathuranga

Answer 2

在SWI-Prolog中，您可以使用谓词partition/4（通常从apply模块自动加载）：

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

- Kaarel

---

SWI-Prolog的partition/4谓词不是内建谓词。它是在apply模块中定义的库谓词（最有可能被自动加载）。 - Paulo Moura

@PauloMoura 谢谢，已修复。 - Kaarel

Answer 3

这里是一个使用约束条件的定义。在这种情况下，它是 SWI 和 YAP（也许还有 XSB）的 library(clpfd)。这个库非常通用，可以涵盖常规整数使用。

:- 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.

- false

Answer 4

保持逻辑纯粹和高效，如何做到？通过使用元谓词tpartition/4和(#=<)/3！首先，让我们定义(#=<)/3，它是基于bool01_t/2的(#=<)/2的具象化版本。
为了完整起见，让我们也定义(#<)/3，(#>)/3和(#>=)/3！请注意保留HTML标签。

#=<(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年6月2日

如果我们在上述查询中使用SWI-Prolog库谓词partition/4会怎样呢？

?- 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不是单调的！

- repeat

---

#=<(X, Y, Truth) :- X #=< Y #<==> B, ( B = 0, Truth = false ; B = 1, Truth = true ).（假设B = 0; B = 1有索引） - false

tpartition/4用于替代partitionlist/4吗？ - false

@false。当然，为什么不呢？顺便问一下，tfilter中的“t”实际上代表什么？-） - repeat