`predsort/3`的可能行为

Question

`predsort/3`的可能行为

7

这是关于在Prolog中按特定参数对项进行排序而不创建新列表keysort的问题的一个答案后续。

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

?- predsort(compare, List, Sorted).

现在假设我们想要使用msort/2实现的方式来使用predsort/3进行排序(参见此问题)。一种方法是定义一个比较谓词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 和 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统一为<是非常重要的。此外，其行为取决于实现，并且仅在predsort/3将元素传递到比较谓词时保留原始顺序时才与keysort示例相同。 问题：这样正确吗？ 问题：是否有任何标准涵盖了predsort/3的这个方面？

- user1812457

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1812457 · Accepted Answer

由于没有人回答，而我现在非常确定：

是的，您可以使用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)

(请点击此处)使用predsort(keycmp, List, Sorted)比使用keysort/2更加高效。其中，keycmp/3由用户定义。即使这样，具有等价键的结果顺序不仅取决于keycmp/3的(用户)定义，还取决于predsort/3的实现。

换句话说，使用predsort/3进行“稳定”排序是不明智的。