序言中的列表长度 [英] List Length in Prolog

问题描述

我是Prolog编程的初学者. 我写了这个程序来计算列表的长度.为什么下面的程序错误?

I am beginner in Prolog programming. I wrote this program to calculate the length of a list. Why is below program wrong?

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).

推荐答案

您需要使用累加器.虽然您可以执行以下操作:

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 .

它将一直递归到列表的末尾，然后在每次调用返回时，将长度加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)
  .

此代码为一个携带有一个累加器的工作者谓词提供种子，并以0为种子.在每次递归中，它都会创建一个新的累加器，其值是当前值+1.到达列表的末尾时，该累加器的值为与预期的结果保持一致.

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.

prolog引擎足够聪明(TRO/Tail递归优化)，可以看到它可以在每次调用时重用堆栈帧(因为在递归调用之后没有使用任何本地变量)，因此可以将递归整齐地转换为迭代.

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.

这篇关于序言中的列表长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！