“predsort/3”的可能行为

Question

这是对有关对术语的特定参数进行排序的问题的后续，而无需为keysort创建新列表（如果我正确理解原始问题）。

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

?- predsort(compare, List, Sorted).

现在假设我们想使用 predsort/3 来排序，如 msort/2 实现的那样（另请参阅此问题）。一种方法是定义一个比较谓词Pred(-Delta, +A, +B)，当元素实际上相等时，该谓词不会将Delta与=统一起来：

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

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

继续：假设我们想按照术语中第 n 个参数的标准顺序对术语进行 arity> 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和B，A在原始列表中都排在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与<统一起来是很重要的。此外，该行为依赖于实现，并且仅与 iff keysort示例相同predsort/3在将元素传递给比较谓词时保持元素的原始顺序。

问题 这是对的吗？

问题 是否有任何标准涵盖predsort/3的这一方面？

Answer 1

既然没有人回答，而且我现在很确定：

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

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

• "稳定性"取决于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)

（

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

换句话说，具有predsort/3的"稳定"排序是一个坏主意。