了解序言中反向列表的这种实现

Question

我已经编写了以下小型知识库来反转给定列表，

reverse_list([],[]).
reverse_list([X|L1], [L2|X]) :-
   reverse_list(L1, L2).

当前，执行时

reverse_list([a,b,c,d], X).

它产生，

X = [[[[[]|d]|c]|b]|a].

解释为什么会发生将不胜感激。而且，我该如何解决这个问题？

我认为在最后一步L2变为[]，在向后传播期间，它变成这样。如何X = [d,c,b,a]使用这种方法的修改来获得类似的输出。

PS：我是Prolog的新手。

Answer 1

您可以对Prolog程序进行代数推理。

为了向您展示一种方式，让我们考虑一个更简单的目标，该目标也显示了该问题：

？-reverse_list（[a]，Ls）。
Ls = [[] | a]。

为什么会这样？

由于此举行，如果下式成立：

α-[a] ＝ [X | L1]，Ls ＝ [L2 | X]，reverse_list（L1，L2）。
L1 = L2，L2 = []，
Ls = [[] | a]，
X = a。

我只是插入了的定义reverse_list/2，使其等效于原始查询，因此当然仍然显示了问题。

现在，要点：我们可以泛化查询（只需省略一些目标），仍然可以看到问题所在：

α-[a] ＝ [X | L1]，Ls ＝ [L2 | X]。
L1 = []，
Ls = [L2 | a]，
X = a。

因此，很明显，子句标题包含一个错误：您正在描述形式的术语[Ls|a]。这不是列表，因为a是原子。

+1是一个很好的命名约定！list_reversed/2甚至会更好（避免必须提出其他使用方式也很有意义），并且可能会有更好的名称。

Answer 2

您已经发现程序有问题，并且@mat向您显示了为什么给出的答案不正确。这是解决问题的另一种方法：只需遵循您的期望即可！在您的情况下，这将是：

?- reverse_list([a,b,c,d], [d,c,b,a]).
false.  % unexpected failure

因此，在这里您声明应该是这种情况，但事实并非如此。因此，您的程序对于查询来说太专业了。它缺少此解决方案。

要在程序中找到负责的部分，您现在可以对程序进行泛化，以使目标仍然失败。

：-op（950，fy，*）。％前缀*，请参阅更多内容。
*（_）。

reverse_list（[]，_ / * [] * /）。
reverse_list（[X | L1]，[L2 | X]）：-
   *  reverse_list（L1，L2）。

因此，我删除了规则中的目标和事实中的第二个参数-程序仍然失败！现在，您需要在其余可见部分中进行修改，以解决问题。

reverse_list([X|L1], [L2|X])
              ^          ^

在X出现一次作为元素并为列表。

有一个避免这种错误的简单约定：名称列表最好加上一个复数- s。因此，如果您有一个元素X，请调用该列表Xs，这将是一起[X|Xs]。这样，问题将更容易发现：

  reverse_list([X|Xs], [Ys|X]) :- ...
                           ^ suspicious!