10

我是 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).
4

5 回答 5

11

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

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

于 2013-10-07T20:28:57.377 回答
7

这段代码

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.

在您重写的代码（第二个版本）中，您会收到一个错误，因为在您调用 is/2 时 N1 尚未实例化。

于 2013-10-07T17:19:14.393 回答
4

正如 Carlo 的回答所暗示的，L+1是一个带有两个参数的 Prolog 项，L并且1，其函子是+。Prolog 不是函数式语言，因此您不能键入L+1并期望它被求和。尝试遵循 Carlo 的建议并使用is/2谓词强制算术评估。例如，调用目标X is 3 + 4将评估右操作数并尝试将结果与左操作数统一。如果左操作数 ,X是一个变量，它将与7. 另请注意，在 Prolog 中，变量是单一赋值（但如果赋值项包含变量，则可以进一步实例化）。即您只能将一个术语分配给一个变量一次。当您回溯完成任务的目标时，此任务将被撤消。

于 2013-10-07T18:21:26.187 回答
4 
len([], LenResult):-
    LenResult is 0.

len([X|Y], LenResult):-
    len(Y, L),
    LenResult is L + 1.
于 2016-05-13T11:10:42.853 回答
0

其他答案指出了相关问题，但我认为问题只是一个未实例化的变量。在最后一个例子中

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

虽然我们可以在 的右侧有变量is，但它们必须已实例化为整数，以便 Prolog 可以执行算术运算。在上面的例子中，N1还没有实例化，Prolog 不能应用is函子。问题中没有提到错误的类型，但它应该是一个instantiation_error或“参数没有充分实例化”（如果在 SWI-Prolog 中）。

当你颠倒第二条规则中的目标时

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

N1在被调用时已经实例化为一个整数is，并且程序完成没有错误。

另请参阅此其他线程。

于 2019-05-08T13:16:53.363 回答