Prolog计算列表中高于n的元素个数

Question

我对Prolog比较陌生，因此在某个任务上遇到了一些问题。这个任务是编写一个尾递归谓词count_elems(List,N,Count)，条件是List_Element > N，Count1 is Count+1。

我的方法：

count_elems( L, N, Count ) :-
   count_elems(L,N,0).
count_elems( [H|T], N, Count ) :-
   H > N ,
   Count1 is Count+1 ,
   count_elems(T,N,Count1).
count_elems( [H|T], N, Count ) :-
   count_elems(T,N,Count).

错误消息：

ERROR: toplevel: Undefined procedure: count_elems/3 (DWIM could not correct goal)

我不太确定问题出在哪里。谢谢任何帮助 :)

- vicR

Answer 1

如果想要编写一个尾递归版本的代码，你需要（正如CapelliC所指出的）添加一个额外的参数作为累加器。你可以从第一个语句中看到这个问题：

count_elems(L, N, Count) :- count_elems(L,N,0).

在这里，Count是一个单例变量，在任何地方都没有实例化。你对count_elems的递归调用从0开始计数，但不再有一个变量来实例化总数。所以，你需要：

count_elems(L, N, Count) :-
    count_elems(L, N, 0, Count).

接下来声明count_elem/4条子句：

count_elems([H|T], N, Acc, Count) :-
    H > N,                            % count this element if it's > N
    Acc1 is Acc + 1,                  % increment the accumulator
    count_elems(T, N, Acc1, Count).   % check the rest of the list
count_elems([H|T], N, Acc, Count) :-
    H =< N,                           % don't count this element if it's <= N
    count_elems(T, N, Acc, Count).    % check rest of list (w/out incrementing acc)
count_elems([], _, Count, Count).     % At the end, instantiate total with accumulator

您可以为count_elems/4使用“if-else”结构：

count_elems([H|T], N, Acc, Count) :-
    (H > N
    ->  Acc1 is Acc + 1
    ;   Acc1 = Acc
    ),
    count_elems(T, N, Acc1, Count).
count_elems([], _, Count, Count).

同样，正如CapelliC所指出的那样，您所述的错误消息可能是由于未读取您的prolog源文件引起的。

- lurker

Answer 2

使用clpfd保持逻辑纯度！

以下是操作方法：

:- use_module(library(clpfd)).

count_elems([],_,0).
count_elems([X|Xs],Z,Count) :-
   X #=< Z,
   count_elems(Xs,Z,Count).
count_elems([X|Xs],Z,Count) :-
   X #> Z,
   Count #= Count0 + 1,
   count_elems(Xs,Z,Count0).

让我们看看多功能的count_elems/3如何使用：

？- count_elems([1,2,3,4,5,4,3,2],2,Count)。
计数=5；（留下无用的选择点）
假。
？- count_elems([1,2,3,4,5,4,3,2],X,3)。
X=3；
假。
？- count_elems([1,2,3,4,5,4,3,2],X,Count)。
计数=0，X在5..sup中；
计数=1，X=4；
计数=3，X=计数；
计数=5，X=2；
计数=7，X=1；
计数=8，X在inf..0中。

---

编辑于2015年5月5日

我们还可以使用元谓词tcount/3，与(#<)/2的具象化版本结合使用：

#<(X,Y,Truth) :- integer(X), integer(Y), !, ( X<Y -> Truth=true ; Truth=false ).
#<(X,Y,true)  :- X #<  Y.
#<(X,Y,false) :- X #>= Y.

让我们再次运行上面的查询！

?- tcount(#<(2),[1,2,3,4,5,4,3,2],Count).
Count = 5.                                           % succeeds deterministically

?- tcount(#<(X),[1,2,3,4,5,4,3,2],3).
X = 3 ;
false.

?- tcount(#<(X),[1,2,3,4,5,4,3,2],Count).
Count = 8, X in inf..0 ;
Count = 7, X = 1       ;
Count = 5, X = 2       ;
Count = 3, X = Count   ;
Count = 1, X = 4       ; 
Count = 0, X in 5..sup .

关于效率的说明:

• count_elems([1,2,3,4,5,4,3,2],2,Count) 留下了一个无用的选择点。
• tcount(#<(2),[1,2,3,4,5,4,3,2],Count) 成功地确定了结果。

- repeat

---

为什么不使用高阶版本？ - false

你不需要使用(=)/3，因为它涉及到语法相等，但你想要基于CLPFD模块的相等性。 - false

好的，将(#=<)/3定义为与(=)/2类似。 - false

Answer 3

看起来你没有查阅源文件。

当你修复这个问题时（你可以将这些规则保存在一个名为count_elems.pl的文件中，然后发出一个?- consult(count_elems).），你将面临实际的问题，即第一条规则中的Count是单例模式，这意味着你必须将计数器传递到实际的尾递归子句中，并在访问列表结束时将其与累加器（更新为Count1的Count）统一。

你最终会得到3个count_elems/4子句。不要忘记基本情况：

count_elems([],_,C,C).

- CapelliC