Prolog列表成员资格,返回多个结果

Question

我有一个标准程序来确定列表的成员资格:

member(X, [X|_]).  
member(X, [_|T]) :- member(X, T).

当我提出以下查询时,我不明白的原因是:

?- member(a,[a,b]).

结果是

True;  
False.

我会想到,在使用第一条规则满足目标时(作为列表的头部),将返回True,这将是if的结束.看起来好像是在试图用第二条规则来满足目标并且失败了？

Prolog翻译是SWI-Prolog.

Answer 1

让我们先考虑一个类似的问题:[编辑:这样做而不添加你自己的定义; member/2已定义]

?- member(a,[b,a]).
true.

在这种情况下,您将获得最佳答案:只有一个解决方案.但是当交换列表中的元素时,我们得到:

?- member(a,[a,b]).
true ;
false.

从逻辑上讲,两者都只是对查询为真的肯定.

差异的原因在于,在第二个查询中,true在找到a列表的元素时立即给出答案.其余列表[b]不包含拟合元素,但尚未检查.只有在请求(命中SPACE或;)时才会尝试列表的其余部分,结果是没有进一步的解决方案.

从本质上讲,当计算完成并且还有一些工作要做时,这个小差异会给你一个提示.对于简单查询,这没有什么区别,但在更复杂的查询中,这些开放的备选方案(选择点)可能会累积并耗尽内存.

老年人总是问你是否想看到进一步的解决方案,即使没有.

编辑:

如果没有答案,则避免要求下一个答案的能力极其依赖于实施细节.即使在同一系统中,加载相同的程序,您也可能得到不同的结果.但是,在这种情况下,我使用的是SWI的内置定义,member/2而您使用自己的定义,它会覆盖内置定义.

SWI使用以下定义作为内置逻辑上与您的定义相同,但是使SWI更容易避免不必要的选择点 - 但许多其他系统无法从中获利:

member(B, [C|A]) :-
        member_(A, B, C).

member_(_, A, A).
member_([C|A], B, _) :-
        member_(A, B, C).

使事情变得更加复杂:许多Prolog有一个不同的顶层,当查询不包含变量时,它永远不会要求进一步的答案.因此,在这些系统(如YAP)中,您会得到错误的印象.

请尝试以下查询以查看此内容:

?- member(X,[1]).
X = 1.

SWI再次能够确定这是唯一的答案.但YAP,例如,不是.