Am Mittwoch, den 10.09.2014, 13:41 +0100 schrieb Pippijn van Steenhoven:
> On Wed, Sep 10, 2014 at 02:26:28PM +0200, Gerd Stolpmann wrote:
> > type t = ...
> > type t_cmp = t * int
> > 
> > let wrap x = (x, Hashtbl.hash x)
> > 
> > let my_compare (x1,h1) (x2,h2) =
> >   if h1=h2 then
> >     compare x1 x2
> >   else
> >     h1-h2
> 
> This code is incorrect when h1 is large and negative.

Hashtbl.hash returns non-negative ints. For other hash functions you are
correct.

>  You should use
> "compare h1 h2" and annotate h1 and/or h2 with its type (int), so that
> int-compare is called directly.
> 
> Also, if you store the hash before the actual value, compare will
> probably stop comparing after it finds that the hashes are not equal, so
> you can simply use the polymorphic compare on t_cmp. I don't know this
> for sure, since I haven't looked at the source, but I would assume this
> is true.

The OCaml manual doesn't define compare for tuples, so you cannot
exploit that. I wouldn't bet that compare runs from left to right over
the values, as OCaml is known for sometimes preferring right to left.
But maybe this could be a future language feature? If the OCaml manual
defined compare on tuples, this would in deed be a fine trick.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------