list - `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做？好像应该。

继续:假设我们想按照术语中第 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).

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

?- 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)].

假设对于每对 A和 B传递给比较谓词 Pred(Delta, 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与 <当两个“键”相等时。此外，该行为取决于实现，并且仅与 keysort 相同。示例 iff predsort/3将元素传递给比较谓词时保持元素的原始顺序。

问题 那是对的吗？

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

Answer 1

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

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

然而 : 这是一个坏主意，原因有几个。

“稳定性”取决于 predsort/3 的实现(见问题)

predsort/3本身不属于任何标准(据我所知)

很有可能，您的 Prolog 实现提供了 msort/2或 keysort/2这比 predsort/3 高效得多

可能在极少数情况下，列表元素的大小远大于我们正在排序的列表的长度，还有这个小舞:

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 .

换句话说，使用 predsort/3 进行“稳定”排序是个坏主意。