`predsort/3` 的可能行为

Question

这是 answer 的后续问题，该问题是关于对术语的特定参数进行排序，而不为 keysort 创建新列表（如果我正确理解了原始问题） .

假设我们希望 predsort/3 的行为与 sort/2 完全相同：如果我理解正确，这意味着将其称为：

?- predsort(compare, List, Sorted).

现在说我们想使用 predsort/3 来排序，正如 msort/2 所实现的那样（另见 question）。一种方法是定义一个比较谓词 Pred(-Delta, +A, +B)，当元素实际上相等时，它不会统一 Delta 和 =：

mcompare(Delta, A, B) :-
    compare(Delta0, A, B),
    (   Delta0 == (=)
    ->  Delta = (<)
    ;   Delta = Delta0
    ).

?- predsort(mcompare, List, Sorted).

问题：这真的像msort/2那样简单排序而不删除重复项吗？好像应该的。

继续：假设我们想要对 arity > n 的项进行排序，按照项中第 n 个参数的标准顺序。干净的方法是：

sort_argn(N, List, Sorted) :-
    map_list_to_pairs(arg(N), List, Pairs),
    keysort(Pairs, Sorted_pairs),
    pairs_values(Sorted_pairs, Sorted).

如果我们想用predsort/3达到同样的效果，我们可以尝试使用比较谓词如下：

compare_argn(N, Delta, A, B) :-
    arg(N, A, AN),
    arg(N, B, BN),
    compare(Delta, AN-A, BN-B).

并根据第二个参数排序：

?- predsort(compare_argn(2), List, Sorted).

但是，这与上面使用 keysort/2 的 sort_argn/3 不同。它将删除重复项，如果两个术语的第二个参数恰好相等，它将根据原始完整术语的标准顺序对复合术语进行排序：

?- predsort(compare_argn(2), [f(b,2), f(a,1), f(a,1), f(a,2)], Sorted).
Sorted = [f(a, 1), f(a, 2), f(b, 2)].

?- sort_argn(2, [f(b,2), f(a,1), f(a,1), f(a,2)], Sorted).
Sorted = [f(a, 1), f(a, 1), f(b, 2), f(a, 2)].

做出假设，对于传递给比较谓词 Pred(Delta, A, B)、A 的每一对 A 和 B在原始列表中出现在 B 之前。我们可以定义一个比较吗：

compare_argn_stable(N, Delta, A, B) :-
    arg(N, A, AN),
    arg(N, B, BN),
    compare(Delta0, AN, BN),
    (   Delta0 == (=)
    ->  Delta = (<)
    ;   Delta = Delta0
    ).

此时，当且仅当任何两个元素A和B总是以与它们相同的顺序传递给比较谓词在原始列表中，这应该与上面的 sort_argn/3 相同：

?- predsort(compare_argn_stable(N), List, Sorted).

现在当然重要的是 compare_argn_stable/4 统一 Delta 和 < 当两个 "keys" 相等时。此外，该行为取决于实现，并且仅与 keysort 示例相同，当且仅当 predsort/3 在将元素传递给比较谓词时保持元素的原始顺序。

问题正确吗？

问题有没有涵盖这方面的标准predsort/3?

Answer 1

因为没有人回答，而且我现在很确定：

是的，您可以使用 predsort/3 来模拟任何其他类型。这个问题详细描述了如何。

但是：出于几个原因，这是一个坏主意。

"stability" 取决于 predsort/3 的实现（见问题）
predsort/3 本身不是任何标准的一部分（据我所知）
很有可能，您的 Prolog 实现提供了比 predsort/3

msort/2

keysort/2

可能很少有列表元素的大小比我们正在排序的列表的长度大得多的情况，这个小舞蹈：

list_to_keyval_pairs(List, Pairs), % defined by the user as necessary
keysort(Pairs, Sorted_pairs),
pairs_values(Sorted_pairs, Sorted)

(see here) 实际上比使用 predsort(keycmp, List, Sorted) 更昂贵（更慢），其中 keycmp/3 由用户定义。即便如此，具有等效键的结果顺序不仅取决于 keycmp/3 的（用户）定义，还取决于 predsort/3.

的实现

换句话说，"stable" 排序 predsort/3 是个坏主意。

`predsort/3` 的可能行为

Possible behaviors of `predsort/3`

sorting

compare

list

prolog

stable-sort