« Return to Thread: Numerical sort, reverse sort, etc?
Re: Numerical sort, reverse sort, etc?
by Ulrich Neumerkel
::
Rate this Message:
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@...
> > > 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@...
« Return to Thread: Numerical sort, reverse sort, etc?
| Free Forum Powered by Nabble | Forum Help |