在Prolog中查找列表的长度

Question

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

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

我的逻辑是，递归调用应该包括列表的尾部（XS），并将先前的长度加1（Y为M+1）。

但这总是返回false。

有什么想法吗？

- MrD

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，如下所示：

:- op(950,fy, *).

*_.

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

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

现在我们得到了一个更加通用的定义。再一次，我们来看看最一般的查询的答案:

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

什么？只有长度为0和1的列表才能使len/2成立。这意味着，即使是len([1,2], N)也会失败！因此，我们现在可以确定：程序中可见剩余部分中的某些内容必须被修复。实际上，[XS]只描述了长度为1的列表。因此，它必须被删除...

细则：

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

- false

---

我想将规则头和体中的一些子项概括成 foo(_,_,X) :- ... .，例如 foo(1,2,X)：- ...。 如何在视觉上表示“那个”？理想情况下，我会在术语中使用 (*)/1。我可以使用 term_expansion 来实现吗？我不太愿意转换为额外的统一目标。 - repeat

@repeat: 首先将这些“硬编码”的术语翻译为 foo(A1,A2,X) :- A1 = 1, A2 = 2, ...。 - false

@repeat: 另一种方法是将 foo(_/*1*/,_/*2*/,X) ：- ... 写成这样。可以想象，我对此感到相当满意。 - false