'predsort/3`的可能行为

Question

这是关于对术语的特定参数进行排序的问题的答案的后续,而没有为a创建新列表keysort(如果我正确理解原始问题).

假设我们想predsort/3表现得如下sort/2:如果我理解正确,这将意味着将其称为:

?- predsort(compare, List, Sorted).

现在说我们想用它predsort/3来实现排序msort/2(参见这个问题).一种方法是定义一个比较谓词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统一它是很重要的.此外,行为是依赖于实现的,并且仅与示例iff 相同,iff 在将元素传递给比较谓词时保持元素的原始顺序.Delta<keysortpredsort/3

问题是对的吗？

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

Answer 1

既然没有人回答，而且我现在对此非常确定：

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

然而：由于多种原因，这是一个坏主意。

• “稳定性”取决于实施predsort/3（参见问题）
• 它predsort/3本身不属于任何标准（据我所知）
• 很可能，您的 Prolog 实现提供了一个msort/2比keysort/2predsort/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)）实际上比使用keycmp/3由用户定义的更昂贵（更慢） 。即使如此，具有等效键的结果的顺序不仅取决于 的（用户）定义keycmp/3，还取决于 的实现predsort/3。

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