1

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)

ben
  • 1,064
  • 3
  • 15
  • 29
  • 1
    See this question and the accepted answer for several alternatives depending on what you want to achieve exactly: http://stackoverflow.com/questions/8247032/prolog-predsort-3-like-msort-2. There is also `keysort`: see http://www.swi-prolog.org/pldoc/doc_for?object=keysort/2 –  Jan 21 '15 at 15:15

1 Answers1

3

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.

Community
  • 1
  • 1
  • s(X) for the first answer. `predsort/3` is very error prone, the example you give is excellent but it is not about two different functors, rather about two identical functors but different first argument. You can improve `compare_2/3` though. – false Jan 21 '15 at 15:57
  • `compare_2_i(Ord, A,B) :- arg(2, A, A2), arg(2, B, B2), compare(Ord,A2-A,B2-B).` Not clear what recreate means. I would say it rather means use `functor(2,a)` in place of `functor(a,2)`. At least, `A2-A` does not "recreate" `A`, for `A` is there entirely unmodified. – false Jan 21 '15 at 16:23
  • `compare_2_stable/3` is not a total order. So whatever you get form sorting might happen to work, but this looks extremely brittle. Think of `A=f(1,a), B=f(2,a), compare_2_stable(<,A,B),compare_2_stable(<,B,A)` – false Jan 21 '15 at 16:44
  • The example I gave shows it is no order at all. So it depends on precisely the way the sorting algorithm will use it whether or not sort will be a stable sort or not. And that might be the case, but it is difficult to ensure. – false Jan 21 '15 at 17:56
  • A stable sort guarantees that elements that compare equal will appear in exactly the same order. No more, no less. But your comparison predicate never concludes that two elements are equal. So I can imagine a stable sort that will not give the result you like: Think of a sort that sometimes uses `call(C_3, R, A,B)` and sometimes `call(C_2,R,B,A)` (by unfolding the sort) = then you definitely are no longer sorting in a stable manner. – false Jan 21 '15 at 17:59
  • Your claim that "it will just sort them by the second argument of the term, and leave terms with equal second arguments in their original order" might hold in **this particular** implementation of `predsort/3`. But it definitely does not hold in all stable implementations of `predsort/3`. In case you are not convinced, make a new question – false Jan 21 '15 at 18:14
  • Could you simplify the problem? In fact it seems to be sufficient to consider: `newcompare(R, A,B) :- compare(R0, A,B), (R0 == (=) -> R = (<) ; R = R0 ).` – false Jan 21 '15 at 18:23