计算列表中的出现次数
Counting occurrences in list
我正在尝试创建一个规则来计算给定列表中某个元素出现的次数,到目前为止我所尝试的似乎并不像我期望的那样工作:
这里第一个参数应该是列表,第二个是我们要找的元素,最后一个是出现次数:
%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
这是正确的。
问题是 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
.
评价与统一
在 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
。
我正在尝试创建一个规则来计算给定列表中某个元素出现的次数,到目前为止我所尝试的似乎并不像我期望的那样工作:
这里第一个参数应该是列表,第二个是我们要找的元素,最后一个是出现次数:
%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
这是正确的。
问题是 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
.
评价与统一
在 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
。