Version française
Home     About     Download     Resources     Contact us    
Browse thread
wish: hash function for module Num
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jean-Christophe Filliatre <filliatr@c...>
Subject: wish: hash function for module Num

[ 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