Prolog 联合失败 [英] Prolog union fails
问题描述
我试图了解 Prolog 中联合(内置谓词)的使用.在许多情况下，它似乎在它应该成功的时候却失败了.它似乎与列表元素的顺序有关.以下所有情况均失败(它们返回false".).
I'm trying to understand the use of union (the built in predicate) in Prolog. In many cases it seems to fail when it should succeed. It seems it has something to do with the order of the elements of the lists. All of the below cases fail (they come back with "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]).
难道所有这些都不应该是真的吗?关于为什么这些案例不断失败的任何解释都会非常有帮助.
Shouldn't all of these be true? Any explanation as to why these cases keep failing would be very helpful.
另外:为什么下面没有成功并找到 A 的正确列表?
Also: Why does the below not succeed and find the correct list for A?
?- union([1,5,3], A, [4,1,5,3,2]). /** comes back with "fail." */
推荐答案
这里有几个问题.声明性和程序性的.让我们从声明性的开始，他们真的坐得更深了.可以使用适当的编程技术轻松处理程序方面，如在此答案中.
There are a couple of issues here. Declarative and procedural ones. Let's start with the declarative ones, they are really sitting a bit deeper. The procedural aspects can be handled easily with appropriate programming techniques, as in this answer.
当我们考虑谓词的声明性属性时，我们会考虑它的一组解决方案.所以我们假装我们只关心谓词将描述什么解决方案.我们将完全忽略所有这些是如何实现的.对于非常简单的谓词，这是对事实的简单枚举——就像数据库表一样.在这种情况下，这一切都是显而易见的.如果解决方案的集合是无限的，它变得更加不直观.这很容易发生.想想查询
When we consider declarative properties of a predicate, we consider its set of solutions. So we pretend that all we care about is what solutions the predicate will describe. We will completely ignore how all of this is implemented. For very simple predicates, that's a simple enumeration of facts - just like a database table. It is all obvious in such situations. It becomes much more unintuitive if the set of solutions is infinite. And this happens so easily. Think of the query
?- length(Xs,1).
这个看起来无害的查询要求所有长度为 1 的列表.他们都是！让我数一数 - 那是无限多！
This harmless looking query asks for all lists of length one. All of them! Let me count - that's infinitely many!
在我们查看 Prolog 产生的实际答案之前，想一想在这种情况下你会做什么.你会如何回答这个问题?我的一些微不足道的尝试
Before we look at the actual answer Prolog produces, think what you would do in such a situation. How would you answer that query? Some of my feeble attempts
?- 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 应该产生所有这些无限多的值吗?这需要多少时间?你有多少时间盯着文字墙?你的一生显然是不够的.
Should Prolog produce all those infinitely many values? How much time would this take? How much time do you have to stare at walls of text? Your lifetime is clearly not enough.
有一条出路:逻辑变量！
There is a way out: The logic variable!
?- length(Xs, 1).
Xs = [_A].
% ^^
这个小 _A 允许我们将所有奇怪的解决方案折叠成一个单一答案！
This little _A permits us to collapse all strange solutions into a single answer!
所以在这里我们真的很幸运:我们用这个不错的变量驯服了无穷大.
So here we really had a lot of luck: we tamed the infinity with this nice variable.
现在回到你们的关系.在那里，我们希望将集合表示为列表.列表显然不是集合本身.考虑列表 [a,a] 和列表 [a].虽然它们不同，但它们旨在代表同一个集合.想一想:[a] 有多少种替代表示?是的，无限多.但是现在，逻辑变量不能帮助我们紧凑地表示所有这些1.因此，我们必须一一列举它们.但是，如果我们必须枚举所有这些答案，实际上所有查询都不会终止，因为要显式枚举无限多的解决方案.好的，有些仍然会:
Now back to your relation. There, we want to represent sets as lists. Lists are clearly not sets per se. Consider the list [a,a] and the list [a]. While they are different, they are meant to represent the same set. Think of it: How many alternate representations are there for [a]? Yep, infinitely many. But now, the logic variable cannot help us to represent all of them compactly1. Thus we have to enumerate them one-by-one. But if we have to enumerate all those answers, practically all queries will not terminate due to infinitely many solutions to enumerate explicitly. OK, some still will:
?- union([], [], Xs).
Xs = [].
以及所有地面查询.以及所有失败的查询.但是一旦我们有一个像
And all ground queries. And all failing queries. But once we have a variable like
?- union([a], [], Xs).
Xs = [a]
; Xs = [a,a]
; Xs = [a,a,a]
; ...
我们已经深入到不终止状态了.
we already are deep into non-termination.
因此，我们必须做出一些决定.我们需要以某种方式驯服这种无限.一个想法是考虑以某种方式偏向一边的实际关系的子集.如果我们想问像 union([1,2],[3,4], A3) 这样的问题，那么在我们有这个 函数依赖
So given that, we have to make some decisions. We somehow need to tame that infinity. One idea is to consider a subset of the actual relation that leans somehow to a side. If we want to ask questions like union([1,2],[3,4], A3) then it is quite natural to impose a subset where we have this functional dependency
A1, A2 → A3
A1, A2 → A3
有了这个函数依赖，我们现在可以为每对 A1、A2 准确地确定 A3 的 one 值.以下是一些示例:
With this functional dependency we now determine exactly one value for A3 for each pair of A1, A2. Here are some examples:
?- union([1,5,3], [1,2], A3).
A3 = [5,3,1,2].
?- union([1,2,3], [], A3).
A3 = [1,2,3].
请注意，Prolog 总是将 . 放在末尾.这意味着 Prolog 说:
Note that Prolog always puts a . a the end. That means Prolog says:
迪西！我已经说过.没有更多的解决方案.
Dixi! I have spoken. There are no more solutions.
(其他 Prologs 最后会抱怨不".)因此，查询(来自您的评论)现在失败:
(Other Prologs will moan "No" at the end.) As a consequence, the queries (from your comments) now fail:
?- union([1,5,3], [1,2], [1,5,3,2]).
false.
?- union([1,2,3],[],[2,3,1]).
false.
因此，现在施加这种功能依赖性极大地限制了解决方案集.该限制是实施者的任意决定.本来可以不一样的！有时会删除重复项，有时则不会.如果 A1 和 A2 都是重复的空闲列表，结果 A3 也将是重复的空闲列表.
So imposing that functional dependency now restricts the set of solutions drastically. And that restriction was an arbitrary decision of the implementer. It could have been different! Sometimes, duplicates are removed, sometimes not. If A1 and A2 both are duplicate free lists, the result A3 will be duplicate free, too.
在研究了它的实现之后，以下内容似乎成立(您不需要这样做，文档应该足够好 - 但事实并非如此):最后一个参数中的元素结构如下，其中顺序:
After looking into its implementation, the following seems to hold (you do not need to do this, the documentation should be good enough - well it isn't): The elements in the last argument are structured as follows and in that order:
A1 的元素也不会出现在 A2 中.按照A1的相对顺序.
The elements of A1 that do not occur in A2, too. In the relative order of A1.
A2 的所有元素按其原始顺序排列.
All elements of A2 in their original order.
所以有了这个函数依赖，更多的属性被潜入了.比如 A2 总是 A3 的后缀！因此，以下内容不可能为真，因为没有 A3 的后缀可以使该查询为真:
So with this functional dependency further properties have been sneaked in. Such as that A2 is always a suffix of A3! Consequently the following cannot be true, because there is no suffix of A3 that would make this query true:
?- union([1,5,3], A2, [4,1,5,3,2]).
false.
还有更多可以在声明级别上描述的违规行为.通常，为了效率，关系过于笼统.喜欢:
And there are even more irregularities that can be described on a declarative level. Often, for the sake of efficiency, relations are too general. Like:
?- union([],non_list,non_list).
我们通常只对带有参数的目标感兴趣，这些目标要么是列表(如 [a,b])，要么是部分列表(如 [a,b|Xs]).
Such concerns are often swiped away by noting that we are only interested in goals with arguments that are either lists (like [a,b]) or partial lists (like [a,b|Xs]).
无论如何.我们现在终于描述了我们期望的所有声明性属性.现在是下一部分:应该充分实施这种关系！又有一堆新问题在等着我们！
Anyway. We finally have now described all the declarative properties we expect. Now comes the next part: That relation should be implemented adequately! There again a new bunch of problems awaits us!
使用 SWI 的 library(lists)，我得到:
With library(lists) of SWI, I get:
?- union([1,2], [X], [1,2,3]).
false.
?- X = 3, union([1,2], [X], [1,2,3]).
X = 3.
确实不正确:这只能从程序上理解，看实际实现.这不再是一个干净的关系.但是这个问题可以修复！
Which is really incorrect: This can only be understood procedurally, looking at the actual implementation. This no longer is a clean relation. But this problem can be fixed!
您可以通过坚持使用 Prolog 的纯单调子集来完全避免正确性问题.有关更多信息，请参见上文.
You can avoid the correctness issues altogether by sticking to the pure, monotonic subset of Prolog. See above for more.
1) 说实话，可以用某种形式的约束来表示那个无限集.但是，当前的 Prolog 系统没有为集合提供一个单一的库这一事实应该清楚地表明这不是一个明显的选择.
这篇关于Prolog 联合失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
