Prolog联合失败
Prolog union fails
我正在尝试了解联合（内置谓词）在 Prolog 中的使用。在许多情况下，它似乎在应该成功的时候失败了。它似乎与列表元素的顺序有关。以下所有情况都失败了（它们返回 "false."）。
?- union([1,2,3],[],[2,3,1]).
?- union([1,5,3], [1,2], [1,5,3,2]).
?- union([4,6,2,1], [2], [1,2,4,6]).
?- union([1,2], [], [2,1]).
这些不应该都是真的吗？关于为什么这些案例不断失败的任何解释都会非常有帮助。
另外：为什么下面没有成功找到 A 的正确列表？
?- union([1,5,3], A, [4,1,5,3,2]). /** comes back with "fail." */
这里有几个问题。声明性和程序性的。让我们从声明性的开始，他们真的坐得更深了。使用适当的编程技术可以轻松处理程序方面的问题，如 in this answer.
当我们考虑谓词的声明性属性时，我们会考虑其解决方案集。所以我们假装我们只关心谓词将描述什么解决方案。我们将完全忽略所有这些是如何实现的。对于非常简单的谓词，这是事实的简单枚举 - 就像数据库 table。在这种情况下，这一切都是显而易见的。如果解决方案集是无限的，它会变得更加不直观。这很容易发生。想想查询
?- length(Xs,1).
这个看起来无害的查询要求所有长度为 1 的列表。他们都！让我数一数 - 无穷多！
在我们查看 Prolog 生成的实际答案之前，请想一想在这种情况下您会怎么做。你会如何回答这个问题？我的一些微弱尝试
?- length(Xs, 1).
Xs = [1]
; Xs = [42]
; Xs = [ben+jerry]
; Xs = [feel([b,u,r,n])]
; Xs = [cromu-lence]
; Xs = [[[]]]
; ... % I am running out of imagination
Prolog 是否应该产生所有这些无限多的值？这需要多少时间？您有多少时间盯着文字墙？你的一生显然不够
驯服解决方案的数量，从解决方案到答案
有个出路：逻辑变量！
?- length(Xs, 1).
Xs = [_A].
% ^^
这个小小的 _A 允许我们将所有奇怪的解决方案折叠成一个 单一答案 !
所以在这里我们真的很幸运：我们用这个漂亮的变量驯服了无穷大。
现在回到你的关系。在那里，我们希望将集合表示为列表。列表显然不是集合 本身 。考虑列表 [a,a] 和列表 [a]。虽然它们不同，但它们代表同一个集合。想一想：[a] 有多少种替代表示法？是的，无限多。但是现在，逻辑变量不能帮助我们将它们全部紧凑地表示1。因此，我们必须一一列举。但是，如果我们必须枚举所有这些答案，实际上所有查询都不会终止，因为要显式枚举无限多的解决方案。好的，有些人仍然会：
?- union([], [], Xs).
Xs = [].
以及所有地面查询。以及所有失败的查询。但是一旦我们有一个像
这样的变量
?- union([a], [], Xs).
Xs = [a]
; Xs = [a,a]
; Xs = [a,a,a]
; ...
我们已经陷入了非终止状态。
鉴于此，我们必须做出一些决定。我们需要以某种方式驯服这种无限。一个想法是考虑以某种方式向一边倾斜的实际关系的子集。如果我们想问像 union([1,2],[3,4], A3) 这样的问题，那么在我们有 functional dependency
的地方强加一个子集是很自然的
A1, A2 → A3
有了这个函数依赖，我们现在可以为每对 A1、A2 准确地确定 A3 的 一个 值。以下是一些示例：
?- union([1,5,3], [1,2], A3).
A3 = [5,3,1,2].
?- union([1,2,3], [], A3).
A3 = [1,2,3].
请注意，Prolog 总是将 . 放在末尾。这意味着 Prolog 说：
Dixi! I have spoken. There are no more solutions.
（其他 Prologs 会在最后抱怨 "No"。）因此，查询（来自您的评论）现在失败了：
?- union([1,5,3], [1,2], [1,5,3,2]).
false.
?- union([1,2,3],[],[2,3,1]).
false.
因此，强加这种功能依赖性现在极大地限制了解决方案集。该限制是实施者的 任意 决定。本来可以不一样的！有时，重复项会被删除，有时不会。如果 A1 和 A2 都是重复空闲列表，结果 A3 也将是重复空闲列表。
在研究了它的实现之后，以下内容似乎成立（您不需要这样做，文档应该足够好 - 但事实并非如此）：最后一个参数中的元素结构如下和按顺序：
A1 中没有出现在 A2 中的元素。按照A1的相对顺序。
A2 中所有元素的原始顺序。
所以有了这个函数依赖，更多的属性被偷偷带进来了。比如 A2 总是 A3 的后缀！因此，以下不可能为真，因为没有 A3 的后缀可以使该查询为真：
?- union([1,5,3], A2, [4,1,5,3,2]).
false.
而且还有更多的违规行为可以在声明层面进行描述。通常，为了效率，关系过于笼统。喜欢：
?- union([],non_list,non_list).
注意到我们只对参数为列表（如 [a,b]）或部分列表（如 [a,b|Xs]）的目标感兴趣，这样的担忧通常会被扫除。
总之。我们现在终于描述了我们期望的所有声明性属性。现在是下一部分：应该充分实施这种关系！又有新问题等着我们了！
使用 library(lists) 的 SWI，我得到：
?- union([1,2], [X], [1,2,3]).
false.
?- X = 3, union([1,2], [X], [1,2,3]).
X = 3.
实在是不对：这个只能从程序上理解，看实际实现。这不再是一个干净的关系。但是这个问题can be fixed!
您可以通过坚持使用纯的、单调的 Prolog 子集来完全避免正确性问题。见上文了解更多。
1) 说实话，用某种形式的约束来表示无限集合是可能的。但是，当前的 Prolog 系统没有为集合提供一个单一的库这一事实应该清楚地表明这不是一个明显的选择。
我正在尝试了解联合（内置谓词）在 Prolog 中的使用。在许多情况下，它似乎在应该成功的时候失败了。它似乎与列表元素的顺序有关。以下所有情况都失败了（它们返回 "false."）。
?- union([1,2,3],[],[2,3,1]).
?- union([1,5,3], [1,2], [1,5,3,2]).
?- union([4,6,2,1], [2], [1,2,4,6]).
?- union([1,2], [], [2,1]).
这些不应该都是真的吗？关于为什么这些案例不断失败的任何解释都会非常有帮助。
另外：为什么下面没有成功找到 A 的正确列表？
?- union([1,5,3], A, [4,1,5,3,2]). /** comes back with "fail." */
这里有几个问题。声明性和程序性的。让我们从声明性的开始，他们真的坐得更深了。使用适当的编程技术可以轻松处理程序方面的问题，如 in this answer.
当我们考虑谓词的声明性属性时，我们会考虑其解决方案集。所以我们假装我们只关心谓词将描述什么解决方案。我们将完全忽略所有这些是如何实现的。对于非常简单的谓词，这是事实的简单枚举 - 就像数据库 table。在这种情况下，这一切都是显而易见的。如果解决方案集是无限的，它会变得更加不直观。这很容易发生。想想查询
?- length(Xs,1).
这个看起来无害的查询要求所有长度为 1 的列表。他们都！让我数一数 - 无穷多！
在我们查看 Prolog 生成的实际答案之前，请想一想在这种情况下您会怎么做。你会如何回答这个问题？我的一些微弱尝试
?- length(Xs, 1).
Xs = [1]
; Xs = [42]
; Xs = [ben+jerry]
; Xs = [feel([b,u,r,n])]
; Xs = [cromu-lence]
; Xs = [[[]]]
; ... % I am running out of imagination
Prolog 是否应该产生所有这些无限多的值？这需要多少时间？您有多少时间盯着文字墙？你的一生显然不够
驯服解决方案的数量，从解决方案到答案
有个出路：逻辑变量！
?- length(Xs, 1).
Xs = [_A].
% ^^
这个小小的 _A 允许我们将所有奇怪的解决方案折叠成一个 单一答案 !
所以在这里我们真的很幸运：我们用这个漂亮的变量驯服了无穷大。
现在回到你的关系。在那里，我们希望将集合表示为列表。列表显然不是集合 本身 。考虑列表 [a,a] 和列表 [a]。虽然它们不同，但它们代表同一个集合。想一想：[a] 有多少种替代表示法？是的，无限多。但是现在，逻辑变量不能帮助我们将它们全部紧凑地表示1。因此，我们必须一一列举。但是，如果我们必须枚举所有这些答案，实际上所有查询都不会终止，因为要显式枚举无限多的解决方案。好的，有些人仍然会：
?- union([], [], Xs).
Xs = [].
以及所有地面查询。以及所有失败的查询。但是一旦我们有一个像
这样的变量?- union([a], [], Xs).
Xs = [a]
; Xs = [a,a]
; Xs = [a,a,a]
; ...
我们已经陷入了非终止状态。
鉴于此，我们必须做出一些决定。我们需要以某种方式驯服这种无限。一个想法是考虑以某种方式向一边倾斜的实际关系的子集。如果我们想问像 union([1,2],[3,4], A3) 这样的问题，那么在我们有 functional dependency
A1, A2 → A3
有了这个函数依赖，我们现在可以为每对 A1、A2 准确地确定 A3 的 一个 值。以下是一些示例：
?- union([1,5,3], [1,2], A3).
A3 = [5,3,1,2].
?- union([1,2,3], [], A3).
A3 = [1,2,3].
请注意，Prolog 总是将 . 放在末尾。这意味着 Prolog 说：
Dixi! I have spoken. There are no more solutions.
（其他 Prologs 会在最后抱怨 "No"。）因此，查询（来自您的评论）现在失败了：
?- union([1,5,3], [1,2], [1,5,3,2]).
false.
?- union([1,2,3],[],[2,3,1]).
false.
因此，强加这种功能依赖性现在极大地限制了解决方案集。该限制是实施者的 任意 决定。本来可以不一样的！有时，重复项会被删除，有时不会。如果 A1 和 A2 都是重复空闲列表，结果 A3 也将是重复空闲列表。
在研究了它的实现之后，以下内容似乎成立（您不需要这样做，文档应该足够好 - 但事实并非如此）：最后一个参数中的元素结构如下和按顺序：
A1 中没有出现在 A2 中的元素。按照A1的相对顺序。
A2 中所有元素的原始顺序。
所以有了这个函数依赖，更多的属性被偷偷带进来了。比如 A2 总是 A3 的后缀！因此，以下不可能为真，因为没有 A3 的后缀可以使该查询为真：
?- union([1,5,3], A2, [4,1,5,3,2]).
false.
而且还有更多的违规行为可以在声明层面进行描述。通常，为了效率，关系过于笼统。喜欢：
?- union([],non_list,non_list).
注意到我们只对参数为列表（如 [a,b]）或部分列表（如 [a,b|Xs]）的目标感兴趣，这样的担忧通常会被扫除。
总之。我们现在终于描述了我们期望的所有声明性属性。现在是下一部分：应该充分实施这种关系！又有新问题等着我们了！
使用 library(lists) 的 SWI，我得到：
?- union([1,2], [X], [1,2,3]).
false.
?- X = 3, union([1,2], [X], [1,2,3]).
X = 3.
实在是不对：这个只能从程序上理解，看实际实现。这不再是一个干净的关系。但是这个问题can be fixed!
您可以通过坚持使用纯的、单调的 Prolog 子集来完全避免正确性问题。见上文了解更多。
1) 说实话，用某种形式的约束来表示无限集合是可能的。但是，当前的 Prolog 系统没有为集合提供一个单一的库这一事实应该清楚地表明这不是一个明显的选择。