list - 我想计算列表中某个元素的出现次数

Question

我想计算列表中某个元素的出现次数，如果存在则谓词 unique 将为 true，否则为 false。然而，如果该元素出现多次，Prolog 会发现它为真。我不知道该怎么办...

count([], X, 0).
count([X|T], X, Y) :- count(T, X, Z), Y is 1+Z, write(Z).
count([_|T], X, Z) :- count(T, X, Z).

unique(St, [Y|RestList]) :- count([Y|RestList], St, N), N =:= 1.

Answer 1

只要第一个参数是基本列表，该解决方案就有效。在其他一些情况下，这是不正确的:

?- count([E], a, 0).
   false.

我们在这里问

How must the element E of a list of length 1 look like such that the list contains 0 occurences of a?

事实上，这个问题有答案，例如 E = b 或 E = c:

?- count([b],a,0).
   true.
?- count([c],a,0).
   true.

因此，Prolog 的回答 不完整。它应该说，是的。但如何呢？

count([], _, 0).
count([E|Es], F, N0) :-
   count(Es, F, N1),
   if_(E = F, D = 1, D = 0),
   N0 is N1+D.

这使用 if_/3和 (=)/3 .

?- length(Xs, I), count_dif(Xs, a, N).
   Xs = [], I = N, N = 0
;  Xs = [a], I = N, N = 1
;  Xs = [_A], I = 1, N = 0, dif(_A, a)
;  Xs = [a, a], I = N, N = 2
;  Xs = [_A, a], I = 2, N = 1, dif(_A, a)
;  Xs = [a, _A], I = 2, N = 1, dif(_A, a)
;  Xs = [_A, _B], I = 2, N = 0, dif(_A, a), dif(_B, a)
; ... .

为了进一步改进这一点，我们可以使用 library(clpfd)，因为它在 SICStus、YAP 和 SWI 中可用。

:- use_module(library(clpfd)).

count([], _, 0).
count([E|Es], F, N0) :-
   N0 #>= 0,
   if_(E = F, D = 1, D = 0),
   N0 #= N1+D,
   count(Es, F, N1).

现在甚至以下内容也会终止:

?- count([a,a|_], a, 1).
   false.
?- N #< 2, count([a,a|_], a, N).
   false.