Prolog的尾递归方法来计算列表

未初始化变量我试图写一个尾递归方法来计算列表中的未初始化变量的数目。我有点卡住了，我哪里错了。Prolog的尾递归方法来计算列表

我当前的查询是以下：

count([S,L],N) :- var(S), !, N+1. 
count([L],N).

来源

2011-07-12 General_9

注：这个答案提出了一个解决方案，它是递归的，但不是尾递归。对于尾递归解决方案，您应该使用累加器，这可以从此问题的其他答案中看出。

与任何递归过程，你应该添加适当的基本情况。在这种情况下，它应该是与返回与未初始化变量的数目统一0空单的条款：

count([], 0).

检查你写的条款。它输入两个元素，而不是表现为头项和尾单的列表清单，它确实没有什么用N：

count([Head|Tail], M):- 
    var(Head), 
    !, 
    count(Tail, N), 
    M is N+1.

最后，你还应该添加一个条款来处理该情况下，当列表的第一个项目是不是一个非实例变量：

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

来源

2011-07-12 19:41:41 gusbro

这不是一个尾递归因为递归调用'计数（尾，N）'之后是进一步的目标'M是N + 1'。 – Jiri

@Jini：你是对的！我监督了问题的“尾递归”部分，我只是修正了OP代码。 – gusbro

没有递归在这里，因为为了有递归，你必须在本身来定义的东西 - 你会发现代码右侧缺少count/2规则。

% two paths, variable and non-variable 
% and a base case to start the count 
count([S|L], N) :- var(S), !, count(L, N0), N is N0+1. 
count([S|L], N) :- nonvar(S), !, count(L, N). 
count([], 0).

或者，这可以简单地findall/3完成。

count_alt(L, N) :- findall(S, (member(S, L), var(S)), D), length(D, N).

来源

2011-07-12 20:08:58 Orbling

溶液'计数（...）'是不是一个尾递归因为递归调用'计数（L，N0）接着通过'进一步目标'N为N0 + 1'。 – Jiri

@Jiri：注意到，非常正确。这就是为什么我+1你的答案。我认为这个非累加器版本更简洁，因为子句更少。但蓄压器的版本是大约两倍的速度（120％较慢 - 我跑一些简档）时，'的findall/3'版本比蓄压器更慢的约50％。 – Orbling

Orbling：非蓄能器无疑是显而易见的Prolog的解决方案 - 而是一个尾递归有人问。感谢您让我知道您的性能测试和您的投票:)！ – Jiri

这是一个用于计数列表中变量的尾递归。它使用累加器技术：

count(L, N) :- count(L, 0, N).  % L=list, N=count, 0=value of the sum accumulator S 
count([], S, S) :- !.    % the innermost call, the accumulator S (2nd arg) "copied" to final result (3rd arg) 
count([H| T], S, N):- var(H), !, S1 is S+1, count(T, S1, N). % increase accumulator if H is var 
count([H| T], S, N):- count(T, S, N). % keep accumulator if H is not var

没有调用在所有子句中都跟随最后的递归调用。

来源

2011-07-12 20:21:09 Jiri

我在我的非变量规则中包含'nonvar（）'，而你已经离开了它。我认为这是因为规则顺序总是匹配第一个适合的规则，所以这些规则对我来说是顺序敏感的。 'nonvar（）'调用可能会降低速度。 – Orbling

'nonvar（）'调用会减慢速度，如果我们接受规则的顺序是不需要的。使用'nonvar（）'不需要剪切。 – Jiri

Prolog的尾递归方法来计算列表

回答

相关问题