From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.5 required=5.0 tests=AWL,SPF_SOFTFAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 04137BBAF for ; Tue, 20 Jan 2009 18:05:16 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: At8AAA2TdUnVhjEYkWdsb2JhbACUBwEBAQEJCwoHEQO3VIVz X-IronPort-AV: E=Sophos;i="4.37,295,1231110000"; d="scan'208";a="19909387" Received: from ihsmtp02voda.lis.interhost.com (HELO ihsmtp02cons.lis.interhost.com) ([213.134.49.24]) by mail2-smtp-roc.national.inria.fr with ESMTP; 20 Jan 2009 18:05:15 +0100 Received: from [192.168.1.64] ([77.54.249.136]) by ihsmtp02cons.lis.interhost.com with Microsoft SMTPSVC(6.0.3790.3959); Tue, 20 Jan 2009 17:02:37 +0000 Message-ID: <4976044A.3060407@inescporto.pt> Date: Tue, 20 Jan 2009 17:05:14 +0000 From: Hugo Ferreira User-Agent: Thunderbird 2.0.0.19 (X11/20090105) MIME-Version: 1.0 To: Martin Jambon Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Making a polymorphic type non-polymorphic to comply with original signature References: <4975AEA2.6050901@inescporto.pt> <4975E72C.8060709@ens-lyon.org> In-Reply-To: <4975E72C.8060709@ens-lyon.org> Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 20 Jan 2009 17:02:37.0613 (UTC) FILETIME=[E57D3DD0:01C97B20] X-Spam: no; 0.00; run-time:01 sig:01 node:01 node:01 val:01 bool:01 val:01 hash:01 struct:01 hash:01 hashtbl:01 hashtbl:01 hashedtype:01 hashedtype:01 mli:01 Martin, Thanks for the alternate solution. It seems to provide a much simpler interface i.e: doesn't require such a convoluted way of declaring the types. I wonder if it has any run-time benefits compared to the previous solution. Regards, Hugo F. Martin Jambon wrote: > Hugo Ferreira wrote: >> Hello, >> >> I have the following definition: >> >> module rec H : >> sig >> type 'a node = >> | Node of 'a node J.t >> | Leaf of 'a >> >> type 'a t = 'a node >> val equal : 'a t -> 'a t -> bool >> val hash : 'a t -> int >> end = >> struct >> type 'a node = >> | Node of 'a node J.t >> | Leaf of 'a >> >> type 'a t = 'a node >> let equa = (==) >> let hash = Hashtbl.hash >> end >> >> and J : Hashtbl.S with type 'a key = 'a H.node = Hashtbl.Make( H ) >> ;; >> >> The data type 'a node is polymorphic. It is also a key used by the >> hash-table. Note that H now does not comply with Hashtbl.HashedType >> (because Hashtbl.HashedType is not polymorphic). By adding the >> constraint "with type" also does not help. >> >> Is it possible to make H comply with Hashtbl.HashedType i.e: make >> J.Key = 'a H.node ? > > > I just posted an implementation of polymorphic hash tables with physical > comparison, using the Obj module: > > http://martin.jambon.free.fr/phys.html > > It is the following code: > > (***** phys.mli *****) > > type ('a, 'b) t > > val add : ('a, 'b) t -> 'a -> 'b -> unit > val clear : ('a, 'b) t -> unit > val copy : ('a, 'b) t -> ('a, 'b) t > val create : int -> ('a, 'b) t > val find : ('a, 'b) t -> 'a -> 'b > val find_all : ('a, 'b) t -> 'a -> 'b list > val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c > val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit > val length : ('a, 'b) t -> int > val mem : ('a, 'b) t -> 'a -> bool > val remove : ('a, 'b) t -> 'a -> unit > val replace : ('a, 'b) t -> 'a -> 'b -> unit > > > > (***** phys.ml *****) > > (* > This implementation uses the Obj module which allows to transgress > the type system. It is not regular OCaml. > *) > > module Magic_key = > struct > type t = Obj.t > let equal = ( == ) > let hash = Hashtbl.hash > end > > module Magic_table = Hashtbl.Make (Magic_key) > > > type ('a, 'b) t = 'b Magic_table.t > > let add tbl k v = Magic_table.add tbl (Obj.repr k) v > let clear tbl = Magic_table.clear tbl > let copy tbl = Magic_table.copy tbl > let create n = Magic_table.create n > let find tbl k = Magic_table.find tbl (Obj.repr k) > let find_all tbl k = Magic_table.find_all tbl (Obj.repr k) > let fold f tbl accu = Magic_table.fold (Obj.magic f) (Obj.magic tbl) accu > let iter f tbl = Magic_table.iter (Obj.magic f) (Obj.magic tbl) > let length tbl = Magic_table.length tbl > let mem tbl k = Magic_table.mem tbl (Obj.repr k) > let remove tbl k = Magic_table.remove tbl (Obj.repr k) > let replace tbl k v = Magic_table.replace tbl (Obj.repr k) v > > > (*****************) > > > > Martin >