`predsort/3` 的可能行为 [英] Possible behaviors of `predsort/3`

问题描述

这是 回答关于对术语的特定参数进行排序的问题，而不为 keysort 创建新列表(如果我正确理解了原始问题).

This is a followup to an answer to a question about sorting on a particular argument of a term, without creating a new list for a keysort (if I understood the original question correctly).

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

Say we wanted predsort/3 to behave exactly as sort/2: if I understand correctly, this would mean calling it as:

?- predsort(compare, List, Sorted).

现在说我们想使用 predsort/3 来按照 msort/2 的实现进行排序(另请参阅此 问题).一种方法是定义一个比较谓词 Pred(-Delta, +A, +B) 不统一 Delta 与 = 当元素实际上相等时:

Now say that we wanted to use predsort/3 to sort as implemented by msort/2 (see also this question). One way to do it would be to define a comparison predicate Pred(-Delta, +A, +B) that does not unify Delta with = when the elements are actually equal:

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

?- predsort(mcompare, List, Sorted).

问题:真的像 msort/2 那样简单地排序而不删除重复项吗?好像应该这样.

Question: does that really simply sort without removing duplicates, as msort/2 does? It seems like it should.

继续:假设我们想按照术语中第 n 个参数的标准顺序对 arity > n 的术语进行排序.干净的方法是:

Moving on: say we wanted to sort terms with arity > n, on the standard order of the nth argument in the term. The clean way to do it would be:

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

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

If we wanted to use predsort/3 to achieve the same effect, we could try using a comparison predicate as follows:

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

对第二个参数进行排序:

And to sort on the second argument:

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

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

However, this is not the same as sort_argn/3 above that uses keysort/2. It will remove duplicates, and it will order compound terms according to the standard order of the original full term if the second arguments of two terms happen to be equal:

?- 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 之前.我们可以定义一个比较:

Making the assumption that for every pair of A and B passed to the comparison predicate Pred(Delta, A, B), A comes before B in the original list. Can we define a comparison:

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 相同:

At this point, if and only if any two elements A and B are always passed to the comparison predicate in the same order as they were in the original list, this should behave identically to sort_argn/3 above:

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

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

Now of course it is important that compare_argn_stable/4 unifies Delta with < when the two "keys" are equal. Furthermore, the behavior is implementation dependent, and only identical to the keysort example iff predsort/3 keeps the original order of elements when passing them to the comparison predicate.

问题正确吗?

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

Question Is there any standard that covers this aspect of predsort/3?

推荐答案

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

Since no one has answered, and since I am quite certain about it now:

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

Yes, you could use predsort/3 to emulate any of the other sorts. The question describes in some detail how.

但是:这是一个坏主意，原因有很多.

However: this is a bad idea for several reasons.

• 稳定性"取决于 predsort/3 的实现(见问题)
• predsort/3 本身不是任何标准的一部分(据我所知)
• 很有可能，您的 Prolog 实现提供了一个比 predsort/3 更高效的 msort/2 或 keysort/2/li>

• The "stability" depends on the implementation of predsort/3 (see the question)
• The predsort/3 itself is not part of any standard (as far as I can tell)
• The chances are, your Prolog implementation provides an msort/2 or keysort/2 that is far more efficient than predsort/3

在极少数情况下，列表元素的大小比我们正在排序的列表的长度大得多，这个小舞会:

There might be rare cases where the size of the elements of the list is much bigger than the length of the list we are sorting, and this little dance:

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的实现.

(see here) is actually more expensive (slower) than using predsort(keycmp, List, Sorted), with keycmp/3 defined by the user. Even then, the order of results with equivalent keys depends not only on the (user) definition of keycmp/3, but also on the implementation of predsort/3.

换句话说，使用 predsort/3 的稳定"排序是个坏主意.

In other words, a "stable" sort with predsort/3 is a bad idea.

这篇关于`predsort/3` 的可能行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！