Prolog 计数元素错误

Question

我正在学习序言，我想计算列表中特定元素的出现次数。

所以这是代码 -

count(_, [], _) := !.

count(El, [El|T], N) :-
    N1 is N + 1,
    count(El, T, N1).

count(El, [_|T], N) :-
    count(El, T, N).

check(List1, List2) :-
    count(3, List1, M),
    count(2, List2, N),
    M is N.

所以基本上我想传递给控制台检查（[3,4,3], [2,3,4,5,2]），它应该 return 是真的，因为出现了list1 中的 3 与 list2 中 2 的出现次数相同。但相反，它抛出了我 -

Arguments are not sufficiently instantiated. 
Exception: (10) _G1383 is _L155+1 ? creep
Exception: (9) count(3, [3, 4, 2], _G1385) ? creep
Exception: (8) count(3, [2, 3, 4, 2], _G1385) ? creep
Exception: (7) check([2, 3, 4, 2], [2, 3, 4]) ? creep

这是什么原因，我该如何解决？我检查了所有论坛，到处都写着这应该有效。这是某种版本相关的东西，还是我真的遗漏了什么？

编辑：使用 SWI-Prolog。

编辑 2：

成功了，谢谢！

代码：

count(_, [], 0) :- !.

count(El, [El|T], N) :-
    count(El, T, N1),
    N #= N1 + 1.

count(El, [Y|T], N) :-
    El \= Y,
    count(El, T, N).

check(List1, List2) :-
    count(3, List1, M),
    count(2, List2, N),
    M #= N.

Answer 1

您正在使用称为 moded 的谓词，因为它们只能在非常特殊的情况下使用。特别是，(is)/2 不能用作您在这里需要的关系。

解决这个问题的一种方法是使用更通用的谓词。例如，在对整数进行推理时，请考虑使用 Prolog 系统的 CLP(FD) 约束，它适用于所有方向。

例如，使用 GNU Prolog，只需将替换 (is)/2 为 (#=)/2:

就可以消除错误

count(_, [], _).

count(El, [El|T], N) :-
    N1 #= N + 1,
    count(El, T, N1).

count(El, [_|T], N) :-
    count(El, T, N).

check(List1, List2) :-
    count(3, List1, M),
    count(2, List2, N),
    M #= N.

现在我们得到：

?- count(3, [3, 4, 2], C).
C+1#=_1204 ;
true ;
false.

（或者，根据您的 Prolog 系统，等效答案）。

为什么？很明显，这个程序有点瑕疵。

我将查找错误作为练习。提示：M #= N 看起来很可疑：这是真的 iff M 等于 N...

Answer 2

很高兴你现在可以通过使用声明性算法让它工作了！

我对您获得的解决方案有一些小的补充意见，即：

count(_, [], 0) :- !.

count(El, [El|T], N) :-
    count(El, T, N1),
    N #= N1 + 1.

count(El, [Y|T], N) :-
    El \= Y,
    count(El, T, N).

check(List1, List2) :-
    count(3, List1, M),
    count(2, List2, N),
    M #= N.

首先请注意check/2在代码中没有使用，所以我在下面省略了它的定义。

最一般的查询

当我查看我一无所知的 Prolog 代码时，我总是首先尝试最通用的查询，其中所有参数都是变量。理想情况下，答案向我展示了解决方案通常。

例如，在您的情况下：

?- count(E, Ls, C).
Ls = [],
C = 0.

这——错误地——表明你的谓词只有一个单一解！这显然不是故意的。

因此，作为第一步，我建议您 删除 !/0 并将此代码更改为：

count(_, [], 0).

count(El, [El|T], N) :-
    count(El, T, N1),
    N #= N1 + 1.

count(El, [Y|T], N) :-
    El \= Y,
    count(El, T, N).

应用此更改后，我们得到：

?- count(E, Ls, C).
Ls = [],
C = 0 ;
Ls = [E],
C = 1 ;
Ls = [E, E],
C = 2 ;
Ls = [E, E, E],
C = 3 .

这看起来好多了：我们现在得到了几个有效答案。

终止

这个谓词可能产生多少 个答案？特别是，是否只有有限个答案？如果是这样，我们希望以下查询 terminate:

?- count(E, Ls, C), false.

您可以尝试一下，看看它实际上不会终止（至少不会很快）。这是一个 好兆头 ，因为从 正确的 实现 count/3，我们 预计不会终止 在最一般的情况下！

完整性

理想情况下，我们希望谓词完整：它不应该省略个有效答案。

例如：

?- count(E, [X,Y,Z], C).
E = X, X = Y, Y = Z,
C = 3 ;
false.

这些真的是所有解决方案吗？我不这么认为！当然有长度为 3 的列表不同于 [E,E,E]。

而且，事实上，您的程序也在某种意义上 "knows" 关于它们：

?- count(E, [1,2,3], C).
E = C, C = 1 ;
false.

但同样，这些肯定不是所有情况！ E 与 1 不同的答案在哪里？

您遇到这些问题是因为您使用的是 非单调 (\=)/2 谓词。这有一些非常难以理解的属性，特别是如果您目前才刚刚开始学习 Prolog。例如：

?- X \= Y, X-Y = a-b.
false.

?- X-Y = a-b, X \= Y.
X = a,
Y = b.

我建议使用dif/2来表示两个术语不同，获取以下版本：

count(_, [], 0).

count(El, [El|T], N) :-
    count(El, T, N1),
    N #= N1 + 1.

count(El, [Y|T], N) :-
    dif(El, Y),
    count(El, T, N).

使用这个版本，我们得到：

?- count(E, [X,Y,Z], C).
E = X, X = Y, Y = Z,
C = 3 ;
E = X, X = Y,
C = 2,
dif(Y, Z) ;
E = X, X = Z,
C = 2,
dif(Z, Y) ;
etc.

并且，特别是：

?- count(E, [1,2,3], C).
E = C, C = 1 ;
E = 2,
C = 1 ;
E = 3,
C = 1 ;
C = 0,
dif(E, 3),
dif(E, 2),
dif(E, 1).

这涵盖了所有可能出现的情况！

公平枚举

由于谓词是纯和单调，我们可以用它来公平枚举通过迭代深化.

回答

例如：

?- length(Ls, _), count(E, Ls, C).
Ls = [],
C = 0 ;
Ls = [E],
C = 1 ;
Ls = [_G588],
C = 0,
dif(E, _G588) ;
Ls = [E, E],
C = 2 ;
Ls = [E, _G597],
C = 1,
dif(E, _G597) .
C = 2 ;
etc.

非常好，表明我们可以将其用作真正的关系，不仅用于计数，还用于 正在生成.

因此，您可以考虑一个谓词 name，它更恰当地描述了这个谓词的含义 in general。我把它留作练习。

尾递归版本

请注意，由于您使用的是纯谓词，因此您可以自由地 重新排序 您的目标，并使您的谓词 尾递归，产生：

count(_, [], 0).
count(El, [El|T], N) :-
    N #= N1 + 1,
    count(El, T, N1).
count(El, [Y|T], N) :-
    dif(El, Y),
    count(El, T, N).

决定论

我们目前还有例如：

?- count(a, [a,a,a], Cs).
Cs = 3 ;
false.

使用if_/3，你可以改进这个谓词的确定性：

:- use_module(library(reif)).

count(_, [], 0).
count(E, [L|Ls], N) :-
        if_(E=L, N #= N1 + 1, N #= N1),
        count(E, Ls, N1).

这使您的谓词至少可以建立索引。在这种情况下是否改进确定性取决于您的 Prolog 系统的索引机制。

Prolog 计数元素错误

Prolog count numbers of elements Error

prolog

instantiation-error

最一般的查询

终止

完整性

公平枚举

尾递归版本

决定论