sorting - sort/2、keysort/2 与 samsort/3、predsort/3

Question

ISO-Prolog 提供 sort/2和 keysort/2它依赖于术语顺序(7.2)，通常称为“标准术语顺序”。
以不同顺序对列表进行排序的常用方法是映射每个元素 El以某种方式将该列表中的一对列表 XKey-El然后对该列表进行排序，最后将 key 投影出去。作为一个例子，考虑如何 keysort/2可以用 sort/2 表示(See the note for an implementation)。

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

我的问题归结为:

Are there cases where a sorting using predsort/3 resp. samsort/3 cannot be replaced by some mapping, sort/2-ing and projecting?¹

为了清楚起见，最好坚持有限的基础术语。因为，无限基本项不具有总的词典顺序，因为它需要作为有限情况的扩展；此外，在 ISO/IEC 13211-1:1995 的 7.2.1 中，变量与两个不同变量的实现相关的情况的比较将如何结果尚不清楚:

7.2.1 Variable

If X and Y are variables which are not identical then
X term_precedes Y shall be implementation dependent
except that during the creation of a sorted list (7.1.6.5,
8.10.3.1 j) the ordering shall remain constant.

所以不清楚 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.

我并不是说这样做是可行的，但显然，这是可能的。

全排序是弱排序，集合 T 上的关键函数 f 和 f 的共域上的全排序 r， 定义 弱排序 wr(x, y) <==> r(f(x), f(y))。

(该上下文中函数的共域是函数返回的值的域。)

我可能完全错了，但是关系的存在需要 key 的存在:您可以根据另一个关系定义关系，但最终您必须比较也可以孤立存在的东西: key 。

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

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

比较谓词保持自己的状态；

您有提供比较功能但不提供关键功能的“不透明”对象(例如，在 C 中定义)。

无论哪种方式， predsort可能有用:没有人愿意 atom_neg/2 Will Ness 的解决方案。然而，它目前有一个严重的缺陷:它不允许稳定的排序。 SWI-Prolog 已经 can be used in this way ，只需将当前行为添加到 predsort/3 的规范和文档中即可。 .