Re: wish: hash function for module Num

[Pierre Weis <Pierre.Weis@inria.fr>]

> [ 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/