Numerical sort, reverse sort, etc?

[Jan Wielemaker]

Hi,

Sorting recently came into discussion again. sort/2 sorts on standard
order of terms and removes duplicates. That is fine for most logical
manipulations, but often not adequate for applications. They may wish to

        * Sort numerically (using ISO, 2.0 ends before 1).
        * Sort case-insensitively
        * Sort locale-dependent
        * Reverse the order
        * Remove or do not remove duplicates.

One can do some things using keysort, but not easily all of these.
Adding lots of predicates is probably not a good idea, as especially
reversing and duplicate-handling is orthogonal on the sorting criterium.

I'm tempted to define sort/3 as sort(+List, -Ordered, +Options), where
options provides:

        * compare(:Goal)
        Comparision predicate.  Default compare/3
        * reverse(+Boolean)
        Iff =true=, sort largest first
        * duplicates(+Action)
        One of =keep= or =remove=

Using a couple of built-ins for Goal, we can still use an efficient
(foreign) implementation for the common cases.  This notably requires
a compare_numbers/3

Opions?

        Cheers --- Jan


------------
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@...

[Paulo Moura]

On 2008/04/16, at 11:09, Jan Wielemaker wrote:

> Sorting recently came into discussion again. sort/2 sorts on standard
> order of terms and removes duplicates. That is fine for most logical
> manipulations, but often not adequate for applications. They may  
> wish to
>
> * Sort numerically (using ISO, 2.0 ends before 1).

Just to help clarify the issue here, the ISO Prolog standard (section  
7.2) dictates the order of terms, where all floating-point numbers  
precede all integers. Thus, 2.0 only precedes 1 in the standing order  
of terms, i.e. when using @</2 instead of </2.

> * Sort case-insensitively
> * Sort locale-dependent
> * Reverse the order
> * Remove or do not remove duplicates.
>
> One can do some things using keysort, but not easily all of these.
> Adding lots of predicates is probably not a good idea, as especially
> reversing and duplicate-handling is orthogonal on the sorting  
> criterium.
>
> I'm tempted to define sort/3 as sort(+List, -Ordered, +Options), where
> options provides:
>
> * compare(:Goal)
> Comparision predicate.  Default compare/3

Why not use the standard operators here? The default could be @<. In  
order to sort numerically, we would use compare(<).

> * reverse(+Boolean)
> Iff =true=, sort largest first

Or use e.g. compare(>) for reverse order.

> * duplicates(+Action)
> One of =keep= or =remove=

Or use e.g. compare(>=) for ordering numerically, lower values last,  
and keeping duplicates. I.e. specify a sort/3 where the third argument  
is simply an operator or a user defined (arity two) predicate.  
Nevertheless, your suggestion of using a list of options is more  
declarative, even if more verbose. As Gibarian said to Kelvin in the  
remake of the "Solaris" movie, "There are no answers, only  
choices." :-) (*)

> Using a couple of built-ins for Goal, we can still use an efficient
> (foreign) implementation for the common cases.  This notably requires
> a compare_numbers/3


The default values should match the behavior of the specification of  
the sort/2 on the Core Prolog draft revision proposal.

Cheers,

Paulo

(*) For the nitpicks, the line above is *not* from Stanislaw Lem, the  
author of the novel.


-----------------------------------------------------------------
Paulo Jorge Lopes de Moura
Dep. of Computer Science, University of Beira Interior
6201-001 Covilhã, Portugal

Office 4.3  Ext. 3257
Phone: [phone] Fax: [phone]
Email: <mailto:pmoura@...>

Home page: <http://www.di.ubi.pt/~pmoura>
Research:  <http://logtalk.org/>
-----------------------------------------------------------------







------------
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@...

[Stiffler]

----------------------------------------

> From: wielemak@...
> To: prolog@...
> Subject: [SWIPL] Numerical sort, reverse sort, etc?
> Date: Wed, 16 Apr 2008 12:09:11 +0200
>
> Hi,
>
> Sorting recently came into discussion again. sort/2 sorts on standard
> order of terms and removes duplicates. That is fine for most logical
> manipulations, but often not adequate for applications. They may wish to
>
> * Sort numerically (using ISO, 2.0 ends before 1).
> * Sort case-insensitively
> * Sort locale-dependent
> * Reverse the order
> * Remove or do not remove duplicates.
>
> One can do some things using keysort, but not easily all of these.
> Adding lots of predicates is probably not a good idea, as especially
> reversing and duplicate-handling is orthogonal on the sorting criterium.
>
> I'm tempted to define sort/3 as sort(+List, -Ordered, +Options), where
> options provides:
>
> * compare(:Goal)
> Comparision predicate.  Default compare/3
> * reverse(+Boolean)
> Iff =true=, sort largest first
> * duplicates(+Action)
> One of =keep= or =remove=
>
> Using a couple of built-ins for Goal, we can still use an efficient
> (foreign) implementation for the common cases.  This notably requires
> a compare_numbers/3
>
> Opions?
>
> Cheers --- Jan

I like this idea - a nice interface to capture all this functionality seems a good thing especially if all prolog implementors can agree.

As you point out, a lot may already be possible with existing built-ins but it requires a higher degree of familiarity with the language.  And I confess to occasionally using sort/2 followed by reverse/2 because I can't remember offhand the details of using compare.
PJ
_________________________________________________________________
Free Windows Live software. Chat, search, share pics and more
http://get.live.com/
------------
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@...

[Ulrich Neumerkel]

> I'm tempted to define sort/3 as sort(+List, -Ordered, +Options), where
> options provides:
>  
>         * compare(:Goal)
>         Comparision predicate.  Default compare/3

Most orders are implemented providing only some boolean comparison.
Yours is definitely better in certain circumstances, as it allows to
remove duplicates. But what about orders where you do not have =
naturally?

>         * reverse(+Boolean)
>         Iff =true=, sort largest first

Couldn't this be called ascending(Bool)? This sounds more natural to
me.  And if you insist upon reverse, why not reversed?

>         * duplicates(+Action)
>         One of =keep= or =remove=

Why not duplicates(true) meaning yes, there may be duplicates.

------------
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@...

[Jan Wielemaker]

On Wednesday 16 April 2008 16:06, Ulrich Neumerkel wrote:
> > I'm tempted to define sort/3 as sort(+List, -Ordered, +Options), where
> > options provides:
> >
> >         * compare(:Goal)
> >         Comparision predicate.  Default compare/3
>
> Most orders are implemented providing only some boolean comparison.

Is that true?  See qsort() from the C-library.

> Yours is definitely better in certain circumstances, as it allows to
> remove duplicates. But what about orders where you do not have =
> naturally?

Nobody says you must return '='. Paulo suggested something along these
lines (using >, >=, etc.). I somehow recall some sort implementations
get very upset if you tell them (A op B) is true AND (B op A) is true.

It is of course possible to have both using mutually exclusive option
arguments.

> >         * reverse(+Boolean)
> >         Iff =true=, sort largest first
>
> Couldn't this be called ascending(Bool)? This sounds more natural to
> me.  And if you insist upon reverse, why not reversed?

You are right. ascending is better. Maybe even order(ascending) vs.
order(descending)?

> >         * duplicates(+Action)
> >         One of =keep= or =remove=
>
> Why not duplicates(true) meaning yes, there may be duplicates.

Hmmm.  I thought about that first, but thought keep/remove is clearer.
Nobody knows whether or not the result has duplicates if you do not
remove them.  I don't like 'may be' very much.

        Cheers --- Jan


------------
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@...

[Günter Kniesel]

Jan Wielemaker schrieb:

>>>         * duplicates(+Action)
>>>         One of =keep= or =remove=
>> Why not duplicates(true) meaning yes, there may be duplicates.
>
> Hmmm.  I thought about that first, but thought keep/remove is clearer.

I'd like to second that. Keep / remove IS clearer.

Another thought. Is there any evidence that we are talking here about
a real need? For instance, is there anybody who does NOT want sort to
remove duplicates? For the past few years I've used it almost
exclusively for the purpose of removing duplicates fast from
large lists, accepting the sorting as an inevitable side-effect
that, however, didn't do any harm!

Günter

------------
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@...

[Paul Singleton]

Jan Wielemaker wrote:
> On Wednesday 16 April 2008 16:06, Ulrich Neumerkel wrote:

>>>         * reverse(+Boolean)
>>>         Iff =true=, sort largest first
>> Couldn't this be called ascending(Bool)? This sounds more natural to
>> me.  And if you insist upon reverse, why not reversed?
>
> You are right. ascending is better. Maybe even order(ascending) vs.
> order(descending)?

I'm not sure: if the comparison is essentially a < rather than a >
(or is it the other way around?) the natural result may descend,
and to reverse it we'd need order(descending) which is confusing.

How about an atomic option 'reversed', also 'uniq' (and 'unique')
(and 'dedup'?!) but see below.  Or is this kind of flag bad style?

And 'random'?!  (I'm at least half serious)

>>>         * duplicates(+Action)
>>>         One of =keep= or =remove=
>> Why not duplicates(true) meaning yes, there may be duplicates.
>
> Hmmm.  I thought about that first, but thought keep/remove is clearer.
> Nobody knows whether or not the result has duplicates if you do not
> remove them.  I don't like 'may be' very much.

Are there one or two "duplicates" in [a,a]?

Since "equal under comparison" terms need not be identical, we may
want to keep only the first (in the original list) of each, or last?
E.g. keep(first) | keep(last)

And if we don't say, is sort free to make an undefined choice?

Paul Singleton


------------
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@...

[Ulrich Neumerkel]

On Wednesday 16 April 2008 17:06, Jan Wielemaker wrote:
> > > I'm tempted to define sort/3 as sort(+List, -Ordered, +Options), where
> > > options provides:
> > >
> > >         * compare(:Goal)
> > >         Comparision predicate.  Default compare/3
> >
> > Most orders are implemented providing only some boolean comparison.
>
> Is that true?  See qsort() from the C-library.

I meant to refer to cases where this might be useful in Prolog. Also,
qsort is not the ultimate sort.

> > Yours is definitely better in certain circumstances, as it allows to
> > remove duplicates. But what about orders where you do not have =
> > naturally?
>
> Nobody says you must return '='. Paulo suggested something along these
> lines (using >, >=, 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 somehow recall some sort implementations
> get very upset if you tell them (A op B) is true AND (B op A) is true.

You cannot take any alorithm, but there is still enough freedom.
What do you guarantee about stability?

> It is of course possible to have both using mutually exclusive option
> arguments.
>
> > >         * reverse(+Boolean)
> > >         Iff =true=, sort largest first
> >
> > Couldn't this be called ascending(Bool)? This sounds more natural to
> > me.  And if you insist upon reverse, why not reversed?
>
> You are right. ascending is better. Maybe even order(ascending) vs.
> order(descending)?

My hesitation is just about the introduction of a new type/domain.

> > >         * Duplicates(+Action)
> > >         One of =keep= or =remove=
> >
> > Why not duplicates(true) meaning yes, there may be duplicates.
>
> Hmmm.  I thought about that first, but thought keep/remove is clearer.
> Nobody knows whether or not the result has duplicates if you do not
> remove them.  I don't like 'may be' very much.

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?

(I was primarily interested to remove the imperative sounding argument
"+Action", since there is nothing here to act or agitate.  Ideally,
options detail what the relation is and not what some implementation
chooses to do.)


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

------------
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@...

[Richard A. O'Keefe]

On 16 Apr 2008, at 11:00 pm, Paulo Moura wrote:
> Why not use the standard operators here? The default could be @<. In  
> order to sort numerically, we would use compare(<).

ARRGH!  NO!  TEN THOUSAND TIMES NO!

One of the things that Prolog got brilliantly *RIGHT* was
providing a three-way comparison operation as the foundation.
(It's a pity that compare_numbers/3 wasn't there from the
  beginning, but when the only numbers were integers, compare/3
  did the same job.)

This is also one of the things that Eiffel and Haskell get
brilliantly right too.

It's one of the things that Smalltalk got painfully wrong.

Three-way comparison is simply a far far better building block
than two-way comparison.



------------
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@...

[Richard A. O'Keefe]

On 17 Apr 2008, at 4:17 am, Günter Kniesel wrote:
> Another thought. Is there any evidence that we are talking here about
> a real need? For instance, is there anybody who does NOT want sort to
> remove duplicates? For the past few years I've used it almost
> exclusively for the purpose of removing duplicates fast from
> large lists, accepting the sorting as an inevitable side-effect
> that, however, didn't do any harm!

I frequently sort in order to
  - COUNT           => msort, then group and count adjacent equals
  - COMBINE         => keysort, then group keys and combine satellite  
data
  - CANONICALISE    => msort; I don't *care* if there are duplicates  
or not.

The classic "find anagrams by sorting a string then searching in a
collection of sorted-original pairs" trick would go hopelessly haywire
if duplicates were deleted.

I would be very very pleased if whenever I bought two things at a
supermarket I was charged for only one of them!





------------
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@...

[Richard A. O'Keefe]

>
> 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@...

[Paulo Moura]

On 2008/04/17, at 01:38, Richard A. O'Keefe wrote:

> On 16 Apr 2008, at 11:00 pm, Paulo Moura wrote:
>> Why not use the standard operators here? The default could be @<.  
>> In order to sort numerically, we would use compare(<).
>
> ARRGH!  NO!  TEN THOUSAND TIMES NO!
>
> One of the things that Prolog got brilliantly *RIGHT* was
> providing a three-way comparison operation as the foundation.
> (It's a pity that compare_numbers/3 wasn't there from the
> beginning, but when the only numbers were integers, compare/3
> did the same job.)
>
> This is also one of the things that Eiffel and Haskell get
> brilliantly right too.
>
> It's one of the things that Smalltalk got painfully wrong.
>
> Three-way comparison is simply a far far better building block
> than two-way comparison.

Just to clarify my suggestion:

sort(L, S, <)   - ascending order,  remove duplicates, compare  
numerically
sort(L, S, @<)  - ascending order,  remove duplicates, compare using  
standard order
sort(L, S, >)   - descending order, remove duplicates, compare  
numerically
sort(L, S, @>)  - descending order, remove duplicates, compare using  
standard order
sort(L, S, =<)  - ascending order,  keep duplicates,   compare  
numerically
sort(L, S, @=<) - ascending order,  keep duplicates,   compare using  
standard order
sort(L, S, >=)  - descending order, keep duplicates,   compare  
numerically
sort(L, S, @>=) - descending order, keep duplicates,   compare using  
standard order

sort(L, S, UserFunctor) - whatever the predicate with UserFunctor  
dictates

The compact notation suggested above does not prevent three-way  
comparison if it's interpreted as stating order, what to do with  
duplicates, and either to use numeric order or standard order.

Cheers,

Paulo


-----------------------------------------------------------------
Paulo Jorge Lopes de Moura
Dep. of Computer Science, University of Beira Interior
6201-001 Covilhã, Portugal

Office 4.3  Ext. 3257
Phone: [phone] Fax: [phone]
Email: <mailto:pmoura@...>

Home page: <http://www.di.ubi.pt/~pmoura>
Research:  <http://logtalk.org/>
-----------------------------------------------------------------







------------
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@...

[Ulrich Neumerkel]

Since this issue starts to get pretty technical, could we use concrete
test cases to communicate desired properties? Jan will be happy to
have some too.

> > 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.

Of interest and ambiguity is the case with two terms = .  If I
correctly understand your suggestion, you believe the sort options
proposed by Jan not to be useful safe for the order itself.  In
particular you have no way to indicate what happens with
duplicates. So, I assume you will have them removed.

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

mycompare1(R, A-_,B-_) :-
        compare(R, A, B).

test(t1,[true(Sorted = [a-_X])]) :-
        rok:sort(mycompare1, [a-1,a-2], Sorted).

with _X either 1 or 2?


mycompare2((=),A, B) :-
        A =:= B.
mycompare2((<), A, B) :-
        A < B.
mycompare2((>), A, B) :-
        A > B.

test(t2,[true(Sorted = [_])]) :-
        rok:sort(mycompare2, [1+1,1*1], Sorted).

> > 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.

Courage ! We will sort that out.

I am particularily interested in narrowing down what can be tested
about the comparison relation, since - no matter how nice the
interface is - this will definitely be a source of inevitable errors.

Maybe some plunit-mode to indicate those properties could be of
interest.  (Jan, you read this?)

> > 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.

Here, I lost you completely. What kind of combination predicates?

------------
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@...

[Jan Wielemaker]

On Thursday 17 April 2008 21:20:23 Ulrich Neumerkel wrote:
> Since this issue starts to get pretty technical, could we use concrete
> test cases to communicate desired properties? Jan will be happy to
> have some too.

Sure, but first we need to get the specs right. Richard showed me in
what was (accidentally?) a private mail that all there is to sorting is
comparison and combination.  Combination defines the term that goes into
the result if comparision yields equal.  Richard proposes (I guess he
will correct me if I summarise this incorectly)

%% sort(:Compare, :Combine, +List, -Ordered) is det.

Compare is the usual beast, compare/3 being the prototypical example for
standard order. Combine says what must happen with two terms that are
equal.  A simple way to remove duplicates is, keeping the first one:

keep_first(X, _, X).

A nicer example is with keysort if you would like a union of the values
(being ordered sets):

compare_keys(Diff, K1-_, K2-_) :-
        compare(Diff, K1, K2).

join_value_sets(K-Set1, K-Set2, K-Set) :-
        ord_union(Set1, Set2, Set).

So, now we can dow the whole lot nice and easily:

        sort(compare_keys, join_value_sets, KeySetsIn, KeySetsOut).

Quite nice.  I have asked two questions

        (1) Shouldn't the argument order be

                sort(+List, -Ordered, :Compare, :Combine).

        So, we can drop arguments from the right and substitute defaults

        To map the de-facto standard stuff, we could have:

        sort(In, Out, Compare) :- sort(In, Out, Compare, keep_first).
        sort(In, Out) :- sort(In, Out, compare).
        msort(In, Out) :- sort(In, Out, compare, fail).
        keysort(In, Out) :- sort(In, Out, compare_keys, keep_first).

        (2) Shouldn't we have something special to specify reverse ordering
        to avoid a large set of ordering predicates?

I'm in favour of (1), I'm not sure of (2). I don't like the many
predicates, but I also like the simple API of sort/4. Only with properly
defined standard predicates however we can optimise away the common
simple cases. Getting the very most out of sorting is quite attractive
as their are many operations for which sorting is the difference between
O(n*log(n)) and O(n**2) and it is not uncommon to see that programs spent
a significant amount of time in sorting.

> I am particularily interested in narrowing down what can be tested
> about the comparison relation, since - no matter how nice the
> interface is - this will definitely be a source of inevitable errors.
>
> Maybe some plunit-mode to indicate those properties could be of
> interest.  (Jan, you read this?)

Its surely a good idea to have some test infrastructure for these
things.  In itself that is easy, but the hard part is generating
data-sets to verify comparison predicates.

        Cheers --- Jan


------------
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@...

[Ulrich Neumerkel]

On Thursday 17 Apr 2008 21:58:51 Jan Wielemaker clarified

>                                ... that all there is to sorting is
> comparison and combination.  Combination defines the term that goes into
> the result if comparision yields equal.  Richard proposes (I guess he
> will correct me if I summarise this incorectly)
>
> %%      sort(:Compare, :Combine, +List, -Ordered) is det.
>
> Compare is the usual beast, compare/3 being the prototypical example for
> standard order. Combine says what must happen with two terms that are
> equal.  A simple way to remove duplicates is, keeping the first one:
>
> keep_first(X, _, X).

So, :Combine combines two elements, and the one occuring first in the
original list is the one in the first argument?

But how can I express that duplicates should be kept (for exemples as
given previously)? Do I really have to do this all myself? How do I
get the keysort functionality which is L=[a-4,a-4],keysort(L,L)?

And what does fail mean in this context? (The one in msort below?)

> A nicer example is with keysort if you would like a union of the values
> (being ordered sets):
>
> compare_keys(Diff, K1-_, K2-_) :-
>         compare(Diff, K1, K2).
>
> join_value_sets(K-Set1, K-Set2, K-Set) :-
>         ord_union(Set1, Set2, Set).
>
> So, now we can dow the whole lot nice and easily:
>
>         sort(compare_keys, join_value_sets, KeySetsIn, KeySetsOut).
>
> Quite nice.  I have asked two questions

Nice, but this is something different. That's not keysort.

>         (1) Shouldn't the argument order be
>
>                 sort(+List, -Ordered, :Compare, :Combine).
>
>         So, we can drop arguments from the right and substitute defaults
>
>         To map the de-facto standard stuff, we could have:
>
>         sort(In, Out, Compare) :- sort(In, Out, Compare, keep_first).
>         sort(In, Out) :- sort(In, Out, compare).
>         msort(In, Out) :- sort(In, Out, compare, fail).
>         keysort(In, Out) :- sort(In, Out, compare_keys, keep_first).

Would you ever consider call(sort(List,Ordered),Compare,Combine) ?
Probably not. But maybe call(sort(Compare,Combine), List,Ordered).  So
it is still better to put those arguments first, it's longer but
better readable.

>         (2) Shouldn't we have something special to specify reverse ordering
>         to avoid a large set of ordering predicates?

opposite(Compare, R, X,Y) :-
    call(Compare, RO, X, Y),
    order_opposite(RO,R).

order_opposite(=,=).
order_opposite(<,>).
order_opposite(>,<).

These facts are Japanese smileys!

?- compare(R,1,2).
R = (<).

?- opposite(compare,R,1,2).
R = (>).

?- opposite(opposite(compare),R,1,2).
R = (<).

That predicate should be predefined such that you can recognise it.

> I'm in favour of (1), I'm not sure of (2). I don't like the many
> predicates, but I also like the simple API of sort/4. Only with properly
> defined standard predicates however we can optimise away the common
> simple cases. Getting the very most out of sorting is quite attractive
> as their are many operations for which sorting is the difference between
> O(n*log(n)) and O(n**2) and it is not uncommon to see that programs spent
> a significant amount of time in sorting.
>
> > I am particularily interested in narrowing down what can be tested
> > about the comparison relation, since - no matter how nice the
> > interface is - this will definitely be a source of inevitable errors.
> >
> > Maybe some plunit-mode to indicate those properties could be of
> > interest.  (Jan, you read this?)
>
> Its surely a good idea to have some test infrastructure for these
> things.  In itself that is easy, but the hard part is generating
> data-sets to verify comparison predicates.

The idea would be to get those on-the-fly while testing the
corresponding sorting.

------------
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@...