`predsort / 3'的可能行为 [英] Possible behaviors of `predsort/3`
问题描述
这是对回答关于对某个术语的特定参数排序的问题，而不为 keysort 创建新列表（如果我理解原始问题正确）。
假设我们想要 predsort / 3 2 ：如果我理解正确，这意味着调用它：
？ - predsort ，List，Sorted）。
现在我们想使用 predsort / 3 按 msort / 2 实现排序（另请参见问题）。一种方法是定义一个不能统一 Delta Pred（-Delta，+ A，+ B） c $ c> = 当元素实际上相等时：
mcompare（Delta，A，B）： -
compare（Delta0，A，B），
（Delta0 ==（=）
- Δ b; Delta = Delta0
）。
？ - predsort（mcompare，List，Sorted）。
问题：确实很简单地排序而不删除重复项，因为 msort / 2 有吗？它似乎应该这样。
继续：我们想按照术语中第n个参数的标准顺序对arity> n进行排序。干净的方法是：
sort_argn（N，List，Sorted）： -
map_list_to_pairs （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），
比较（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 = [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 = [f（a，1），f（a，1），f（b，2），f（a，2）]。
对传递给比较谓词 Pred（Delta，A，B）的和 B A 在原始列表中的 B 之前。我们可以定义比较：
compare_argn_stable（N，Delta，A，B）： -
arg A，AN），
arg（N，B，BN），
（Delta0，AN，BN），
（Delta0 ==（=）
- =（<）
; Delta = Delta0
）。
此时，当且仅当 $ c> A 和 B 始终以与原始列表中相同的顺序传递到比较谓词，这应该与 sort_argn / 3 上面：
？ - predsort（compare_argn_stable ，List，Sorted）。
现在当然， compare_argn_stable / 4 当两个键相等时，将与 keysort 示例iff predsort / 3 相同才保持原始顺序
> 问题是否有涵盖 predsort / 3 这一方面的标准？
因为没有人回答，因为我现在很确定：
是的，你可以使用 predsort / 3 以模拟任何其他排序。
- 稳定性取决于
predsort / 3（见问题）的实现 -
predsort / 3本身不是任何标准的一部分（据我所知） - ，您的Prolog实现提供
msort / 2或keysort / 2，远远高于predsort / 3
在很少的情况下，列表元素的大小大于我们排序的列表的长度，这个小舞：
list_to_keyval_pairs用户必要的
keysort（Pairs，Sorted_pairs），
pairs_values（Sorted_pairs，Sorted）
$ b b
（参见这里）其实更贵（慢于）使用 predsort（keycmp，List，Sorted）与用户定义的 keycmp / 3 即使这样，使用等价键的结果顺序不仅取决于 keycmp / 3 的（用户）定义，还取决于 predsort / 3 。
换句话说，使用 predsort / 3 是一个坏主意。
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).
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).
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).
Question: does that really simply sort without removing duplicates, as msort/2 does? It seems like it should.
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).
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).
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)].
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
).
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).
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.
Question Is that correct?
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:
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.
- The "stability" depends on the implementation of
predsort/3(see the question) - The
predsort/3itself is not part of any standard (as far as I can tell) - The chances are, your Prolog implementation provides an
msort/2orkeysort/2that is far more efficient thanpredsort/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)
(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.
In other words, a "stable" sort with predsort/3 is a bad idea.
这篇关于`predsort / 3'的可能行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
