> [ 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/
This archive was generated by hypermail 2b29 : Wed Mar 01 2000 - 18:11:55 MET