16

ISO-Prolog provides sort/2 and keysort/2 which relies on term order (7.2) often called "standard term order". The common way to sort a list with a different order is to map each element El of that list somehow to a list of pairs XKey-El and then sort that list, and finally project the keys away. As an example consider how keysort/2 can be expressed in terms of sort/2 (See the note for an implementation).

In many situations this approach is much faster than using a generic implementation specific sorting predicate that relies on a user defined order as SWI's predsort(C_3, List, SortedList) or SICStus' samsort(O_2, List, SortedList).

My question boils down to:

Are there cases where a sorting using predsort/3 resp. samsort/3 cannot be replaced by some mapping, sort/2-ing and projecting?1

And for the sake of clarity, better stick to finite, ground terms. For, infinite ground terms do no possess a total, lexicographic order as it would be needed as an extension of the finite case ; and further, it is not clear how the comparison of variables with the case of two different variables being implementation dependent will turn out given 7.2.1 of ISO/IEC 13211-1:1995:

7.2.1 Variable

If X and Y are variables which are not identical then
X term_precedes Y shall be implementation dependent
except that during the creation of a sorted list (7.1.6.5,
8.10.3.1 j) the ordering shall remain constant.

So it is not clear whether predsort/3 would still qualify as a creation of a sorted list. What is clear is that the ordering remains constant during sort/2 and keysort/2.

1 Thanks to @WillNess, this projection should at least include also reverse/2 — or any linear transformation. It also means that results with both duplicates and unique ones can be implemented (similarly to the way keysort/2 is implemented).

false
  • 10,264
  • 13
  • 101
  • 209
  • If we define "X term_precedes Y" as a non-transitive relation, the `predsort` will give different results depending on the initial input order. – Eugene Sh. Jul 22 '15 at 20:34
  • @EugeneSh. A `keysort` will also give different results on permutations of a list with _equivalent_ elements, as in `keysort([a-b,a-c], Sorted)` vs. `keysort([a-c,a-b], Sorted)`, even though equivalence is transitive. –  Jul 23 '15 at 10:15
  • @EugeneSh.: In other words: any relation that does not implement a total order, be it not transitive, or anything else, will not work with `predsort/3`! So you will get quasi-random results with it. Compared to that the other approach will give similarly random results. – false Jul 23 '15 at 11:51

3 Answers3

4

First off, you can "negate" Prolog atoms. Let's call it atom_neg/2 (it is a silly name, but it does something silly anyway):

atom_neg(A, NK) :-
    atom_codes(A, Cs),
    maplist(negate, Cs, NCs),
    append(NCs, [0], NK).

negate(X, N) :- N is -X.

I am not claiming it is practical to do this, but apparently, it is possible.

A total ordering is a weak ordering, and a key function f on a set T together with a total ordering r on the codomain of f, define a weak ordering wr(x, y) <==> r(f(x), f(y)).

(Codomain of a function in that context is the domain of the values that the function returns.)

I might be totally wrong, but the existence of a relation requires the existence of a key: you can define a relation in terms of another relation, but eventually you must compare something that can exist in isolation as well: the key.

The point here is that the key does not need to be in the same domain as the thing we want to sort, and that a weak ordering (a relation) is defined for objects of the same domain. Prolog does something weird here: it defines a standard order of terms for all possible terms. Prolog also does not have a proper notion of "types", or "domains". My gut feeling tells me that sorting things that do not belong to the same domain is simply not very useful, but Prolog obviously disagrees.

You can not define a key function for two cases:

  1. The comparison predicate keeps its own state;
  2. You have "opaque" objects (defined in C, for example) that provide the comparison function but not a key function.

Either way, predsort can be useful: no one would prefer atom_neg/2 over the solution by Will Ness. However, it has one serious defficiency at the moment: it does not allow for a stable sort. The SWI-Prolog already can be used in this way, all it takes would be to add the current behavour to the specification and documentation of predsort/3.

Community
  • 1
  • 1
  • 1
    this all started at http://stackoverflow.com/questions/31571094/sort-a-list-by-polar-angle-in-counterclockwise-order-in-prolog/31571618#comment51101235_31571618 , it was about sorting with some primary and secondary comparison criteria, and the Decorate-Sort-Undercorate pattern. so standard order of terms is useful in that situation. your atom negation disproves my answer in that respect (that it's impossible and we must use reverse/2). the D-S-U is important when the comparison predicate is slow - it replaces loglinear number of comparisons with liner number of key constructions. – Will Ness Jul 25 '15 at 10:52
  • 1
    Yes atom_neg/2 works, since 0 is below a cons cell. We have therefore ?- sort([[x,x,0],[x,0]],X). X = [[x,0],[x,x,0]]. For compounds to mirror sort you can also use lists, but instead of 0 you need something above cons cell. For example '.'('','',''). We would then have: ?- sort([[x,x,'.'('','','')],[x,'.'('','','')]],X). X = [[x,x,'.'('','','')],[x,'.'('','','')]] –  Jul 25 '15 at 14:46
  • 1
    The D-S-U pattern could be provided in a library by a new predicate collatesort/3 that similarly to predsort/3 takes a closure argument. But this time the closure is not doing a comparison but calculating a key. –  Jul 25 '15 at 14:54
  • 1
    @j4nbur53 There are several issues here. One is that `predsort/2` is, in my opinion, a useful predicate, but the original question by false feels a bit like an attempt to show that it is not. Another is that `predsort/2` can be made more useful; I think I have outlined how. Yet another is that the semantics of the traditional Prolog `sort/2` are more specific than the very general name suggests. Just a few thoughts. –  Jul 25 '15 at 18:33
  • W.r.t: Negating atoms: Your idea is really nice, but you then have to consistently map other terms accordingly. – false Jul 26 '15 at 22:41
  • @false I would not do this in practice. The only point was that it is not impossible. –  Jul 27 '15 at 05:52
3

edit: the answer by @Boris shows how to "negate" atoms for the purposes of comparison, so it invalidates my contr-argument in that case. And the new stipulation in the question invalidates it entirely.

In case of complex sorting criteria, multiple sub-keys will have to be arranged. If retention of duplicates is desired, incrementing indices should be prefixed to the original term, following the sorting subkeys, in terms constructed for sort/2 to sort.

The complexity and number of the constructed subkeys can get out of hand though. Imaging sorting points by X first, then by Y, in ascending or descending orders in some regions, and by Y first, and by X second, in others.

Then the sought for advantage of replacing the loglinear number of (presumably computationally heavy) comparisons with only a linear number of key constructions and a loglinear number of (presumably light) comparisons in standard order of terms, can disappear.

Trivially, predsort/3ing e.g. a list of atoms in reverse, with custom comparison predicate

comp(<,A,B):- B @< A.

etc., can't be done by sort/2ing which works in "standard order of terms" (quoting SWI documentation). With numbers, we could flip the sign, but not with names.

Perhaps you'd want to add reverse to the allowed actions.

With sort/4 allowed, I don't see anything that wouldn't work. And since it's stable, secondary criteria can be accommodated as well, by the secondary passes (first by a minor, then by a major criterion).

Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Wanted to give the same answer, with comp(D,A,B) :- compare(D,B,A). Also allowing reverse/2 doesn't solve the problem, since the comparison predicate could do any slice and dice, which is much more complicated. –  Jul 23 '15 at 22:42
  • @j4nbur53 your `comp` is of course much better. the "slice and dice" is presumably using several criteria, like sorting by Xs but if equal then by Ys? I thought I addressed it in the last sentence? (then of course it needs `sort/4`...) – Will Ness Jul 23 '15 at 22:47
  • sort/4 seems to generalize sort, msort and keysort. I think predsort can still do more. Slice and dice means for a example a value subrange is sorted B @< A and another value subrange on the same attribute is sorted A @< B, you can't do that with a simple sort and reverse combination. –  Jul 23 '15 at 22:49
  • @j4nbur53 you can, with multiple subkeys. let's say we sort random numbers in [1..10] ascending, but if both numbers are in [3..8], then we swap the order, right? then for x in [1..3] the value is `x-0`, for x in [3..8] it's `5-x`, for [8..10] it's `x-0`. then we sort descending by second subkey, then ascending by the first. -- see also [this comment](http://stackoverflow.com/questions/31571094/sort-a-list-by-polar-angle-in-counterclockwise-order-in-prolog/31571618#comment51099973_31571618) by Eugene Sh. – Will Ness Jul 23 '15 at 23:01
  • ... [this comment](http://stackoverflow.com/questions/31571094/sort-a-list-by-polar-angle-in-counterclockwise-order-in-prolog/31571618#comment51099973_31571618) by Eugene Sh. which seems to prove the existence of such mapping, from the general argument. – Will Ness Jul 23 '15 at 23:07
  • 1
    s(X). Your example shows that my question was not posed in the very best manner. I think you will agree that nobody will say: We need `predsort/3` for this example. – false Jul 23 '15 at 23:51
  • @false of course. that's what I meant by referring to `reverse/2`. But what about `sort/4`? Would you allow it too? Then the question really becomes non-trivial. – Will Ness Jul 24 '15 at 08:37
  • But sort/4 is very similar too, you can assemble a key that will be used for sort/2-ing. Am I missing something essential? – false Jul 24 '15 at 10:14
  • @false sort/4 allows to specify descending order; how can I do this with sort/2? I thought it was impossible, with sort/2. – Will Ness Jul 24 '15 at 10:43
  • @WillNess: But that's what we have just discussed before. Is there anything else to it? – false Jul 24 '15 at 11:03
  • Eugene Sh: I am of course refering to an attribute whos value range is an atom. WillNess already pointed out that for atoms negation doesn't work. For atoms you can also define sub ranges, i.e. for example all atoms starting with character a-k and all atoms starting with character l-z would be two such ranges. –  Jul 24 '15 at 11:08
  • @false ah, you mean if we allow for intervening reverses between the several runs of sort/2 (and mappings, to shuffle the subkeys into proper positions), then we don't need sort/4... then yes, sort/4 is just convenience, it seems. – Will Ness Jul 24 '15 at 17:32
  • @WillNess: Why several runs? I just thought of one, seems I am missing something with sort/4. – false Jul 24 '15 at 18:41
  • @false for context see my above [comment](http://stackoverflow.com/questions/31573197/sort-2-keysort-2-vs-samsort-3-predsort-3/31599195?noredirect=1#comment51150515_31599195). I haven't tried running any code though, to test this. – Will Ness Jul 24 '15 at 19:20
  • 1
    @j4nbur53 and others: of course one can define "negation" for atoms or arbitrary strings of characters. See my answer. –  Jul 25 '15 at 09:50
  • How about negation of terms? –  Jul 25 '15 at 14:22
  • @j4nbur53 presumably we can always encode non-cyclic terms as finite lists of atoms and numbers... I haven't thought it fully through obviously... – Will Ness Jul 25 '15 at 14:34
  • Still not sure whether any comparison has a key equivalent. –  Jul 25 '15 at 15:00
  • @j4nbur53 this might be a good question for http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/. – Will Ness Jul 25 '15 at 15:20
2

I think I might have a proper answer to your question.

If you have a partial ordering, you can still try and sort using predsort/3, and you might get a better result than just saying "a total ordering does not exist."

Here is an example: say you have a game played by two teams. Each play gives a point to only one of the teams, and you play until one team reaches a certain number of points.

Now, you organize a tournament, and it has a group stage, in groups of 4 teams, which is a round-robin. Only the two top teams make it out of the groups.

For each game played, teams get a score of own_points - other_teams_points. In other words, if you play to 7, and the final score is:

Team A - 5:7 - Team B

them Team A scores -2 and Team B scores 2.

At the end of the group stage, you order the teams by:

  1. Total score
  2. If the total score is the same, the team that won the direct fight is ordered higher.

Most notably, using this scoring scheme, you cannot resolve a three-way draw if Team A beat Team B, Team B beat Team C, and Team C beat Team A. A "stable" sort makes no sense in this context.

However, using predsort/3, you can attempt to find the two top teams, and you will get a definitive answer in most cases. Resolving a three-way draw as above is usually resolved using a coin-toss.