Prolog 中的列表长度 [英] 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 .

这将一直递归到列表的末尾，然后在每次调用返回时将长度加一，直到返回到具有正确结果的顶层.

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 Recursion Optimization)，可以看到它可以在每次调用时重用堆栈帧(因为在递归调用之后没有使用任何局部变量)，从而巧妙地将递归转换为迭代.

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 中的列表长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！