Prolog中的列表长度

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

length(0, []). 
length(L+l, H|T) :- length(L, T).

我写下面的程序，它工作正常。

length([], 0). 
length([H|T], N) :- length(T, N1), N is N1+1.

当我改变了顺序，我得到了一个错误。为什么？

length([], 0). 
length([H|T], N) :- N is N1+1, length(T, N1).

来源

2013-10-07 Fery

这个代码

length_1(0,[]). 
length_1(L+1, [H|T]) :- length_1(L,T).

工程（注意添加的方括号），但意想不到的方式。它将构建一个表达式树，这可能是后来评价：

?- length_1(X, [1,2,3]), L is X. 
X = 0+1+1+1, 
L = 3.

在你重写代码（第二版），你会得到一个错误，因为N1还没有在调用时实例为/ 2。

来源

2013-10-07 17:19:14 CapelliC

正如卡罗的回答暗示，L+1是Prolog项有两个参数，L和1，其仿函数是+。 Prolog不是一种功能性语言，因此您无法输入L+1，并期望对它进行评估。尝试遵循卡罗的建议并使用谓词来强制进行算术评估。例如，调用目标X is 3 + 4将评估右操作数，并尝试将结果与左操作数统一。如果左操作数X是一个变量，它将与7统一。还要注意的是，在Prolog中，变量是单个赋值（但是如果赋值的术语包含变量，则可以进一步实例化）。即你只能给变量分配一个词。当您完成作业的目标回溯时，此作业会被撤消。

来源

2013-10-07 18:21:26

您需要使用累加器。虽然你可以做这样的事情：

list_length([]  , 0). 
list_length([_|Xs] , L) :- list_length(Xs,N) , L is N+1 .

这将递归一路下跌到列表的末尾，然后，因为每个调用返回，添加一个长度，直到它回来到顶级以正确的结果。

这种方法的问题是每次递归都会在堆栈上推送一个新的堆栈帧。这意味着，如果给出足够长的列表，您将[最终]耗尽堆栈空间。

相反，使用尾递归中介，像这样：

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。到达列表末尾时，累加器的值与所需结果统一。

prolog引擎足够智能（TRO /尾递归优化）看到它可以在每次调用时重用堆栈帧（因为递归调用后没有使用局部变量），因此整齐地将递归转换为迭代。

来源

2013-10-07 20:28:57

len([], LenResult):- 
    LenResult is 0. 

len([X|Y], LenResult):- 
    len(Y, L), 
    LenResult is L + 1.

来源

2016-05-13 11:10:42 garciparedes

尽管这段代码可以回答这个问题，提供附加的上下文有关_why_和/或_how_它回答问题将显著改善其长期值。请[编辑]你的答案，添加一些解释。 –

Prolog中的列表长度

回答

相关问题