From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA23546; Mon, 22 Mar 2004 09:52:09 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id JAA24108 for ; Mon, 22 Mar 2004 09:52:08 +0100 (MET) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i2M8q7Hd032165 for ; Mon, 22 Mar 2004 09:52:08 +0100 Received: from pc8-123 (pc8-123 [129.175.8.123]) by lri.lri.fr (8.12.10/jtpda-5.4) with ESMTP id i2M8WmCr027373 ; Mon, 22 Mar 2004 09:32:48 +0100 (MET) Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian)) id 1B5KrY-0008VQ-00; Mon, 22 Mar 2004 09:32:48 +0100 From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <16478.42160.362909.932912@gargle.gargle.HOWL> Date: Mon, 22 Mar 2004 09:32:48 +0100 To: Bob Bailey Cc: Caml List Subject: Re: [Caml-list] Question about string ref and Hashtbl. In-Reply-To: <20040320000558.71279.qmail@web40311.mail.yahoo.com> References: <20040320.075814.105434271.yoriyuki@mbg.ocn.ne.jp> <20040320000558.71279.qmail@web40311.mail.yahoo.com> X-Mailer: VM 7.03 under Emacs 20.7.2 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) X-MailScanner: Found to be clean X-Miltered: at concorde by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 caml-list:01 hashtbl:01 hashtbl:01 hash-consing:01 implemented:01 hash:01 hash:01 consing:01 instantiate:01 lri:01 filliatr:01 hash-consing:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk X-Status: X-Keywords: X-UID: 301 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