元素在Prolog列表中仅出现一次 [英] Element appears exactly once in the list in Prolog

问题描述

我想写一个谓词，以检查元素是否在列表中恰好出现一次.

I want to write a predicate which check if the Element appeares exactly once in the List.

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解.错误在哪里?

Why? Prolog should find X = c solution. Where is bug?

推荐答案

在序言中运行trace对于确定此类问题的答案可能非常有帮助.我们将在此处手动进行跟踪以进行说明.

Running a trace in prolog can be very helpful in determining the answer to this sort of question. We'll do the trace manually here for illustration.

让我们看看您的谓词:

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，它将变为:

First, Prolog attempts the first clause of your predicate. The head is once(X, [H|T]) and first expression is \+ X = H, which will become:

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最初未绑定时，\+ X = b的结果将为false，因为X = b将X与b统一并且为true.

X is instantiated (be unified with) with the atom b here, and the result of that unification succeeds. However, you have a negation in front of this, so the result of \+ X = b, when X is initially unbound, will be false since X = b unifies X with b and is true.

第一个子句因此失败. Prolog移至下一个子句.子句头为once(X, [X|T])，子句头为\+ member(X, T)，其变为:

The first clause thus fails. Prolog moves to the next clause. The clause head is once(X, [X|T]) and following is \+ member(X, T), which become:

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])失败.

member(b, [a,a,c,b,a]) succeeds because b is a member of [a,a,c,b,a]. Therefore, \+ member(b, [a,a,c,b,a]) fails.

第二个子句也失败.

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

There are no more clauses for the predicate once(X, [b,a,a,c,b,a]). All of them failed. So the query fails. The primary issue is that \+ X = H (or even X \= H, when X is not instantiated, won't choose a value from the list that is not the same as the value instantiated in H. Its behavior isn't logically what you want.

更直接的谓词方法是:

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，因此将产生:

The select will query as desired for uninstantiated X, so this will yield:

?- 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中内置谓词的名称.但这与这个特定问题无关.

As an aside, I'd avoid the predicate name once since it is the name of a built-in predicate in Prolog. But it has no bearing on this particular problem.

这篇关于元素在Prolog列表中仅出现一次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！