这是 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
的这一方面? ?
最佳答案
既然没有人回答,而且我现在很确定:
是的,您可以使用 predsort/3
模仿任何其他类型。该问题详细描述了如何。
然而 : 这是一个坏主意,原因有几个。
predsort/3
的实现(见问题)predsort/3
本身不属于任何标准(据我所知)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
进行“稳定”排序是个坏主意。
关于list - `predsort/3` 的可能行为,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28076715/