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]) 的基本情况，但由于基本情况，所有其他情况 returns 也是正确的，我坚持这一点。

另一个问题是，如果 X 不等于列表头部的第一部分，那么它会跳过 X 和 Y 并转到下一个 'X'；例如，如果 c 不等于 a，那么它会跳过 a 和 b 并检查 c 是否等于 c。这是有问题的，例如，列表是

[a, c, d, e]

因为它最终从不检查 c（我相信）。

我完全不知道如何调和这两个问题并将我对需要发生的事情的逻辑理解转化为代码。

编辑：感谢 Christian Hujer 的回答，我的基本案例错误已得到纠正，所以现在我只停留在第二个问题上。

Answer 1

我认为你的基本情况是错误的。在您的情况下，您希望递归以假谓词而不是真谓词终止。这是合乎逻辑的：在一个空列表中，没有相邻的元素。从来没有。

Answer 2

在这个答案中，我们试图通过构建 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 3

原解尝试中：

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 自然地解决（尽管@repeat 基于 append/3 的解决方案更简洁）：

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 4

辅助谓词adjacent_/5总是"lags behind"恰好有两个（列表项）：

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.

Answer 5

从长远来看，我认为这是一个比@repeat 的解决方案更可取的定义：

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 = X0, E1 = X1 ),
       true,
       adjacent_(Es, E1, E2, X0, X1)).

使用具体化和：

','(A_1, B_1, T) :-
   if_(A_1, call(B_1, T), T = false).

;(A_1, B_1, T) :-
   if_(A_1, T = true, call(B_1, T)).

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

Prolog - Finding adjacent elements in a list

recursion

traversal

list

编辑