Re: Numerical sort, reverse sort, etc?

>
> There is this nexus between the actual comparison and
> duplicates/uniques. Some comparisons might not be able to identify
> equals - and thus are unable to remove duplicates.  The current
> interface - as far as I understand it - insists upon being able to do
> this.  What, if the implementation calls mycompare(A,B,=)? After all,
> mycompare/3 should be a relation.  And mycompare(A, A, =) should
> succeed with any instantiation (modulo instantiation errors indeed).

I'm sorry, but there is something fundamental being overlooked here.
We are talking about SORTING.  Sorting requires a total order.

If you base sorting on an analogue of "<",
it must satisfy this form of trichotomy:

    for all x, y in the domain
        either x < y
            or y < x
            or neither

So we have
     three_way_comparison_from_less_than(Less, R, X, Y) :-
         (   call(Less, X, Y) -> R = (<)
        ;   call(Less, Y, X) -> R = (>)
        ;                       R = (=)
        ).

If it _isn't_ sound to do this, that is, if the equality
defined this way is not an equivalence relation, then it makes
NO sense to sort using your Less predicate.

If you base sorting on an analogue of "<=",
it must satisfy this form of trichotomoy:

    for all x, y in the domain
        either x <= y and y <= x
            or x <= y and not (y <= x)
            or not (x <= y) and y <= x

So we have

     three_way_comparison_from_less_than_or_equal_to(LessEq, R, X, Y) :-
      (   call(LessEq, X, Y) ->
            (   call(LessEq, Y, X) -> R = (=)
            ;                         R = (<)
        ;                             R = (>)
        ).

If it _isn't_ sound to do this, that is, if the equality
defined this way is not an equivalence relation, then it makes
NO sense to sort using your Less predicate.

So if you have any kind of binary predicate that it makes sense
to sort with, then it can most certainly identify equals.  There
cannot be such a thing as a predicate that cannot identify equals
in the required sense and yet makes sense for sorting.

I hope that by now it is obvious that if you wanted to do

        jan:sort(List, Sorted, [compare(<)])

then you can just as well do

        rok:sort(three_way_comparison_from_less(<), List, Sorted)

Equally, of course, you can write an adapted going the other way.

I really do not like hiding important bits of code inside data lists.
 From a higher order programming perspective, fine, but from a software
engineering point of view, it's very nearly the most important thing
and needs to be in a visually and linguistically salient position.


It is usually conceptually
simpler and practically more efficient to define and use the
three-way comparison than any of the derived two-way comparisons.

Take the classic example of comparing pairs, where we are taking
the reversed order for the second component:

     pair_compare(R, (A1,B1), (A2,B2)) :-
        compare(Ra, A1, A2),
        (   Ra = (=) -> compare(R, B2, B1)
        ;   R = Ra
        ).

What's it like to do this using @<?

    'pair<'((A1,B1), (A2,B2)) :-
        (    A1 @< A2 -> true
        ;    A2 @< A1 -> fail
        ;    B2 @< B1
        ).

You see that we have to repeat the test on the first components.
This is inefficient and error-prone.

> That's what I didn't like, too. So what about:
>
> uniques(true) meaning elements are uniques.
>
> "unique" is also a noun, but is it common enough? At least uniques
> might look common to people used to uniq.
>
> Or uniqueness?

All this argument over what to call the wrong kind of interface
is very depressing.

> Something else comes up: will the existing sorts be interchangably
> expressible with sort/3?

The ONLY useful option we've seen is what comparison predicate to
use.  We need two predicates.  One accepts a comparison predicate,
and the other accepts both a comparison predicate and a combination
predicate.  At this point, nobody has suggest any kind of sort that
cannot be done using those.



------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...