Version franēaise
Home     About     Download     Resources     Contact us    
Browse thread
Re: [Caml-list] Question about string ref and Hashtbl.
[ 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 <Jean-Christophe.Filliatre@l...>
Subject: Re: [Caml-list] Question about string ref and Hashtbl.

Bob Bailey writes:
 > That's an interesting idea.  SO the key string and the value string will really point to the same
 > location in memory.  
 > 
 > So if I did (string,string ref) Hashtbl.t,
 > then the string ref would be a pointer to the key string.
 > Would that allow me to compare two string ref variables together?  Would the comparason of the
 > locations of the strings mean I wouldn't have to do a full string compare?

What you are trying to achieve  is called hash-consing and comes up to
Lisp a long time ago. It is indeed implemented using a hash table, but
refs are not needed:

	let (hash_cons : string -> string) = 
	  let h = Hashtbl.create 97 in
	  fun s -> try Hashtbl.find h s with Not_found -> Hashtbl.add h s s; s

A string is mapped to itself  whenever it is encountered for the first
time.

If  you achieve  full hash  consing  (i.e. any  string passes  through
function hash_cons) then you can  safely substitute == for = (they are
now equivalent).

If you need  a total order over strings  (e.g. to instantiate Set.Make
or Map.Make) you need to associate unique integer keys to strings. You
may have a look at module Hashcons available here:
http://www.lri.fr/~filliatr/software.en.html 
which already  does this, and at  the companion modules  Hset and Hmap
(sets and  map for  hash-consed values). There  is also a  short paper
describing the hash-consing technique in ocaml.

Hops this helps,
-- 
Jean-Christophe Filliātre

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners