wish: hash function for module Num

wish: hash function for module Num

[Jean-Christophe Filliatre]

[ francais ci-dessous ]

It would be  nice if the module Num would provide  a hash function for
type num, with the expected property:

     eq_num n m  =>  hash_num n = hash_num m

The generic  hash function cannot be  used, since equal  nums may have
different  representations, on  which the  generic hash  function will
return   different   value  (even   with   normalization  after   each
computation):

======================================================================
# open Num;;
# let _ = Arith_status.set_normalize_ratio  true;;
- : unit = ()

# div_num (Int 1) (Int 1);;
- : Num.num = Ratio <abstr>

# Hashtbl.hash (div_num (Int 1) (Int 1));;
- : int = 504151169
# Hashtbl.hash (Int 1);;                  
- : int = 1
======================================================================

It is  quite a mean  trick, and makes  the writing of a  hash function
rather tedious, since you  have to normalize the representation first.

More  generally, I  would expect  the Num  module to  use  a canonical
representation (as soon as we set_normalize_ratio).


== francais =================================================================

La fonction generique de hachage  d'ocaml ne peut etre utilisee sur le
type  Num.num,  parce  qu'un  meme  entier  peut  etre  represente  de
plusieurs manieres differentes, donnant des resultats differents (voir
exemple ci-dessus).  Une fonction  de hash fournie  par le  module Num
serait la  bienvenue. Plus generalement, il serait  souhaitable que le
module Num utilise une representation canonique pour chaque rationnel.

-- 
Jean-Christophe Filliatre    
  Computer Science Laboratory   Phone (650) 859-5173
  SRI International             FAX   (650) 859-2844
  333 Ravenswood Ave.           email  filliatr@csl.sri.com
  Menlo Park, CA 94025, USA     web    http://www.csl.sri.com/~filliatr

  

Re: wish: hash function for module Num

[Pierre Weis]

> [ francais ci-dessous ]
> 
> It would be  nice if the module Num would provide  a hash function for
> type num, with the expected property:
> 
>      eq_num n m  =>  hash_num n = hash_num m
> 
> The generic  hash function cannot be  used, since equal  nums may have
> different  representations, on  which the  generic hash  function will
> return   different   value  (even   with   normalization  after   each
> computation):
> 
> ======================================================================
> # open Num;;
> # let _ = Arith_status.set_normalize_ratio  true;;
> - : unit = ()
> 
> # div_num (Int 1) (Int 1);;
> - : Num.num = Ratio <abstr>
> 
> # Hashtbl.hash (div_num (Int 1) (Int 1));;
> - : int = 504151169
> # Hashtbl.hash (Int 1);;                  
> - : int = 1
> ======================================================================
> 
> It is  quite a mean  trick, and makes  the writing of a  hash function
> rather tedious, since you  have to normalize the representation first.

You just have to write one line of code:

let hash_num n = Hashtbl.hash (normalize_num n);;

However, I agree that the best way to achieve this when nums are
embedded into more complex data structures would be to attach a hash
function to nums (that would just be the preceding hash_num function).

> More  generally, I  would expect  the Num  module to  use  a canonical
> representation (as soon as we set_normalize_ratio).

Yes. We also expected that. I corrected the code of some ``optimized''
functions in the module Num (addition, multiplication and division),
reported the correct versions of Caml Light 0.75.

> == francais =================================================================
> 
> La fonction generique de hachage  d'ocaml ne peut etre utilisee sur le
> type  Num.num,  parce  qu'un  meme  entier  peut  etre  represente  de
> plusieurs manieres differentes, donnant des resultats differents (voir
> exemple ci-dessus).  Une fonction  de hash fournie  par le  module Num
> serait la  bienvenue.

Oui. La fonction en question consiste en 1 seule ligne de code:

let hash_num n = Hashtbl.hash (normalize_num n);;

Cependant, il vaudrait mieux utiliser le nouveau mécanisme qui permet
d'attacher une telle fonction de hachage spécialisée sur les valeurs
d'un type. Ainsi le hachage serait corrrect même si le nombre est à
l'intérieur d'une structure de données plus complexe.

> Plus generalement, il serait  souhaitable que le
> module Num utilise une representation canonique pour chaque rationnel.

Pour des raisons évidentes d'efficacité il ne serait pas souhaitable
que le module Num utilise une représentation canonique pour chaque
rationnel. Cependant, la bibliothèque est bien entendu censée le faire
lorsque l'utilisateur le demande explicitement. C'est donc un bug de
la bibliothèque nums dans Objective Caml: peut-être une optimisation
hâtive lors du portage ? Ou peut-être une correction de la
bibliothèque non reportée dans Objective Caml ?
Quoiqu'il en soit, j'ai reporté les versions de add_num mult_num et
div_num que j'avais debogguées dans Caml Light.

Pierre Weis

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