sort/2,keysort/2 vs. samsort/3,predsort/3

Question

ISO-Prolog提供sort/2并keysort/2依赖于通常称为"标准期限订单"的期限订单(7.2).对具有不同顺序的列表进行排序的常用方法是以某种方式将该列表的每个元素映射El到对列表,XKey-El然后对该列表进行排序,最后将密钥投射出去.作为一个例子,考虑如何keysort/2表达sort/2(参见实施说明).

在许多情况下,这种方法比使用通用实现特定排序谓词快得多,后者依赖于用户定义的顺序作为SWI predsort(C_3, List, SortedList) 或SICStus' samsort(O_2, List, SortedList).

我的问题归结为:

是否存在使用predsort/3resp 进行排序的情况.samsort/3不能被一些映射,sort/2-ing和投射取代？¹

并且为了清楚起见,更好地坚持有限的基础术语.因为,无限的地面术语不具有完整的词典顺序,因为它需要作为有限情况的扩展; 而且,目前尚不清楚如何将变量与两个不同变量的情况进行比较,如果符合ISO/IEC 13211-1:1995的7.2.1,那将是如何实现的:

7.2.1变量

如果X和Y是不相同的变量,则
X term_precedes Y应依赖于实现,
除了在创建排序列表(
7.1.6.5,8.10.3.1 j)期间,排序应保持不变.

因此,目前尚不清楚是否predsort/3仍有资格作为排序列表的创建.很清楚的是,在 sort/2和期间,顺序保持不变keysort/2.

---

1感谢@WillNess,这个预测应该至少包括reverse/2- 或任何线性变换.这也意味着可以实现具有重复和独特结果的结果(类似于实现的方式keysort/2).

Answer 1

首先,你可以"否定"Prolog原子.让我们称之为它atom_neg/2(这是一个愚蠢的名字,但无论如何它确实有些愚蠢):

atom_neg(A, NK) :-
    atom_codes(A, Cs),
    maplist(negate, Cs, NCs),
    append(NCs, [0], NK).

negate(X, N) :- N is -X.

我并不认为这样做很实际,但显然,这是可能的.

的总体排序是弱排序,以及一个键功能˚F上的一组Ť总排序一起ř上的陪域˚F,限定一个弱排序WR(X,Y) <==> R(F(X), f(y)).

(该上下文中函数的Codomain是函数返回的值的域.)

我可能完全错了,但是关系的存在需要一个密钥的存在:你可以用另一个关系来定义一个关系,但最终你必须比较一些可以孤立存在的东西:密钥.

这里的要点是密钥不需要与我们想要排序的东西在同一个域中,并且为同一个域的对象定义弱排序(关系).Prolog在这里做了一些奇怪的事情:它为所有可能的术语定义了一个标准的术语顺序.Prolog也没有"类型"或"域"的正确概念.我的直觉告诉我,排序不属于同一个域的东西根本不是很有用,但Prolog显然不同意.

您无法为两种情况定义键功能:

1. 比较谓词保持自己的状态;
2. 您有"不透明"对象(例如,在C中定义),它们提供比较功能但不提供键功能.

无论哪种方式,predsort都是有用的:没有人会更喜欢atom_neg/2Will Ness的解决方案.然而,它目前有一个严重的效率:它不允许稳定的排序.SWI-Prolog已经可以通过这种方式使用,只需将当前的行为添加到规范和文档中即可predsort/3.

Answer 2

编辑： @Boris 的答案显示了如何“否定”原子以进行比较，因此在这种情况下它使我的反驳无效。而问题中的新规定使其完全无效。

如果排序标准复杂，则需要排列多个子键。如果需要保留重复项，则应将递增索引作为原始术语的前缀，在排序子键之后，按照为sort/2排序而构造的术语。

然而，所构造的子密钥的复杂性和数量可能会失控。在某些区域中，首先按 X，然后按 Y，按升序或降序对排序点进行成像；在其他区域中，首先按 Y，然后按 X 排序。

然后，用仅线性数量的关键结构和标准术语顺序中的对数线性数量（可能是轻量的）比较替换对数线性数量（可能是计算量大的）比较的优势就会消失。

简单地说，predsort/3例如使用自定义比较谓词反转原子列表

comp(<,A,B):- B @< A.

等等，不能通过按“标准术语顺序”sort/2工作的 ing来完成（引用 SWI 文档）。对于数字，我们可以翻转符号，但对于名称则不行。

也许您想要添加reverse允许的操作。

在sort/4允许的情况下，我没有看到任何不起作用的东西。而且由于它是稳定的，因此次要标准也可以通过次要通过（首先是次要标准，然后是主要标准）来适应。