Order and sorting

Help! Algorithm
1

Disclaimer: I seem to have a preoccupation with ordering and sorting; I have managed to not let it influence my daily life too badly. I lived in Germany once but I left the country.

This topic pops up periodically. This time it is the library(ordsets) and multisets discussion. This is not an exclusive list.

Back from 2015, when discussing the then new library(solution_sequences), on the old forum:

On 02/13/2015 02:54 PM, Boris Vassilev wrote:

On Fri, Feb 13, 2015 at 3:45 PM, Jan Wielemaker <J.Wielemaker@vu.nl
mailto:[J.Wielemaker@vu.nl](mailto:J.Wielemaker@vu.nl)> wrote:

As defined, predsort/3 removes duplicates, so stable has no meaning …

You can trick it into doing a stable sort. Just unify Delta with <
when the keys are equivalent, instead of =. This relies on predsort/3
keeping the original order of pairs of elements when comparing them. The
current implementation of predsort/3 does that, but of course this is
not a requirement, so I know it should not be done.

Didn’t know that :slight_smile:

Cheers — Jan

I provided the trivial solution in this post:

equivalence_compare(Order, X, Y) :-
    compare(Order0, X, Y), 
    (   Order0 == '='
    ->  Order = '<'
    ;   Order0 = Order
    ).

At that time I had accepted that keeping the original order of equivalent elements is not in the specification of predsort/3. The following still holds true:

  • The predsort/3 implementation uses a merge sort.
  • A merge sort can be made stable in respect to the order of the input list without any additional logic (just don’t swap the order of the inputs unnecessarily).
  • In Prolog (and for linked lists in general), merge sort is a better algorithm than for example quicksort (which is not stable).

Both sets and multisets have a well-defined representation as a sorted list; the difference is whether it is the result of sort/2 (set) or msort/2 (multiset).

Right now I suspect that the widely accepted, “textbook” algorithms that work on Prolog “sets” are by definition correct also for “multisets”. It will take me some days or weeks to convince myself that this is true.

I am posting this in the hope that someone on the forum already knows that as a fact and can provide a proof, for example in the form of a reference to an external source; or correct my misunderstanding.

I am definitely not suggesting to change the spec or implementation of any library predicate.

3

I went on wikipedia to remind myself of the meaning of a “stable sort” and I found this gem:

Stability: stable sorting algorithms maintain the relative order of records with equal keys (i.e., values).

Keys, i.e. values. Oh, wikipedia.

4

To be fair, the sorting algorithm sorts the keys for key-sort of key-value pairs but sorts values for a list of values. :slight_smile: (The latter is something of a tautology)

5

This is a matter of terminology. I will now write a quote that I can’t be bothered to cite but it should give you an idea:

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) \Leftrightarrow r(f(x), f(y)).

“Codomain” is apparently the domain of the function return value.

The way I understand this is that if a list of Things can be sorted (somehow), this also means that you can define a function that takes any one Thing and returns a key that has a well-defined order.

(Edit: “sorted somehow” is of course hand-waiving. What it really means is that there is a relation function, wr above, which is defined for any pair of elements. Relation here means something like “smaller than”.)

One consequence of the above is that if you can define a comparison predicate and give it to predsort/3, you can achieve the exact same result by applying a function to each of your elements (values), sort on the key with keysort/2, and retrieve the sorted elements.

7

I am not sure how this matters, because I am not sure what you mean when you say object. Do you mean a thing which has a lifetime and a state?

Doesn’t cmp_to_key() do the exact opposite? It is not cmp_FROM_key… You provide a key function (the f above) and you use that key to define the relation (the wr above) so that you can pass it to a predsort/3-like sorted()? This is trivial to implement it seems.

When you say “bootstrapped” I assume you mean “predsort defined in terms of keysort”? But keysort/2 is just a special case of sort with a predefined key function. So, you can define keysort in terms of predsort:

my_keysort(Pairs, Sorted) :-
    predsort(key_cmp, Pairs, Sorted).
key_cmp(Order, A-_, B-_) :-
    compare(Order0, A, B),
    (   Order0 == '='
    ->  Order = '<'
    ;   Order = Order0
    ).

Seems to work but I’d be glad to be proven wrong:

104 ?- my_keysort([z-bar, a-foo, a-bar], Sorted).
Sorted = [a-foo, a-bar, z-bar].

[EDIT] I agree that generating the key function from the comparison function/predicate is non-trivial. I have to think about it for a moment.

9

OK, I now understand what you mean. But take a look at this. To me it seems like they are cheating :smiley: this is not the same as defining predsort/3 in terms of keysort/2, right?

[EDIT] I see your edits. Yes, this is not the same. I will still have to think for a moment for bootstrapping predsort/3 from keysort/2.

11

Yes, I think I understand how Python works (but then again who knows :smiley: )

I am not sure why would there be “no objects in standard Prolog”. It really depends on your definition of object. Just because it doesn’t use the same techniques as Java or Python doesn’t mean you cannot achieve the same outcomes.

Nothing stops you from having state and behavior embedded within compound terms. It is quite useless but surely not difficult?

13

Yes, but this is most definitely not what the definition of cmp_to_key() does. It does not generate a key function, it calls the comparison function when the keys are compared, unless I am completely misreading this???

14

Yes, fully agree. There is no misunderstanding here on my side at least.

16

Well well I thought we live in a free country. I use bold differently from you but I can surely accommodate you. If I want emphasis, is italics OK with you?

Yes, I already did those things. I am starting to think we are getting stuck in semantics here.

18

my oh my. ok then, i drop the capitals too. i used to think that it’s ok to type ok with two big letters. in fact, when i type it with small letters the over-eager spell-checker on my browser underlines it red but this doesn’t bother me too much.

we drifted veeery far off-topic (i hope letter repeats are acceptable) and i am afraid we might get a warning. i at least really appreciate the discussion so far.

just to get this straight: it seems to me that cmp_to_key() takes the comparison function and applies it whenever the sort() needs to compare two keys. this seems different from taking a comparison function and somehow generating a key function from it. it feels as if this happens but “under the hood” it is just applying the comparison function. unless of course i am misreading the code.

21

I don’t know if that’s what they meant. In that case they would have said “keys (or values”) not “keys (i.e. values)”.

Thanks. I hadn’t thought about a formal definition of sorting, but of course one exists. I think that sounds a bit complicated though, especially when it defines such a simple concept as sorting to some total (or I guess partial) order. If you asked me to come up with a definition of sorting I’d have tried to say something like “a function that maps the elements of a set to the elements of a set of ordinals”. But I guess there must be details I haven’t thought of.

22

Just a guess: It might be that a certain formalism is better suited for constructive proofs about the problem. Such constructive proofs are far more useful for developing algorithms that are meant to be executed on a machine.

23

I think the proofs come after the algorithms, usually. I do usually scratch up my algos in a semi-formal notation before I hack at my code, but I don’t think I’ve ever derived a proof before I knew that an algorithm works to begin with.

EDIT: sorry, I’m in a chatty mood today. It’s a Greek national holiday (though I’m in the UK). I see what you mean and you’re probably right. I’ll shut up now :sweat_smile:

24

From the other thread:

Not necessarily. Multisets should be able to contain equivalent elements that do not compare equal. Equivalence is of course meaningless for compare/3; but we have a precedent in keysort/2, where two pairs are equivalent if the keys are equal. Same with sort/4, so we can do:

?- keysort([x-y,a-foo,a-bar], R).
R = [a-foo, a-bar, x-y].

?- sort(1, @=<, [x-y,a-foo,a-bar], R).
R = [a-foo, a-bar, x-y].

?- sort([x-y,a-foo,a-bar], R).
R = [a-bar, a-foo, x-y]. % this flipped foo with bar!

This cannot be done if equivalent subsets are represented as a term and a count.

But it also cannot be done easily if the set predicates are implemented on top of compare/3.

For this, the user should be able to provide a comparison predicate; there is a precedent for this, too, in predsort/3.

Currently predsort/3 needs a first argument Pred:

Pred(-Delta, +E1, +E2) . This call must unify Delta with one of <, > or =.

Side-note: some existing algorithms on sorted sequences only require a semi-det relation predicate p/2 (usually, “less than”). The comparison can be bootstrapped from it:

compare_p(Order, X, Y) :-
    (   p(X, Y)
    ->  Order = (<)
    ;   p(Y, X)
    ->  Order = (>)
    ;   Order = (=)
    ).

Either way, I tried to address my own suspicion from the original post:

Right now I suspect that the widely accepted, “textbook” algorithms that work on Prolog “sets” are by definition correct also for “multisets”.

This was not a useful way to formulate it. Instead:

An algorithm that is correct for multisets represented as ordered lists with repeats will also be correct for sets represented as lists without repeats.

I won’t prove that, it follows from the fact that sets in that representation are a special case of multisets. (ie, repeats are at most 1 long…)

Here it got interesting! @stassa.p already observed that the current implementation “just works”. I went ahead and did the following:

  • I copied from here some of the algorithms that work on sorted or partitioned ranges, and translated them to Prolog.
  • For the algorithms that were implemented in library(ordsets) already:
    • I compared the existing implementation;
    • I also tested the existing implementation along with my own (mechanic) translation.

I am attaching two files:
msorted.pl (6.6 KB)
test_msorted.pl (6.3 KB)

msorted.pl contains the algorithms I copied, and test_msorted.pl contains tests for some of the predicates and the corresponding library(ordsets) predicates. You can do for example

?- use_module(test_msorted).
true.

?- run_tests.

Some results:

  • The library(ordsets) implementation of union, intersection, difference (subtract), and symmetric difference (symdiff) is very close to the mechanical translation I did from procedural code to Prolog.
  • The implementation in library(ordsets) seems to be correct for multisets, and so are my mechanical translations in msorted.pl. Some of the implementations in library(ordsets) however do not follow the strict specifications for the msorted_* predicates (see the file msorted.pl for details).

All of this is in practice useless :smiley: however, I can now allow the user to provide the comparison predicates to the algorithms in msorted.pl. For example, with this:

key_compare(Order, A-_, B-_) :- compare(Order, A, B).

… the msorted_* predicates will be correct for multisets, as produced by keysort/2.

Any thoughts? Sorry for just pasting the files here, I am not sure about the names of things so I would like to see if there is any interest or comments before proceeding.

25

This is much clearer and shorter than what I tried to say over a dozen posts, thanks. Now that I see it written so simply I also have no doubt that it’s obviously true. The interesting thing is that library(ordsets) got that from the other end, i.e. starting from lists without repeats.

It’s interesting that library(ordsets) union and intersection both swap the order compared to your implementation. I haven’t looked carefully enough to tell why.

Ultimately a set isn’t ordered unless explicitly defined as an ordered set, so ordering is not 100% necessary but I guess you were more interested in the sorting in the first place.

26

This might require detective work. The original oset.pl file seems to be from 1993 and contained the relevant code that is now in library(ordsets). That code is again very similar to the code in “The Craft of Prolog” by O’Keefe, which was published in 1990. I have seen that before; but I also took care to translate the procedural code (for multisets!) I linked above in a “mechanical” fashion (see below for a demonstration). And I ended up with basically the same predicates and helper predicates (I did order my arguments differently…). But I don’t see any references in O’Keefe’s text, so I assume it is just such an obvious algorithm that you end up with the same anyway.

It is an optimization, when the head and tail of the second argument are already unpacked, they are used in a call to the helper predicate that initially takes the head and tail of the first argument. You save two predicate calls.

Yes, correct. Because a set is not ordered, the implementation is free to throw away the initial order and work with lists of sorted elements, since this allows for a better algorithm. Python for example has a container called OrderedDict which maintains the order in which key-value pairs were inserted.

27

Demonstration of how I did a mechanical translation of procedural code to Prolog and ended up with the exact same thing :smiley:

If I take “union” as an example, here was the code I started with (provided as “possible implementation”):

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
 
        if (*first2 < *first1)
            *d_first = *first2++;
        else
        {
            *d_first = *first1;
            if (!(*first1 < *first2))
                ++first2;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

I start from the for(; first1 != last1; ++d_first) at the top. first1 != last1 says “until the first list is not exhausted”, so,

union([], ?B, ?U).
union([X|A], ?B, ?U).

The ++d_first informs me that inside the loop, for every possible path, there will be something written to the output list. I keep that in mind.

Next,

        if (first2 == last2)
            return std::copy(first1, last1, d_first);

This now tells me that if I am at the end of the second list, the first list is the remaining of the output list, and I am done. So:


union([], ?B, ?U).
union([X|A], B, U) :-
    union_b(B, X, A, U).

union_b([], X, A, [X|A]).
union_b([Y|B], X, A, U) :- ?.

Then, the first comparison of the two heads:

        if (*first2 < *first1)
            *d_first = *first2++;

I have committed to using compare/3 so I will write compare(Order, X, Y) and add that case. The *d_first = *first2++; tells me to consume the head of the second list and add it to the result.


union([], ?B, ?U).
union([X|A], B, U) :-
    union_b(B, X, A, U).

union_b([], X, A, [X|A]).
union_b([Y|B], X, A, U) :-
    compare(Order, X, Y),
    union_cmp(Order, X, Y, A, B, U).

union_cmp(>, X, Y, A, B, [Y|U]) :-
    union([X|A], B, U).

The “else” of that “if” needs to be read at once because the procedural reading is important:

else
        {
            *d_first = *first1;
            if (!(*first1 < *first2))
                ++first2;
            ++first1;
        }

So, in both other cases of Order, we consume the head of the first list (++first1; at the bottom) and we also add it to the output list (*d_first = *first1; at the top).

In addition, when the two heads are equal, I can consume the head of the second list, too.

            if (!(*first1 < *first2))
                ++first2;

So:


union([], ?B, ?U).
union([X|A], B, U) :-
    union_b(B, X, A, U).

union_b([], X, A, [X|A]).
union_b([Y|B], X, A, U) :-
    compare(Order, X, Y),
    union_cmp(Order, X, Y, A, B, U).

union_cmp(<, X, Y, A, B, [X|U]) :-
    union(A, [Y|B], U).
union_cmp(=, X, Y, A, B, [X|U]) :-
    union(A, B, U).
union_cmp(>, X, Y, A, B, [Y|U]) :-
    union([X|A], B, U). % here we can take the shortcut

“The shortcut” is that we have already unpacked the head and tail of the first list in the last case above, so we can directly call union_b/4.

Finally, at the bottom, when the second list is longer than the first, we take the rest to the output:

return std::copy(first2, last2, d_first);

This informs me how to resolve the first clause of union/3, so that I get, at the end:

union([], B, B).
union([X|A], B, U) :-
    union_b(B, X, A, U).

union_b([], X, A, [X|A]).
union_b([Y|B], X, A, U) :-
    compare(Order, X, Y),
    union_cmp(Order, X, Y, A, B, U).

union_cmp(<, X, Y, A, B, [X|U]) :-
    union(A, [Y|B], U).
union_cmp(=, X, Y, A, B, [X|U]) :-
    union(A, B, U).
union_cmp(>, X, Y, A, B, [Y|U]) :-
    union_b(B, X, A, U). % shortcut

Compare this to the original code for set union from library(oset) as linked above, complete with the argument-swapping shortcut. (Since we only have equality here, this is completely legal!)

% oset_union(+OSet1, +OSet2, -Union).
% -----------------------------
oset_union([], Union, Union).
oset_union([H1|T1], L2, Union) :-
    union2(L2, H1, T1, Union).

union2([], H1, T1, [H1|T1]).
union2([H2|T2], H1, T1, Union) :-
    compare(Order, H1, H2),
    union3(Order, H1, T1, H2, T2, Union).

union3(<, H1, T1,  H2, T2, [H1|Union]) :-
    union2(T1, H2, T2, Union). % this shortcut swaps!
union3(=, H1, T1, _H2, T2, [H1|Union]) :-
    oset_union(T1, T2, Union).
union3(>, H1, T1,  H2, T2, [H2|Union]) :-
    union2(T2, H1, T1, Union).

PS: I should actually try some LLM, give it the C++ code and ask it to give me a Prolog equivalent. Stay tuned! :smiley:
PPS: well it ain’t gonna give it to me easily.

29

Yes, but I had a reason not to. That code ends up in the same place but does not include multisets (lists as sorted by msort/2) in the spec. The fact that I started elsewhere and ended up in the same place is interesting enough to me.

Either way, I would like to hear opinions on whether a new library (maybe distributed as an “add-on package”) is of any interest to anyone. We roughly have the following purely additive features not available at the moment in library(ordsets):

  • A spec that covers multisets as produced by msort/2 (already in the code I provided)
  • A C implementation of the same algorithms, if this makes it that much faster (I would know how to do it and the work seems mechanical enough. I specifically used compare/3 because it is available as PL_compare() in the foreign language interface)
  • A version of the predicates that takes a custom comparator.

This last one is not well defined at the moment. One possible way is to have the client code provide a comparison predicate like predsort/3, another would be to have some convention similar to sort/4 which covers a lot of use cases (but not all).

The only important question is if there is any use whatsoever for any of this. Until Stassa popped up with her questions a month ago, no one ever seems to have needed any of this :smiley: I would have needed it a couple of times but I just wrote custom code or circumvented the issue altogether.

32

Yes, sure. You can also find the msorted_until/4 predicate in msorted.pl I shared above. The ordered_list/1 you show can be bootstrapped as

ordered_list(L) :-
    msorted_until(L, _, _, Rest),
    Rest == [].

I had versions of all predicates in msorted.pl that used the weaker less_than/2 comparison, but got rid of them completely because in SWI-Prolog this is anyway a call to compare/3. With the exception of some edge cases, using a compare/3 instead of a less_than/2 does not make a difference. Again, a reminder, compare/3 can be bootstrapped from a less_than/2 like this:

compare(Order, A, B) :-
    (   less_than(A, B)
    ->  Order = (<)
    ;   less_than(B, A)
    ->  Order = (>)
    ;   Order = (=)
    ).