为什么Prolog在过滤列表时会找到许多解决方案？

Question

我编写了一个谓词，该谓词过滤了所有6以下的数字的列表，但是prolog找到了多个解决方案。

谓词看起来像这样：

sift([], []).
sift([H | T], [H | Res]):- H > 6,
    sift(T, Res).
sift([_ | T], Res):-
    sift(T, Res).

我问这个：?- sift([1, 7, 2, 13], X).

将导致：

X = [7, 13]
X = [7]
X = [13]
X = []

我只期望X = [7, 13]，所以为什么Prolog会找到所有这些额外答案？

Answer 1

回溯。

当您键入sift([1,10], X).时，Prolog可以对sift([H | T], [H | Res])和sift([_ | T], Res)进行模式匹配。这意味着Prolog离开choicepoint，选择一个选项，然后稍后再返回其他谓词。

序言与第一个谓词sift([7, 2, 13], [H | Res])匹配，进一步调用sift([1, 13], Res)。

但是，它也与第二个谓词sift([_ | [2, 13]], Res)相匹配，稍后将回溯到此谓词，跳过7。

我们可以仅通过过滤掉元素来解决此问题。

sift([], []).
sift([H | T], [H | Res]) :-
    H >= 6,
    sift(T, Res).
sift([H | T], Res) :-
    H < 6,
    sift(T, Res).

这给：

?- sift([1, 7, 2, 13], X).
X = [7, 13] ;
false.

一种替代方法是使用Prolog if：

sift2([], []).
sift2([H | T], [H2 | T2]) :-
    H >= 6 ->
    (H2 = H,
    sift2(T, T2)
    ); sift2(T, [H2 | T2]).

此谓词表示'列出清单和可能的答案。如果第一个元素等于或大于6，则列表的第一个元素和答案应匹配，并且过滤后的尾部应与答案的尾部匹配。否则，列表的尾部需要能够产生整个答案。

这避免了回溯，并且将在第一个之后停止搜索解决方案。

?- sift2([1, 7, 2, 13], X).
X = [7, 13].

[打开trace.来查看两个谓词以进行进一步描述。