list - 在 Prolog 中查找列表的长度

Question

我正在运行 Prolog 并尝试编写一个返回列表长度的小函数:

len([],0).
len([XS], Y) :-
    len([X|XS], M),
    Y is M+1.

我的逻辑是递归调用应该包括列表的尾部 (XS) 并将 1 增加到前一个长度(Y 是 M+1。)

这总是返回 false。

有什么想法吗？

Answer 1

以下是调试和测试 Prolog 谓词的通用方法:

从最一般的查询开始!

想一想:在 Prolog 中，您不需要编写一些测试数据。您甚至根本不需要理解谓词:只需输入自由变量即可!这始终是一个专业的举动!

所以在你的情况下，那就是

?- len(L,N).
L = [],
N = 0 ;
*LOOPS**

您的定义并没有您声称的那么糟糕:至少，对于空列表来说是正确的。

现在，也许看看您可能收到的编译器警告:

Warning: user://1:11:
        Singleton variables: [X]

接下来阅读递归规则 箭头方向:- 也就是说，从右到左:

提供 len([X|Xs], M)是真的和 Y is M+1是真的，只要所有这些都是真的，我们可以得出结论
len([XS], Y)也是如此。因此，您总是会得出有关长度为 1 的列表( [Xs] )的结论。

您需要将其重新表述为 len([X|Xs], M) :- len(Xs, N), Y is M+1 .

这是另一个策略:

概括你的程序

通过删除目标，我们可以概括一个程序1。这是我最喜欢的方法。通过添加谓词 (*)/1像这样:

:- op(950,fy, *).

*_.

现在，让我们从您的程序中删除所有目标:

len([],0).len([XS], Y) :-    * len([X|XS], M),    * Y is M+1.

What we have now is a generalization. Once again, we will look at the answers of the most general query:

?- len(L, N).
L = [],
N = 0 ;
L = [_].

什么？ len/2仅适用于长度为 0 和 1 的列表。这意味着，即使 len([1,2], N)失败!所以现在我们肯定知道:必须修复程序可见剩余部分中的某些内容。事实上， [XS]仅描述长度为 1 的列表。因此必须将其删除...

打印精美:

1 某些限制适用。本质上，你的程序必须是一个纯粹的、单调的程序。