Prolog 递归遍历列表时，如何通过回溯返回多个匹配结果？

2026-11-04数据小陈

问题在于递归调用没有将后续元素的匹配结果传回最外层。最外层的 B、C 与第一个元素统一，分别绑定为 fred、sam；递归调用使用的是另一组变量 K、N。即使深层调用得到不同结果，最外层返回的仍是 B = fred, C = sam。

可以把规则改为两个分支：一个返回匹配的当前列表头，另一个递归查找列表尾。生成的 at(left, X, Y) 可以用 findall/3 收集。

第一次进入非空列表规则时：

H = at(right, X, Y)

这会使当前调用的 X、Y 分别与 fred、sam 统一。它们对应查询中的 B、C。

接下来的递归调用是：

flips(right, K, N, T).

K、N 没有与当前调用的 X、Y 关联。每次调用规则时，规则内部的变量也都是该次调用独立使用的变量。

当列表被消耗完，程序执行：

flips(right, X, Y, []) :-
    at(right, X, Y).

这一层的 X、Y 没有受到列表元素约束，因此两个 at/3 事实都能匹配，产生两条成功路径。回到最外层时，B、C 仍分别为 fred、sam，所以出现重复答案。

原代码只在列表为空时查询知识库。非空列表分支中的 H = at(right, X, Y) 只是对两个 term 做统一，没有调用 at/3 检查该元素是否存在于知识库中。

保留原来的两个 at/3 事实，将原来的 flips/4 定义替换为：

flips(right, X, Y, [at(right, X, Y)|_]) :-
    at(right, X, Y).

flips(right, X, Y, [_|T]) :-
    flips(right, X, Y, T).

第一个分支匹配当前列表头，并查询知识库；第二个分支跳过当前元素，递归查找列表尾。

执行：

?- flips(A, B, C,
         [at(right, fred, sam), at(right, steve, sam)]).

通过回溯可以依次得到：

A = right,
B = fred,
C = sam ;
A = right,
B = steve,
C = sam ;
false.

不需要为空列表编写成功分支。列表为空时，已经没有元素可返回，查询应当失败，让回溯结束。

这组规则逐项返回列表中能匹配知识库的元素，不要求列表中的所有元素都存在于知识库中。

portray_clause(Pred) 只负责打印，不能把 Pred 作为查询结果返回。要得到替代 term 的列表，可以用修正后的 flips/4 配合 findall/3：

?- findall(
       at(left, X, Y),
       flips(right, X, Y,
             [at(right, fred, sam), at(right, steve, sam)]),
       Preds
   ).

结果为：

Preds = [at(left, fred, sam), at(left, steve, sam)].

这里的 at(left, X, Y) 是用于构造结果的 term，不会被当作目标执行，因此不需要在知识库中额外定义对应的 at(left, ...) 事实。

每次调用 at(right, X, Y) 都会独立搜索匹配项，返回哪些答案取决于调用时的变量绑定。修正后的代码先用列表元素绑定 X、Y，再通过 at/3 验证这一项。

findall/3 会收集所有成功路径的结果，不会自动去重。如果输入列表有重复项，或者知识库中存在重复事实，结果中也可能出现重复 term。没有任何匹配时，它返回空列表 []。