以下程序中存储的变量是什么? [英] What the the variables in following program stores?

问题描述

total_item([],0).
total_item([_|Rest],N) :- total_item(Rest,C), N is C+1.

此程序将一个数组作为输入，并计算该列表中的项目总数.但是我没有得到确切的变量N和C存储的内容.任何解释将不胜感激.谢谢

This program takes an array as input and count the total number of item in that list. But I am not getting what exactly variable N and C stores. Any explanation would be appreciate. Thank you

推荐答案

Ness的答案应该已经为您清楚地了解了该谓词定义.但是，您可以从中学到更多.让我们跟踪一个简单的调用.在这里，我使用的是GNU Prolog，但是大多数Prolog系统都提供相同的跟踪功能:

Will Ness answer should have provided you with a clear understanding of that predicate definition. But there's more that you can learn from it. Let's do a trace of a simple call. Here I'm using GNU Prolog but most Prolog system provide the same trace functionality:

| ?- trace.
The debugger will first creep -- showing everything (trace)

yes
{trace}
| ?- total_item([1,2,3], N).
      1    1  Call: total_item([1,2,3],_285) ? 
      2    2  Call: total_item([2,3],_354) ? 
      3    3  Call: total_item([3],_378) ? 
      4    4  Call: total_item([],_402) ? 
      4    4  Exit: total_item([],0) ? 
      5    4  Call: _430 is 0+1 ? 
      5    4  Exit: 1 is 0+1 ? 
      3    3  Exit: total_item([3],1) ? 
      6    3  Call: _459 is 1+1 ? 
      6    3  Exit: 2 is 1+1 ? 
      2    2  Exit: total_item([2,3],2) ? 
      7    2  Call: _285 is 2+1 ? 
      7    2  Exit: 3 is 2+1 ? 
      1    1  Exit: total_item([1,2,3],3) ? 

N = 3

(1 ms) yes

您可以在前四行中看到谓词导致遍历列表直到最后，然后 我们计算出待处理 N is C + 1目标.列表中的每个元素都会产生一个未决的算术评估目标.这些未完成的目标必须存储在 stack 中，直到对total_item /2谓词的递归调用终止.结果，计算大小为N的列表的长度需要与N成正比的空间(用于堆栈).该谓词定义不是 tail-recursive .

You can see in the first four lines that the predicate results in walking the list until the end and only then we compute the pending N is C + 1 goals. Each element in the list results in one pending arithmetic evaluation goal. These pending goals must be stored in a stack until the recursive call to the total_item /2 predicate terminates. As a consequence, computing the length of a list of size N requires space (for the stack) proportional to N. I.e. this predicate definition is not tail-recursive.

但是我们可以重写谓词，通过使用累加器使其成为 tail-recursive 来提高其空间复杂度.累加器是一个参数，用于存储中间结果，在这种情况下，该结果到目前为止是列表中元素数量的计数:

But we can rewrite the predicate, making it tail-recursive to improve its space complexity by using an accumulator. An accumulator is an argument that stores intermediate results, in this case, the count so far of the number of elements in the list:

total_item(List, Total) :-
    total_item(List, 0, Total).

total_item([], Total, Total).
total_item([_| Rest], Total0, Total) :-
    Total1 is Total0 + 1,
    total_item(Rest, Total1, Total).

让我们追寻相同的目标:

Let's trace the same goal:

| ?- total_item([1,2,3], N).
      1    1  Call: total_item([1,2,3],_285) ? 
      2    2  Call: total_item([1,2,3],0,_285) ? 
      3    3  Call: _382 is 0+1 ? 
      3    3  Exit: 1 is 0+1 ? 
      4    3  Call: total_item([2,3],1,_285) ? 
      5    4  Call: _435 is 1+1 ? 
      5    4  Exit: 2 is 1+1 ? 
      6    4  Call: total_item([3],2,_285) ? 
      7    5  Call: _488 is 2+1 ? 
      7    5  Exit: 3 is 2+1 ? 
      8    5  Call: total_item([],3,_285) ? 
      8    5  Exit: total_item([],3,3) ? 
      6    4  Exit: total_item([3],2,3) ? 
      4    3  Exit: total_item([2,3],1,3) ? 
      2    2  Exit: total_item([1,2,3],0,3) ? 
      1    1  Exit: total_item([1,2,3],3) ? 

N = 3

(1 ms) yes

请注意，当我们遍历w列表时，累加器(辅助total_item/3谓词中的第二个参数)如何增加.有了这个定义，就没有悬而未决的目标，这意味着空间复杂度是O(1)而不是O(N).好多了.

Notice that how the accumulator, the second argument in the auxiliary total_item/3 predicate is incremented as we walk thew list. With this definition, there are no pending goals, which means the space complexity is O(1) instead of O(N). Much better.

这篇关于以下程序中存储的变量是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！