[Caml-list] Sorting

[Caml-list] Sorting

[Marcin 'Qrczak' Kowalczyk]

Sort.array : order:('a -> 'a -> bool) -> 'a array -> unit
Sort.list  : order:('a -> 'a -> bool) -> 'a list -> 'a list
Array.sort : cmp:('a -> 'a -> int) -> 'a array -> unit
List.sort  : cmp:('a -> 'a -> int) -> 'a list -> 'a list

What are advantages and disadvantages in parametrizing either by '<'
or by the 3-way comparison?

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^
QRCZAK

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Sorting

[Xavier Leroy]

> What are advantages and disadvantages in parametrizing either by '<'
> or by the 3-way comparison?

In addition to what has been said already, the 3-way comparison is
less error-prone with respect to two classic errors:
1- passing a "less than or equal" predicate where a "less than"
   predicate is expected, or conversely;
2- passing a predicate that is not a total ordering where a total
   ordering is expected.
Both errors could cause the old Sort.array or Sort.list functions to
misbehave seriously.  These errors are still possible with the 3-way
comparison approach, but less likely I think.

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Sorting

[jeanmarc.eber]

En réponse à Xavier Leroy <xavier.leroy@inria.fr>:

> > What are advantages and disadvantages in parametrizing either by '<'
> > or by the 3-way comparison?
> 
> In addition to what has been said already, the 3-way comparison is
> less error-prone with respect to two classic errors:
> 1- passing a "less than or equal" predicate where a "less than"
>    predicate is expected, or conversely;
> 2- passing a predicate that is not a total ordering where a total
>    ordering is expected.
> Both errors could cause the old Sort.array or Sort.list functions to
> misbehave seriously.  These errors are still possible with the 3-way
> comparison approach, but less likely I think.
> 
> - Xavier Leroy

When we are just about "sorting predicates":

I always have a little hesitation about the properties that are
assumed on this functions.

Shouldn't one say clearly in the OCaml doc that these comparison
function are simply suppposed (if I'm not wrong) to be a

  total pre-order, that is a binary predicate that is

  total (of course)
  transitive
  reflexive

BUT NOT necessarly anti-symetric.

Of course, these properties have to be "translated" back into the
3-way comparison approach (thats trivial) but I would find it helpful to
say precisely what properties these functions should have.

Jean-Marc Eber
LexiFi Technologies
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Sorting

[Krishnaswami, Neel]

Marcin 'Qrczak' Kowalczyk [mailto:qrczak@knm.org.pl] wrote:
> 
> What are advantages and disadvantages in parametrizing either by '<'
> or by the 3-way comparison?

If comparisons are very expensive -- for instance, if the elements
are long strings or large sets -- then it makes for faster execution
to use a three-way comparison. On the average you will do two-thirds
as many comparisons while sorting with a three-way comparison. 

I find this irritating becuase it just *feels* nicer to pass a 
function of type elt -> elt -> bool to a sorting function. It's
closer to how sorting is taught, and hence to my mental model. :)

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Sorting

[Pierre Weis]

> >What are advantages and disadvantages in parametrizing either by '<'
> >or by the 3-way comparison?
> 
> It's better because it is more modern :-)
[...]
> -- Damien

Wao! I love this argument, thank you Damien!

Just for fun, I would like to help with a small figure that will even
enforce this definitive argument. Consider the following figure 1 that
has to be read horizontally as well as vertically, and where vertical
arrows have to be interpreted as semantics equivalence, as opposed to
horizontal arrows which are used to designate mere opposition (or
``semantical'' contrary), as typographical difference between
horizontal and vertical arrows emphasizes. Hence, the diagram has not
to be confused with a categorical commutating diagram: even if the
vertical commutation is granted, the horizontal commutation does not
apply. In particular, you cannot deduce from the figure that modern is
equivalent to function, but you can take it for granted that object is
new, good, and modern. Note that this figure summarizes also some
fruitful guidelines for programming language designers :). Note also
that you can add new balloons to the figure in order to help you to
explain your point of view to others during discussions; for instance
consider adding balloons for syntax and/or semantics
proposals/extensions for Caml, or also new semantics fields such as
classic, revised, obsolete, pure, hot, {\it ad libitum}...


             |--------|                    |-------------|
             | modern |     <--------->    | traditional |
             |--------|                    |-------------|
                 ^                                ^
                 |                                |
                 |                                |
                 v                                v
             |--------|                    |-------------|
             |  good  |     <--------->    |     bad     |
             |--------|                    |-------------|
                 ^                                ^
                 |                                |
                 |                                |
                 v                                v
             |--------|                    |-------------|
             |  new   |     <--------->    |     old     |
             |--------|                    |-------------|
                 ^                                ^
                 |                                |
                 |                                |
                 v                                v
             |--------|                    |-------------|
             | object |     <--------->    |   function  |
             |--------|                    |-------------|

             Fig. 1, semantical fields associations and equivalences


I hope nobody will take this as a personnal attack, but as a kind of
funny reminder that we should try to do our best to avoid using words
with strong connotations out of our field: it is too easy to generate
flamewares this way! In my opinion, we should prefer technical terms
and arguments directely borrowed from computer science, either from
theory or from practice...

Hope this will help,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Sorting

[Damien Doligez]

>From: "Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>

>Sort.array : order:('a -> 'a -> bool) -> 'a array -> unit
>Sort.list  : order:('a -> 'a -> bool) -> 'a list -> 'a list

Old functions, obsolescent.

>Array.sort : cmp:('a -> 'a -> int) -> 'a array -> unit
>List.sort  : cmp:('a -> 'a -> int) -> 'a list -> 'a list

New functions.


>What are advantages and disadvantages in parametrizing either by '<'
>or by the 3-way comparison?

It's better because it is more modern :-)

Seriously, the 3-way comparison is more consistent with the
definition of Map.OrderedType.

-- Damien
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr