list - 元素在 Prolog 的列表中只出现一次

Question

我想编写一个谓词来检查元素是否在列表中恰好出现一次。

once(Element, List).

我的代码:

once(X, [H | T]) :-
    \+ X = H,
    once(X, T).
once(X, [X | T]) :-
    \+ member(X, T).

?- once(c, [b,a,a,c,b,a]).
true

?- once(b, [b,a,a,c,b,a]).
false.

但如果我问:

once(X, [b,a,a,c,b,a]).

序言回答:

false

为什么？ Prolog 应该找到 X = c 解决方案。错误在哪里？

Answer 1

运行 trace in prolog 对确定这类问题的答案非常有帮助。我们将在此处手动进行跟踪以进行说明。

让我们看看你的谓词:

once(X, [H | T]) :-
    \+ X = H,
    once(X, T).
once(X, [X | T]) :-
    \+ member(X, T).

现在让我们考虑一下查询:

once(X, [b,a,a,c,b,a]).

首先，Prolog 尝试谓词的第一个子句。头像是 once(X, [H|T])第一个表达式是 \+ X = H ，这将变为:

once(X, [b|[a,a,c,b,a]]) :-  % [H|T] instantiated with [b,a,a,c,b,a] here
                             %   So, H is b, and T is [a,a,c,b,a]
    \+ X = b,
    ...

X用原子 b 实例化(统一)在这里，统一的结果成功了。但是，前面有一个否定，所以 \+ X = b 的结果, 当 X最初是未绑定(bind)的，自 X = b 起为假统一 X与 b并且是真的。

因此，第一个子句失败了。 Prolog 移至下一个子句。子句标题是 once(X, [X|T])以下是 \+ member(X, T) ，变成:

once(b, [b|[a,a,c,b,a]]) :-    % X was instantiated with 'b' here,
                               %   and T instantiated with [a,a,c,b,a]
    \+ member(b, [a,a,c,b,a]).

member(b, [a,a,c,b,a])成功是因为 b是 [a,a,c,b,a] 的成员.因此， \+ member(b, [a,a,c,b,a])失败。

第二个条款也失败了。

谓词 once(X, [b,a,a,c,b,a]) 没有更多子句.他们都失败了。所以查询失败。主要问题是 \+ X = H (甚至 X \= H ，当 X 未实例化时，不会从列表中选择与 H 中实例化的值不同的值。它的行为在逻辑上不是你想要的。

更直接的谓词方法是:

once(X, L) :-           % X occurs once in L if...
    select(X, L, R),    % I can remove X from L giving R, and
    \+ member(X, R).    % X is not a member of R

select将根据需要查询未实例化的 X ，所以这将产生:

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

?-  once(b, [b,a,a,c,b,a]).
false.

?- once(X, [b,a,a,c,b,a]).
X = c ;
false.

顺便说一句，我会避免使用谓词名称 once因为它是 Prolog 中内置谓词的名称。但它与这个特定问题无关。