按函子中的第二个原子对列表进行排序 [英] Sort a list by the second atom in functor

问题描述

我在序言中有此列表:

List = [functor(a,1),functor(n,7),functor(l,9),functor(k,0)]

，我想通过函子中的数字而不是字母对其进行排序. 我的意思是 sort(L,L1) 我会得到

and i want to sort it by the number in the functor instead of the letter. I mean if i do sort(L,L1) i will get

L1 = [functor(a,1),functor(k,0),functor(l,9),functor(n,7)]

但我希望它像

L1 = [functor(k,0),functor(a,1),functor(n,7),functor(l,9)]

有什么方法可以做到(不仅仅是重新创建并把数字放在首位)

is there any way of doing that (and not just recreate it and put the number first)

推荐答案

要重新创建"列表(种类如下):

To "recreate" the list (kind of):

?- List = [functor(a,1),functor(n,7),functor(l,9),functor(k,0)],
    map_list_to_pairs(arg(2), List, Pairs),
    keysort(Pairs, Sorted_pairs),
    pairs_values(Sorted_pairs, Sorted).
Pairs = [1-functor(a, 1), 7-functor(n, 7), 9-functor(l, 9), 0-functor(k, 0)],
Sorted = [functor(k, 0), functor(a, 1), functor(n, 7), functor(l, 9)].

请参见此处.鉴于您的实现具有library(pairs)，这可能是最惯用的"方法.如果不是这样，则此处使用的谓词几乎是微不足道的:请参见

See here. This is probably the most "idiomatic" way of doing it, given your implementation has a library(pairs). If it doesn't, the predicates used here are almost trivial to implement: see the library source.

如果您使用predsort，请参见问题评论.您可以定义一个辅助谓词，例如:

If you use predsort, see the question linked also in the comment. You can define a helper predicate like:

compare_2(Order, A, B) :-
    arg(2, A, A2),
    arg(2, B, B2),
    compare(Order, A2-A, B2-B).

(通过@false进行更正)

(correction by @false)

这将首先对第二个参数进行排序，如果相等，则对整个术语进行排序.

This will sort on the second argument first, and if these are equal, on the whole term.

?- List = [f(a,1),f(n,0),f(l,9),f(k,0)],
predsort(compare_2, List, Sorted).
List = [f(a, 1), f(n, 0), f(l, 9), f(k, 0)],
Sorted = [f(k, 0), f(n, 0), f(a, 1), f(l, 9)].

换句话说，它不是稳定排序".因此，实际上，最好使用keysort方法.

In other words, it is not a "stable sort". So actually, it is better to use the keysort approach.

请注意，此版本的compare_2仍会删除除第一次出现的相同术语以外的所有内容，因为这是predsort的作用:

Note that this version of compare_2 will still remove all but the first occurrence of identical terms, because this is what predsort does:

?- List = [f(a,1),f(n,0),f(l,9),f(n,0)],
predsort(compare_2, List, Sorted).
List = [f(a, 1), f(n, 0), f(l, 9), f(n, 0)],
Sorted = [f(n, 0), f(a, 1), f(l, 9)].

您可以通过定义已经对两个相等(但不相等)的元素进行排序来欺骗"它:

You can "cheat" it by defining that two elements that are equivalent (but not equal) are already sorted:

compare_2_stable(Order, A, B) :-
    arg(2, A, A2),
    arg(2, B, B2),
    compare(Order0, A2, B2),
    (   Order0 == (=)
    ->  Order = (<)
    ;   Order = Order0
    ).

?- List = [f(a,1),f(n,0),f(l,9),f(k,0)],
predsort(compare_2_stable, List, Sorted).
List = [f(a, 1), f(n, 0), f(l, 9), f(k, 0)],
Sorted = [f(n, 0), f(k, 0), f(a, 1), f(l, 9)].

?- List = [f(a,1),f(n,0),f(l,9),f(n,0)],
predsort(compare_2_stable, List, Sorted).
List = [f(a, 1), f(n, 0), f(l, 9), f(n, 0)],
Sorted = [f(n, 0), f(n, 0), f(a, 1), f(l, 9)].

请注意，我不确定这是否会真正保持等效元素(具有等于"第二项的元素)的原始顺序.对于该示例，它目前正在执行.仅当predsort将元素传递给比较谓词时将元素保持其原始顺序时，情况才会如此，这可能取决于实现(??).

Note that I don't know for sure if this will actually keep the original order of equivalent elements (elements with "equal" second terms). It does it at the moment, for that example. This will be the case only if predsort keeps the elements in their original order when it passes them to the comparison predicate, and this might depend on the implementation (??).

编辑:在SWI-Prolog中查看了predsort/3的源代码，是的，在SWI-Prolog中，对于当前的实现，最后的解决方案将提供与使用相同的解决方案keysort/2. 但是，除非您有实用理由，并且您愿意牺牲可移植性，否则您应该选择keysort/2.

EDIT: having looked at the source code of predsort/3 in SWI-Prolog, yes, in SWI-Prolog, with the current implementation, the last solution will give the exact same solution as using keysort/2. However, you should prefer keysort/2 unless you have a practical reason not to, and you are willing to sacrifice portability.

这篇关于按函子中的第二个原子对列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！