在Prolog中将列表在枢轴处分成两个列表

Question

我想将一个列表在轴点P处分成两个列表，如果数字小于P，则放入L1中，如果大于P，则放入L2中。

这是我目前的代码，我能够将列表L分割成形如L1 = [[], []]的形式。但我想将列表分成两个列表L1和L2，我该怎么做？

split(L,P,L1):-
   split(L,P,[],L1).

split([],_,[],[]).
split([],_,X,[X]) :- X \= [].
split([P|T],P,[],L1) :- split(T,P,[],L1).
split([P|T],P,L,[L|L1]) :- L \= [], split(T,P,[],L1).
split([H|T],P,S,L1) :- H \= P, append(S, [H], S2), split(T,P,S2,L1).

- user8866063

---

你应该看一下 partition/4。 - joel76

Answer 1

您只需要遵循三个规则来实现这个谓词：

:- use_module(library(clpfd)).

split([], _, [], []).
split([H|T], P, L1, [H|T2]) :-
    H #>= P,
    split(T, P, L1, T2).
split([H|T], P, [H|T1], L2) :-
    H #< P,
    split(T, P, T1, L2).

这段代码相当简单易懂。

请注意，由于使用了library(clpfd)，因此该谓词也可以在初始列表和枢轴未知时正常工作：

?- split(L,P,[5,47],[101]).
L = [101, 5, 47],
P in 48..101 ;
L = [5, 101, 47],
P in 48..101 ;
L = [5, 47, 101],
P in 48..101 ;
false.

使用 partition/4

正如评论中提到的，您可以使用partition/4来完成这个操作：

split(L, P, L1, L2) :-
    partition(zcompare(>,P), L, L1, L2).

然而，这种实现不会展示出像第一个实现那样多样的行为。

- Fatalize

---

使用partition/4与[tag:clpfd]结合在许多非ground查询中会给出逻辑上不正确的答案。为什么不使用(>)/2或者更好的是在library(reif)中使用tpartition/4呢？ - repeat

有没有可能不使用任何库或内置谓词来完成它？ - user8866063

@ScrappyMontana，只需删除库调用并将#>=替换为>=，将#<替换为<即可。但是您将失去一些理想的行为。 - Fatalize

@Fatalize 如果不使用该库，会失去哪些理想的行为？ - user8866063

@ScrappyMontana 这将对你想要的功能起作用，但当第一个参数未知时则无法使用。 - Fatalize