list Prolog中的列表长度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19230594/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
List Length in Prolog
提问by Fery
I am beginner in Prolog programming. I wrote this program to calculate the length of a list. Why is below program wrong?
我是 Prolog 编程的初学者。我编写了这个程序来计算列表的长度。为什么下面的程序是错误的？
length(0, []).
length(L+l, H|T) :- length(L, T).
I wrote below program and it works correctly.
我写了下面的程序，它工作正常。
length([], 0).
length([H|T], N) :- length(T, N1), N is N1+1.
when I changed the order, I got an error. Why?
当我更改订单时，出现错误。为什么？
length([], 0).
length([H|T], N) :- N is N1+1, length(T, N1).
回答by Nicholas Carey
You need to use an accumulator. While you could do something like this:
您需要使用累加器。虽然你可以做这样的事情：
list_length([] , 0 ).
list_length([_|Xs] , L ) :- list_length(Xs,N) , L is N+1 .
which will recurse all the way down to the end of the list and then, as each invocation returns, add one to the length, until it gets back to the top level with the correct result.
这将一直递归到列表的末尾，然后在每次调用返回时，将长度加一，直到返回到具有正确结果的顶层。
The problem with this approach is that each recursion pushes a new stack frame on the stack. That means you will [eventually] run out of stack space given a long enough list.
这种方法的问题在于每次递归都会在堆栈上推送一个新的堆栈帧。这意味着如果列表足够长，您将 [最终] 耗尽堆栈空间。
Instead, use a tail-recursive intermediary, like this:
相反，使用尾递归中介，如下所示：
list_length(Xs,L) :- list_length(Xs,0,L) .
list_length( [] , L , L ) .
list_length( [_|Xs] , T , L ) :-
T1 is T+1 ,
list_length(Xs,T1,L)
.
This code seeds a worker predicate that carries an accumulator, seeded with 0. On each recursion it creates a new accumulator whose value is the current value + 1. When the end of the list is reached, the value of the accumulator is unified with the desired result.
这段代码播种了一个带有累加器的工作谓词，种子为 0。在每次递归时，它创建一个新的累加器，其值为当前值 + 1。当到达列表末尾时，累加器的值与想要的结果。
The prolog engine is smart enough (TRO/Tail Recursion Optimization) to see that it can reuse the stack frame on each call (since none of the locals are used after the recursive call), thus neatly converting the recursion into iteration.
prolog 引擎足够聪明（TRO/Tail Recursion Optimization），可以看到它可以在每次调用时重用堆栈帧（因为在递归调用之后没有使用任何局部变量），从而巧妙地将递归转换为迭代。
回答by CapelliC
this code
这段代码
length_1(0,[]).
length_1(L+1, [H|T]) :- length_1(L,T).
works (please note the added square braces), but in unexpected way. It will build an expression tree, that could be evaluated later:
工作（请注意添加的方括号），但以意想不到的方式。它将构建一个表达式树，稍后可以对其进行评估：
?- length_1(X, [1,2,3]), L is X.
X = 0+1+1+1,
L = 3.
In your rewritten code (second version), you get an error because N1 is not yet instantiated at the time you call is/2.
在您重写的代码（第二个版本）中，您会收到一个错误，因为在您调用 is/2 时 N1 尚未实例化。
回答by Paulo Moura
As hinted in Carlo's answer, L+1is a Prolog term with two arguments, Land 1, whose functor is +. Prolog is not a functional language, so you can not type L+1and expect it to be evaluated to the sum. Try to follow Carlo's suggestion and use the is/2predicate to force arithmetic evaluation. For example, calling the goal X is 3 + 4will evaluate the right operand and attempt to unify the result with the left operand. If the left operand, X, is a variable, it will be unified with 7. Also note that, in Prolog, variables are single assignment (but can be further instantiated if the assigned term includes variables, however). I.e. you can only assign a term to a variable once. This assignment is undone when you backtrack over the goal doing the assignment.
正如 Carlo's answer 所暗示的那样，L+1是一个 Prolog 术语，有两个参数，L和1，其函子是+。Prolog 不是函数式语言，因此您不能键入L+1并期望它被评估为总和。尝试遵循 Carlo 的建议并使用is/2谓词来强制算术评估。例如，调用目标X is 3 + 4将评估右操作数并尝试将结果与左操作数统一。如果左操作数 ,X是一个变量，它将统一为7. 还要注意，在 Prolog 中，变量是单次赋值的（但是，如果赋值的术语包括变量，则可以进一步实例化）。即您只能将一个术语分配给一个变量一次。当您回溯完成分配的目标时，此分配将被撤消。
回答by garciparedes
len([], LenResult):-
LenResult is 0.
len([X|Y], LenResult):-
len(Y, L),
LenResult is L + 1.
回答by AlCorreia
The other answers point out relevant issues, but I think the problem is simply an uninstantiated variable. In the last example
其他答案指出了相关问题，但我认为问题只是一个未实例化的变量。在最后一个例子中
length([], 0).
length([H|T], N) :- N is N1+1, length(T, N1).
Although we can have variables on the right hand side of is, they must have been instantiated to an integer so that Prolog can carry out the arithmetic operation. In the example above, N1is not instantiated yet, and Prolog cannot apply the isfunctor. The type of error is not mentioned in the question, but it should be an instantiation_erroror "Arguments are not sufficiently instantiated" (if in SWI-Prolog).
虽然我们可以在 的右侧有变量is，但它们必须被实例化为一个整数，以便 Prolog 可以执行算术运算。在上面的例子中，N1尚未实例化，Prolog 无法应用is函子。问题中没有提到错误类型，但它应该是一个instantiation_error或“参数未充分实例化”（如果在 SWI-Prolog 中）。
When you invert the goals in the second rule
当你在第二条规则中颠倒目标时
length([], 0).
length([H|T], N) :- length(T, N1), N is N1+1.
N1is already instantiated to an integer by the time isgets called, and the program completes without errors.
N1在is被调用时已经实例化为一个整数，并且程序完成没有错误。
See also this other thread.
另请参阅此其他线程。
