在Prolog列表中计算特定元素的数量

Question

我想要统计列表中某个元素出现的次数，目前我已经想到了以下方法：

rate(X,[H|T],N):-
  X == H,
  N is N+1,
  rate(X,T,N).
rate(X,[_|T],N) :-
  rate(X,T,N).  
rate(_,[],N) :-
  N is 0.

我已经介绍了当找到匹配项、未找到匹配项和到达列表末尾时的情况。但是在测试时，我遇到了

43 ?- rate(4,[4,2,3,4,4,2],X).
ERROR: is/2: Arguments are not sufficiently instantiated
Exception: (6) frequency(4, [4, 2, 3, 4, 4, 2], _G393) ?     

我需要了解您错过了哪些论点？

- rex

Answer 1

如果 X 是数字，您可以使用 is/2（例如：N is X）。如果 X 是自由变量，则不能使用 is/2。在您的第一个条款中，您有：N is N+1。这是错误的，因为 N 是一个自由变量（在此时它没有值，因此对于 N+1 也是如此）。

还有另一个错误。在：

rate(X,[_|T],N) :-
  rate(X,T,N).

只有当X不是列表中的第一个元素时才使用此代码，请确保这一点为真！以下是代码：

count(_, [], 0) :- !. /* empty list, base case */

count(X, [X|T], N) :- /* if X is in the head of the list */
    count(X, T, N2), /* count on the tail (let this N2) */
    N is N2 + 1.     /* and N is N2 + 1  */

count(X, [Y|T], N) :- 
    X \= Y,          /* if X is not in the head */
    count(X, T, N).  /* just count the rest */

- Haile

---

我现在明白了，非常感谢你对处理自由变量的解释！ - rex

你不需要步骤 X \= Y。只需在前一个谓词中加入一个割断，即当它们相等时。 - Ash

Answer 2

你需要让你的子句互斥，第二个子句将在第一个子句成功的任何地方成功。

至于你的错误，它是关于信息流的。你需要交换你第一个子句中的行，像这样:

rate(X,[H|T],N):-
  X == H,
  rate(X,T,N1),
  N is N1+1.

这个更改将使您的谓词不是尾递归。要进行尾递归，它需要向下传递信息，而不是像现在这样在返回时接收它：

rate(X,[H|T],N):-
  X == H,
  N1 is N+1,
  rate(X,T,N1).

现在你可以看到，这里不是得到最终值，而是指定初始值。当我们到达基本情况时，就得到了我们的结果。

rate(X, [], N).

这里的N是结果。如何将其取回？使用额外的参数，一个未实例化的变量，在到达底部时与此结果相一致：

rate(X, [], N, V) :- V is N.

现在递归子句必须适应这个变量，将其 不变地 沿着调用链传递。

- Will Ness

---

现在你有权力点赞了，如果你不知道的话。任何你认为好的答案，你都可以点赞。 :) - Will Ness

@rex 顺便说一下，N is N+1 是不好的，但并不是因为 N 是一个“自由变量”（更常见的称呼是未实例化的变量）。我的意思是，即使 N 先被实例化，N is N+1 仍然是不好的。 - Will Ness

Answer 3

如果您喜欢函数式编程风格，可以使用SWI Prolog进行编写：

:- use_module(library(lambda)).


rate(X,L,N) :-
    foldl(\Y^V0^V1^((X = Y->V1 is V0+1; V1 = V0)), L, 0, N).

- joel76