计算列表中的出现次数

Question

我正在尝试创建一个规则来计算给定列表中某个元素出现的次数，到目前为止我所尝试的似乎并不像我期望的那样工作：

这里第一个参数应该是列表，第二个是我们要找的元素，最后一个是出现次数：

%empty list should always return 0 occurences
count([],E,0) :- true.

%if our head is what we are looking for, count
count([E|T],E,N) :- count(T,E,N-1).

%otherwise, do not count
count([H|T],E,N) :- H \== E, count(T,E,N).

此处 H 是给定列表的 head 和 T tail。

基本情况，例如count([],1,N). returns N = 0 正如预期的那样，但是一旦列表不为空，我们总是得到 false.:

?- count([1],1,N).
false.
?- count([1,2,1,3],1,N).
false.

谁能指出我做错了什么？

更新：

将第二行替换为

似乎有效

count([E|T],E,N+1) :- count(T,E,N).

但我就是不明白为什么这与我的第一个想法不等同。

然后我们得到

?- count([1,2,1,3],1,N).
N = 0+1+1

这是正确的。

Answer 1

问题是 N+1（或 N-1）未被评估，如您的第二个（工作）示例所示。

% empty list has 0 occurrences
count([], _, 0).

% if our head is what we are looking for, count
count([E|T], E, N) :-
    N_1 is N - 1,         % this is the important one
    count(T, E, N_1).

% otherwise, do not count
count([H|T], E, N) :-
    H \== E,
    count(T, E, N).

在你下次使用 N-1。这就是为什么在你的第二个例子中，你最终得到 N=0+1+1 而不是 N=2.

Answer 2

评价与统一

在 Prolog =/2 中是一个 unification 运算符。它不会将术语作为表达式进行评估，即使该术语可能表示可进行数值评估的内容。同样，当您使用 count([E|T], E, N+1) 时，Prolog 不会评估术语 N+1。对于 Prolog，这只是另一个术语，在内部表示为 +(N, 1).

要将术语解释和评估为数值表达式，您需要使用特定的 Prolog 运算符来执行此操作。正如@SQB 指出的那样，其中之一是 is/2:

N = 1, N1 is N + 1.

这将导致 N1 = 2。然而这个：

N = 1, N1 = N + 1.

将导致：N1 = 1 + 1（或等效地，N1 = +(1, 1)）。

Prolog 中也有数值比较运算符，它们也可以计算表达式。它们是 =:=/2、>/2、>=/2、</2 和 =</2。所以你会看到以下内容：

1 + 2 =:= 3.

将产生 "true"，因为 =:=/2 专门用于比较可评估数值表达式的相等性。然而：

1 + 2 = 3.

将产生 "false"，因为术语 +(1,2) 与术语 3 不匹配（或更准确地说，不能统一）。

啊！参数未充分实例化！

我在 SO 上看到很多关于错误的帖子，他们的论点是 "not sufficiently instantiated"。其中很多都在使用is/2。如上所述，is/2 将计算第二个参数中的表达式，然后将该结果与第一个参数统一。第二个参数 必须是完全可评估的 （表达式中涉及的所有变量都必须用数值实例化）否则你会得到一个错误。同样，在使用表达式比较时，两个参数中的所有变量都必须完全实例化。因此，如果 X 是未绑定的变量，则以下将产生 "arguments not sufficiently instantiated" 错误：

9 is X * 3.       % Will NOT yield X = 3, but will give an error
Y + 2 =:= X * 2.  % Error if either X or Y are not instantiated
Y = 1, X = 2, Y + 2 =:= X * 2.  % Yields "false" (fails) since 3 is not equal to 4
Y = 1, X = 2, Y + 2 < X * 2.    % Yields "true" (succeeds) since 3 is less than 4
Y = 1, X = 2, X + 1 = Y + 2.    % Yields "false" since +(2,1) doesn't unify with +(1,2)

在对表达式执行约束逻辑时，要使用的工具是CLP(FD) 库。因此：

X * 3 #= 6.

会屈服，X = 2。

计算列表中的出现次数

Counting occurrences in list

list

count

prolog

clpfd

prolog-dif

更新：