2

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

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

实际上，我不知道如何将 1 和 2 添加到列表 Lst 中。

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

1 回答 1

6

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

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

查看第一条规则的一种方式是，它说“具有一个元素的列表，无论该元素是什么，都与空列表相关。” 看看append([_], [])，如果我们有X = [foo]and 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，它返回除最后一项之外的所有列表。

希望这可以帮助！

于 2013-02-21T05:55:35.737 回答