Prolog，列表中元素 Y 之前的 X 元素[重复]

Question

我将编写谓词，当且仅当且仅当元素

X

出现在列表

Y

上的

L

之前时才为真

before(L, X, Y) :-
    nth1(PX, L, X),
    nth1(PY, L, Y),
    PX < PY.  

在上面，你可以看到我的解决方案。你对此有何看法？

说到我的具体问题：
当至少存在一对

Y

跟随

X

时，我的谓词返回 true。 如何定义谓词使其对于每一对都为真？

Answer 1

您展示的解决方案适用于“如果存在”的情况，但本质上是必要的。也就是说，它有点像翻译成 Prolog 的 C 程序。命令式意味着您使用编程语言告诉计算机要执行哪些步骤才能实现您的结果。

为了更具声明性或关系性，您的“存在”解决方案可以很好地表达为 DCG：

... --> [].
... --> [_], ... .

before(X, Y) --> ... , [X], ... , [Y], ... .

（注意：您可以在 Prolog 中拥有一个名为

...

的谓词，如下所示。）这描述了列表中

X

和

Y

的关系。它不描述执行的步骤，而是描述

X

和

Y

在序列中的关系。该解决方案已在 之前在 SO 上展示过。

按照这种方法（我们描述

X

和

Y

的关系），表达所有

X

在所有

Y

之前的一种方法（不一定是唯一的方法）将是：

before_all(X, Y) -->
    { dif(X,Y) },
    any_sequence_but(Y), [X], any_sequence_but(Y), [Y], any_sequence_but(X).

any_sequence_but(_) --> [].
any_sequence_but(Y) --> [X], { dif(X,Y) }, any_sequence_but(Y).

这会产生这样的解决方案：

?- phrase(before_all(X,Y), [b,a,b,c,a,b,d]).
X = b,
Y = d ;
X = a,
Y = d ;
X = b,
Y = d ;
X = c,
Y = d ;
X = a,
Y = d ;
X = b,
Y = d ;
false.

?-

Answer 2

如果条件应适用于 all 对，则该条件应至少适用于一对，而相反的情况不应适用于 any 对。

我冒昧地将你的

before/3

重命名为

beforeSome/3

。

beforeSome(L, X, Y) :-
    nth1(PX, L, X),
    nth1(PY, L, Y),
    PX < PY.
    
beforeAll(L, X, Y) :-
    beforeSome(X,Y),
    not(beforeSome(L, Y, X)).

这会产生预期的结果：

?- beforeAll([1,2,3,1,4,5], 1, 4).
true.
    
?- beforeAll([1,2,3,1,4,5], 1, 2).
false.

---

请注意，您使用

nth1/3

会阻止将其与未实例化的变量一起使用。换句话说，

beforeAll([1,2,3,1,4,5], X, Y).

是

false

。

更好的实现

beforeSome/3

会是这样的

beforeSome([X|T], X, Y) :-
    member(Y, T).
    
beforeSome([_|T], X, Y) :-
    beforeSome(T, X, Y).
    
% no change needed, but repeated here for sake of completeness
beforeAll(L, X, Y) :-
    beforeSome(X,Y),
    not(beforeSome(L, Y, X)).