Sort a list by the second atom in functor

Question

I have this list in prolog:

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

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)]

but i want it to be like

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)

Answer 1

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)].

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.

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).

(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)].

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

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)].

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 (??).

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.