Prolog - 查找列表中的相邻元素

Question

我正在尝试定义一个谓词adjacent(X, Y, Zs),如果X和Y在列表中相邻,则该谓词为真.我的代码目前是这样的:

adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
  adjacent(X,Y, Tail).

它适用于基本情况adjacent(c, d, [a, b, c, d, e]),但由于基本情况,每个其他情况也返回true,我坚持这一点.

另一个问题是,如果X不等于列表头部的第一部分,那么它会跳过X和Y并转到下一个'X'; 例如,如果c不等于a,则它跳过a和b两者并检查c是否等于c.例如,当列表是这时,这是有问题的

[a, c, d, e]

因为它最终永远不会检查c(我相信).

我很遗憾如何协调这两个问题,并将我对逻辑的理解转化为代码需要发生的事情.

编辑:感谢Christian Hujer的回答,我的基本情况错误已得到纠正,所以现在我只是坚持第二个问题.

Answer 1

在原始解决方案尝试中:

adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
    adjacent(X,Y, Tail).

正如@ChristianHujer所指出的那样,第一个条款不应该存在,因为它不是真的.空列表应该没有相邻的元素.

第二个条款也存在问题.它显示X并且Y在列表中相邻,但随后递归并且不仅仅是成功.适当的条款应该是:

adjacent(X, Y, [X,Y|_]).

如果它们是列表中的前两个元素,则无论尾部是什么,它都表示X并且Y在列表中相邻.这也形成了一个合适的基础案例.然后你的一般递归条款应该处理其余的情况:

adjacent(X, Y, [_|Tail]) :-
    adjacent(X, Y, Tail).

如果他们相邻,那就说X并且相邻.这样可以解决您遇到的第二个问题.Y[_|Tail]Tail

因此,整个解决方案将是:

adjacent(X, Y, [X,Y|_]).
adjacent(X, Y, [_|Tail]) :-
    adjacent(X, Y, Tail).

这将在列表中以该顺序一次多次成功X并Y一起出现.

这也可以通过DCG自然解决(尽管append/3基于@ repeat的解决方案更简洁):

adjacent(X, Y) --> ..., [X, Y], ... .
... --> [] | [_], ... .

adjacent(X, Y, L) :- phrase(adjacent(X, Y), L).

| ?- adjacent(b, c, [a,b,c,d]).

true ? a

(1 ms) no
| ?- 

Answer 2

我认为你的基本情况是错误的.在您的情况下,您希望递归以假谓词终止,而不是使用真正的谓词.这是合乎逻辑的:在一个空列表中,没有相邻的元素.决不.

Answer 3

在这个答案中,我们试图保持简单 - 建立在append/3:

adjacent(E0, E1, Es) :-
    append(_, [E0,E1|_], Es).

示例查询:

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

Answer 4

辅助谓词adjacent_/5总是"落后"恰好两个(列表项):

adjacent(X0, X1, [E0,E1|Es]) :-
   adjacent_(Es, E0, E1, X0, X1).

adjacent_([],      E0, E1, E0, E1).
adjacent_([E2|Es], E0, E1, X0, X1) :-
   if_(E0+E1 = X0+X1,
       true,
       adjacent_(Es, E1, E2, X0, X1)).

使用SWI-Prolog我们运行:

?- set_prolog_flag(double_quotes, chars).
true.

?- adjacent(a, b, "abab").
true.

?- adjacent(b, c, "abcd").
true. 

?- adjacent(X, Y, "abcd").
   X = a, Y = b
;  X = b, Y = c
;  X = c, Y = d.

编辑

更正的定义也adjacent_/5为以下查询提供了正确的答案:

?- adjacent(X, X, [A,B,C]).
   X = A, A = B
;  X = B, B = C, dif(f(C,C),f(A,A)).

?- adjacent(a, X, "aab").
   X = a
;  X = b.

?- adjacent(a, b, "aab").
true.