7

This is a followup to an answer to a question about sorting on a particular argument of a term, without creating a new list for a keysort (if I understood the original question correctly).

Say we wanted predsort/3 to behave exactly as sort/2: if I understand correctly, this would mean calling it as:

?- predsort(compare, List, Sorted).

Now say that we wanted to use predsort/3 to sort as implemented by msort/2 (see also this question). One way to do it would be to define a comparison predicate Pred(-Delta, +A, +B) that does not unify Delta with = when the elements are actually equal:

mcompare(Delta, A, B) :-
    compare(Delta0, A, B),
    (   Delta0 == (=)
    ->  Delta = (<)
    ;   Delta = Delta0
    ).

?- predsort(mcompare, List, Sorted).

Question: does that really simply sort without removing duplicates, as msort/2 does? It seems like it should.

Moving on: say we wanted to sort terms with arity > n, on the standard order of the nth argument in the term. The clean way to do it would be:

sort_argn(N, List, Sorted) :-
    map_list_to_pairs(arg(N), List, Pairs),
    keysort(Pairs, Sorted_pairs),
    pairs_values(Sorted_pairs, Sorted).

If we wanted to use predsort/3 to achieve the same effect, we could try using a comparison predicate as follows:

compare_argn(N, Delta, A, B) :-
    arg(N, A, AN),
    arg(N, B, BN),
    compare(Delta, AN-A, BN-B).

And to sort on the second argument:

?- predsort(compare_argn(2), List, Sorted).

However, this is not the same as sort_argn/3 above that uses keysort/2. It will remove duplicates, and it will order compound terms according to the standard order of the original full term if the second arguments of two terms happen to be equal:

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

Making the assumption that for every pair of A and B passed to the comparison predicate Pred(Delta, A, B), A comes before B in the original list. Can we define a comparison:

compare_argn_stable(N, Delta, A, B) :-
    arg(N, A, AN),
    arg(N, B, BN),
    compare(Delta0, AN, BN),
    (   Delta0 == (=)
    ->  Delta = (<)
    ;   Delta = Delta0
    ).

At this point, if and only if any two elements A and B are always passed to the comparison predicate in the same order as they were in the original list, this should behave identically to sort_argn/3 above:

?- predsort(compare_argn_stable(N), List, Sorted).

Now of course it is important that compare_argn_stable/4 unifies Delta with < when the two "keys" are equal. Furthermore, the behavior is implementation dependent, and only identical to the keysort example iff predsort/3 keeps the original order of elements when passing them to the comparison predicate.

Question Is that correct?

Question Is there any standard that covers this aspect of predsort/3?

Community
  • 1
  • 1

1 Answers1

4

Since no one has answered, and since I am quite certain about it now:

Yes, you could use predsort/3 to emulate any of the other sorts. The question describes in some detail how.

However: this is a bad idea for several reasons.

  • The "stability" depends on the implementation of predsort/3 (see the question)
  • The predsort/3 itself is not part of any standard (as far as I can tell)
  • The chances are, your Prolog implementation provides an msort/2 or keysort/2 that is far more efficient than predsort/3

There might be rare cases where the size of the elements of the list is much bigger than the length of the list we are sorting, and this little dance:

list_to_keyval_pairs(List, Pairs), % defined by the user as necessary
keysort(Pairs, Sorted_pairs),
pairs_values(Sorted_pairs, Sorted)

(see here) is actually more expensive (slower) than using predsort(keycmp, List, Sorted), with keycmp/3 defined by the user. Even then, the order of results with equivalent keys depends not only on the (user) definition of keycmp/3, but also on the implementation of predsort/3.

In other words, a "stable" sort with predsort/3 is a bad idea.

  • I have given you examples of a hypothetical sort that works for a total order but does not work for your order ; that is, a sort that in some place compares A with B and in others compares B with A assuming that they are the opposite to each other. So imagine, that this sort sorts with A, B and then checks with B, A. It would loop for `[a,a]` – false Feb 19 '15 at 10:05
  • @false Indeed. The (unwarranted) assumption that I am silently making throughout is that we are dealing with a `predsort` that keeps the original order of elements when passing them as the last two arguments to the first argument of `predsort/3`. I will incorporate this in my answer, if you don't feel like writing an answer yourself (which you will do better anyway). –  Feb 19 '15 at 12:51
  • 1
    Ideally, ask this question in a more general manner to get feedback from other groups on SO, but this **is** a big effort. I wanted once to extend a question to another language (SQL), but still have to found the time to make a good question... See: http://meta.stackoverflow.com/questions/280348/how-to-handle-cross-language-questions-correctly – false Feb 19 '15 at 13:04
  • @false Prolog is generic enough I guess; would it be enough to show a `predsort/3` implementation that works as I assumed (say a merge sort), and a `predsort/3` implementation that loops on a list like `[a,a]` (or something small enough)? Which sorting algorithm would be susceptible to this problem? –  Feb 19 '15 at 13:27
  • @false Anyway, I am finally starting to see the reason for my confusion: `predsort/3`, as defined in the SWI-Prolog implementation, is a stable sort in disguise: it is a merge sort that discards an element when the comparison returns `=`. There is no reason for a merge sort to do that, or to swap the order of elements during comparison. If I am not wrong, a quicksort has plenty of opportunities to swap elements, so it is not "stable" as such. –  Feb 19 '15 at 13:33
  • 1
    The counterexample I gave does no require that the sorting is not stable. It simply needs to change the operands from time to time. – false Feb 19 '15 at 14:12
  • Calls to `predsort/3` can be optimized in a similar way as calls to other meta-predicates such as `maplist/2`. Just a question of writing the necessary `goal_expansion/2` clauses and use them to expand the calls. – Paulo Moura Feb 19 '15 at 18:11
  • @PauloMoura If I understood the comments of Jan correctly (https://groups.google.com/d/msg/swi-prolog/2MYJHbemplk/8w5kWdlvPIMJ) there is a bigger issue WRT efficiency in SWI-Prolog: a C implementation sorts "in place", avoiding term copying (which is fundamental because of how the "virtual machine" of SWI-Prolog is implemented, I assume?) –  Feb 20 '15 at 07:14
  • @Boris Yes but `predsort/3` is found on several other Prolog implementations. Also in Logtalk (as `sort/3`). Hope to work in the optimization I suggested soon. – Paulo Moura Feb 20 '15 at 11:55