Prolog中的列表长度

Question

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

- Fery

Answer 1

你需要使用一个累加器(accumulator)。虽然你可以像这样做:

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

这将递归到列表的最后，然后当每个调用返回时，将长度加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/尾递归优化），以便在每次调用时重用堆栈帧（因为在递归调用之后没有任何局部变量被使用），从而将递归精美地转换为迭代。

- Nicholas Carey

Answer 2

这段代码

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尚未被实例化，因此会出现错误。

- CapelliC

Answer 3

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

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

- garciparedes

---

尽管这段代码可能回答了问题，但提供关于它为什么和/或如何回答问题的额外上下文会显著提高其长期价值。请编辑您的答案以添加一些解释。 - Toby Speight

Answer 4

正如Carlo的回答中所暗示的那样，L+1是一个Prolog术语，它有两个参数L和1，其函数符号为+。Prolog不是一种函数式语言，因此你不能输入L+1并期望它被计算为和。尝试按照Carlo的建议使用is/2谓词来强制进行算术运算。例如，调用目标X is 3 + 4将求值右操作数，并尝试将结果与左操作数统一。如果左操作数X是一个变量，它将与7统一。还要注意，在Prolog中，变量是单赋值的（但如果分配的术语包括变量，则可以进一步实例化）。即，你只能一次将一个术语分配给一个变量。当你执行分配的目标时回溯覆盖这个分配。

- Paulo Moura

Answer 5

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

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 时已经被实例化为整数，程序顺利完成且没有错误。

另请参见此其他线程。

- AlCorreia

Answer 6

在Prolog中查找列表长度。

list_member(X,[X|_]).

list_member(X,[_|TAIL]) :- list_member(X,TAIL).

- anonymous

---

您发布了一个关于 member 而不是 length 的解决方案。更好的 member 在以下网址可以找到：https://www.swi-prolog.org/pldoc/doc/_SWI_/library/lists.pl?show=src#member/2 - brebs