代码之家 › 专栏 › 技术社区 › flawr

统计列表中的出现次数

prolog-dif clpfd prolog count list

1

flawr · 技术社区 · 9 年前

我正在尝试创建一个规则来计算给定列表中某个元素的出现次数,但迄今为止,我尝试的方法似乎没有达到预期效果:

第一个论点这里应该是列表,第二个是我们要查找的元素,最后一个是出现的次数:

%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 是头和 T 这个尾给定列表的。

基本情况,例如。 count([],1,N). 收益 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

这是正确的。

2 回复 | 直到 4 年前

1

4

lurker 9 年前

评估与统一

在Prolog中 =/2 是一个合一操作人员它不会将一个术语作为一个表达式来计算,即使该术语可能表示某种数值可计算的内容。同样,当您使用 count([E|T], E, N+1) ,序言不会评估术语 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.

将产生“错误”,因为术语 +(1,2) 与术语不匹配(或者更准确地说,不能与术语统一) 3 .

啊!参数未充分实例化!

我看到过不少关于SO的帖子,其中提到了一个错误,即它们的参数“没有充分实例化”。其中许多是在使用 是/2 如上所述, 是/2 将在第二个参数中计算表达式,然后将结果与第一个参数统一。第二个参数 必须是完全可评估的 (表达式中涉及的所有变量都必须用数值实例化),否则会出现错误。同样,当使用表达式比较时,两个参数中的所有变量都必须完全实例化。因此,如果 X 是未绑定的变量,以下操作将产生“参数未充分实例化”错误:

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 .

2

1

SQB 9 年前

问题是 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).

is 事实上评估方程式,而不是统一这个 N 在下次通话中 N-1号机组 这就是为什么在第二个例子中 N=0+1+1 而不是 N=2 .