From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 23C677F890 for ; Wed, 26 Mar 2014 22:11:46 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of lpw25@cam.ac.uk) identity=pra; client-ip=131.111.8.150; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="lpw25@cam.ac.uk"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of lpw25@cam.ac.uk) identity=mailfrom; client-ip=131.111.8.150; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="lpw25@cam.ac.uk"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@ppsw-50.csi.cam.ac.uk) identity=helo; client-ip=131.111.8.150; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="postmaster@ppsw-50.csi.cam.ac.uk"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ar8BAOpBM1ODbwiWnGdsb2JhbABZg0HDSoEeFg4BAQEBAQgLCQkUKIIlAQEBAwEnEz8FCwsHGiUPAQRJE4dxCATKV4ZrFxaOWweEOASuLg X-IPAS-Result: Ar8BAOpBM1ODbwiWnGdsb2JhbABZg0HDSoEeFg4BAQEBAQgLCQkUKIIlAQEBAwEnEz8FCwsHGiUPAQRJE4dxCATKV4ZrFxaOWweEOASuLg X-IronPort-AV: E=Sophos;i="4.97,737,1389740400"; d="scan'208";a="54246914" Received: from ppsw-50.csi.cam.ac.uk ([131.111.8.150]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 26 Mar 2014 22:11:45 +0100 X-Cam-AntiVirus: no malware found X-Cam-ScannerInfo: http://www.cam.ac.uk/cs/email/scanner/ Received: from host5-81-227-149.range5-81.btcentralplus.com ([5.81.227.149]:51700 helo=netbook) by ppsw-50.csi.cam.ac.uk (smtp.hermes.cam.ac.uk [131.111.8.158]:587) with esmtpsa (PLAIN:lpw25) (TLSv1.2:DHE-RSA-AES128-SHA:128) id 1WSv6u-0001gy-rR (Exim 4.82_3-c0e5623) (return-path ); Wed, 26 Mar 2014 21:11:44 +0000 From: Leo White To: John Whitington Cc: "caml-list\@inria.fr" References: <5332F937.1030303@coherentgraphics.co.uk> X-Face: "XWxb[u_Z\PA_Y?9@|IA!!+jTb(/290-*ea/Un$I0B98.$n%eL.;2w*,z]WR#T:,p[ NBd++M7l]#7zj7!{~iw $W-"/=|dVjhT[D{4~gE}gK<2`.6fs!;uqqud]vs2N/3^m7{aS1V, Date: Wed, 26 Mar 2014 21:11:41 +0000 In-Reply-To: <5332F937.1030303@coherentgraphics.co.uk> (John Whitington's message of "Wed, 26 Mar 2014 15:58:47 +0000") Message-ID: <86eh1oacmq.fsf@cam.ac.uk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Subject: Re: [Caml-list] Wrapping up the Set module in another It is not at all ideal, and there is almost certainly a better way, but you could wrap the set module up with the actual set. I also don't know how much the overhead might affect your benchmarks. # module SetSet : SetType = struct module type SetS = sig include Set.S val s : t end;; type 'a t = (module SetS with type elt = 'a) let list_of_set (type elt) ((module S) : elt t) = S.elements S.s let set_of_list (type elt) (l : elt list) : elt t = (module struct include Set.Make (struct type t = elt let compare = compare end) let s = List.fold_right add l empty end) let member (type elt) (x : elt) ((module S) : elt t) = S.mem x S.s let insert (type elt) (x : elt) ((module S) : elt t) : elt t = (module struct include S let s = add x S.s end) let size (type elt) ((module S) : elt t) = S.cardinal S.s end;; module SetSet : SetType # let implementations = [("Lists", (module SetList : SetType)); ("Sets", (module SetSet : SetType))];; val implementations : (string * (module SetType)) list = [("Lists", ); ("Sets", )] Regards, Leo John Whitington writes: > Hi, > > Suppose I want to benchmark various toy set implementations, so I have already written: > > module type SetType = > sig > type 'a t > val set_of_list : 'a list -> 'a t > val list_of_set : 'a t -> 'a list > val insert : 'a -> 'a t -> 'a t > val size : 'a t -> int > val member : 'a -> 'a t -> bool > end > > and then, for example: > > module SetList : sig include SetType end = > struct > type 'a t = 'a list > > let list_of_set x = x > > let rec set_of_list l = > match l with > [] -> [] > | h::t -> > if List.mem h t then set_of_list t else h :: set_of_list t > > let insert x l = x :: l > > let size = List.length > > let member = List.mem > end > > This works fine -- I can put them into a little list, and run tests: > > let implementations = > [("Lists", (module SetList : SetType)); > ("Trees", (module SetTree : SetType)); > ("Red-black trees", (module SetRedBlack : SetType)); > ("Hash tables", (module SetHashtbl : SetType))] > > Now, it would be nice to include OCaml's Set module, but can it be made to fit the signature? So far I have: > > let make_setset (type s) () = > let module SetSet : sig include SetType end = > struct > module S = Set.Make (struct type t = s let compare = compare end) > > type 'a t = S.t > > let list_of_set s = S.elements s > > let set_of_list l = List.fold_right S.add l S.empty > > let member = S.mem > > let insert = S.add > > let size = S.cardinal > end > in > (module SetSet : SetType) > > and > > let implementations = > let module SetSet = (val (make_setset ())) in > [("Lists", (module SetList : SetType)); > ("Trees", (module SetTree : SetType)); > ("Red-black trees", (module SetRedBlack : SetType)); > ("Hash tables", (module SetHashtbl : SetType)); > ("OCaml sets", (module SetSet : SetType))] > > The problem here, it seems to me, is that the connection between 'a in make_setset and (type s) and S.elt is not > established, and so the return types of list_of_set etc. don't type-check. > > Is there any way to do this, or is the functorised implementation of Set fundamentally opposed to the normal > polymorphism of the type 'a t in SetType? > > Thanks, > > -- > John Whitington > Director, Coherent Graphics Ltd > http://www.coherentpdf.com/