序言联合失败 [英] Prolog union fails

问题描述

我试图了解Prolog中union(内置谓词)的用法.在许多情况下，它应该成功时似乎会失败.似乎与列表元素的顺序有关.以下所有情况均失败(它们返回"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]有多少个备用表示形式?是的，无数.但是现在，逻辑变量无法帮助我们紧凑地表示所有 ¹ .因此，我们必须一一列举.但是，如果我们必须枚举所有这些答案，则实际上，由于有无数种显式枚举的解决方案，因此所有查询都不会终止.好的，有些还是可以的:

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 compactly¹. 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)的问题，那么很自然地在我们具有 functional的地方强加一个子集依赖性

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的一个值.以下是一些示例:

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.

(其他序言最后都会抱怨"No".)因此，查询(根据您的评论)现在失败:

(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:

1. A1中也不会出现在A2中的元素.按A1的相对顺序.

1. 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系统没有提供用于集合的库的事实，应该表明这不是一个显而易见的选择.}

这篇关于序言联合失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！