prolog - 下面的序言代码是做什么的？

Question

我无法理解下面的代码。
如果我有以下输入，有人可以逐步解释发生了什么:

append([1,2,3], Lst).

实际上，我不明白 1 和 2 是如何附加到列表 Lst 中的。

append([_], []).    
append([H|T], [H|N]) :- append(T,N).

Answer 1

听起来您是 Prolog 的新手。如果是这样，欢迎!我们来分析一下。

这个不幸命名的函数有两个子句。 Prolog 会查看这些子句以查看适用于哪一个。当它找到一个匹配的时，它会尝试执行它。如果在某处执行失败，它将备份并尝试下一个选项。这些选择点的具体位置因程序而异；在这个程序中，唯一的一个是在子句级别，决定使用哪个规则。

查看第一条规则的一种方式是说“具有一个元素的列表，无论该元素是什么，都与空列表相关。”查看 append([_], [])，如果我们有 X = [foo] 和 Y = []，它将成立，因为 [foo] 是单项列表，而 [] 是空列表。这条规则是很好的 Prolog 风格，因为无论实例化如何，它都会起作用:我们可以提供左侧或右侧或两者都不提供，这无关紧要。

第二个子句也很简单。它表示，如果左参数和右参数都以相同的项目开头，并且列表的其余部分也由同一谓词相关，则它们是相关的。换句话说，如果我有两个列表 X 和 Y 使得 append(X, Y) 为真，那么 append( [H|X], [H|Y]) 也是如此。 H 是什么并不重要，X 和 Y 是什么也不重要，除非 append/2 暗示。

从逻辑上思考，如果我知道任何单项列表都与空列表相关，并且任何列表都与以相同项目开头且其他方面相同的列表相关，那么唯一可以如此相关的是列表，其中每个项目都是相同的，除了左侧列表的末尾还有一个右侧不存在的项目。所以 [1,2,3,4] 与 [1,2,3] 相关，但 [1,2,3,foo] 和 [1,2,3] 也相关。

在程序上，让我们看看使用这组参数处理此谓词时会发生什么:

append([1,2,3], X).

第一条规则不会匹配 [1,2,3]。所以我们必须看第二条规则:

append([1|[2,3]], [1|X]) :- append([2,3], X).

我们可以重复:

append([2|[3]], [2|Y]) :- append([3], Y).

现在第一个规则确实匹配:

append([3], []).

所以把它们放在一起:

append([1,2,3], [1|X]) implies
  append([2,3], X=[2|Y]) implies
    append([3], Y=[])
  so Y = []
so X = [2]
so the right side is [1,2].

Prolog 跟踪将向您显示基本相同的信息:

?- trace, append([1,2,3], X).
   Call: (7) append([1, 2, 3], _G1633) ? creep
   Call: (8) append([2, 3], _G1752) ? creep
   Call: (9) append([3], _G1755) ? creep
   Exit: (9) append([3], []) ? creep
   Exit: (8) append([2, 3], [2]) ? creep
   Exit: (7) append([1, 2, 3], [1, 2]) ? creep

使这段 Prolog 代码困惑的原因是它看起来不像是您告诉 Prolog 如何做任何事情。这是真的，你没有，但通过指定逻辑上的真实情况，Prolog 能够自己弄清楚。这是非常聪明的代码。如果这是 Haskell，我们会谈论内置函数 init，它返回除最后一项之外的所有列表。

希望这对您有所帮助!