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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 6621E7F890 for ; Fri, 28 Mar 2014 09:23:03 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of thomas.braibant@gmail.com) identity=pra; client-ip=209.85.217.177; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="thomas.braibant@gmail.com"; x-sender="thomas.braibant@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of thomas.braibant@gmail.com designates 209.85.217.177 as permitted sender) identity=mailfrom; client-ip=209.85.217.177; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="thomas.braibant@gmail.com"; x-sender="thomas.braibant@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-lb0-f177.google.com) identity=helo; client-ip=209.85.217.177; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="thomas.braibant@gmail.com"; x-sender="postmaster@mail-lb0-f177.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhwCAAAxNVPRVdmxlGdsb2JhbABZDoMzV6t9lnCBEggWDgEBAQEHCwsJEiqCJQEBAQQnGQEbEgsBAwwGBQcEAwoNISIBEQEFAQoSBhMSh1IBAxENolSMX4MOlxAKGScDCmSGSxEBBQyJQIUvB4Q4BJhNgTOPExgphB5APQ X-IPAS-Result: AhwCAAAxNVPRVdmxlGdsb2JhbABZDoMzV6t9lnCBEggWDgEBAQEHCwsJEiqCJQEBAQQnGQEbEgsBAwwGBQcEAwoNISIBEQEFAQoSBhMSh1IBAxENolSMX4MOlxAKGScDCmSGSxEBBQyJQIUvB4Q4BJhNgTOPExgphB5APQ X-IronPort-AV: E=Sophos;i="4.97,749,1389740400"; d="scan'208";a="65132190" Received: from mail-lb0-f177.google.com ([209.85.217.177]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 28 Mar 2014 09:23:02 +0100 Received: by mail-lb0-f177.google.com with SMTP id z11so3429670lbi.36 for ; Fri, 28 Mar 2014 01:23:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=syt8kIY+4XMmfAUQBIAPJSpPEcxzyg7R3Yl2TnKHKAQ=; b=VOcTkkHu8eRxdKsEA9OgBN9zVgjmmZm7JJbJlRBnPtjMzrucOIAn4hqSeyz96nwrua RkZ2r4UrkWIC1i2WtFpobAjA9EAuQzdrFXhWaTfHQ31gGHXUFp4AntR+kLZFuiNw5BBf ZCQBH6kpC5o45kYjSWvJqMmhFiBoqab0D3FEnu9jea1FNrRrQuqDEnvhAu0I23gn8IWX GHx6x2RwfE2UP5vEJCByioQHlKjTD7e7RxgXPwjkuk6zg+ux1X5EffjtlNF1YlFtRb86 I9LAXI/z//yYeYMdPYV/U/qGy7PC1yaFOFIRxkrITxKbY4eSZPWiHYg68SxcRl5pqwwZ g3nw== X-Received: by 10.112.201.1 with SMTP id jw1mr56966lbc.47.1395994982273; Fri, 28 Mar 2014 01:23:02 -0700 (PDT) MIME-Version: 1.0 Received: by 10.114.223.135 with HTTP; Fri, 28 Mar 2014 01:22:42 -0700 (PDT) In-Reply-To: <86eh1oacmq.fsf@cam.ac.uk> References: <5332F937.1030303@coherentgraphics.co.uk> <86eh1oacmq.fsf@cam.ac.uk> From: Thomas Braibant Date: Fri, 28 Mar 2014 08:22:42 +0000 Message-ID: To: Leo White Cc: John Whitington , "caml-list@inria.fr" Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [Caml-list] Wrapping up the Set module in another Hi, I really like this trick of wrapping the module and an actual set together. Do you have any idea of the runtime cost? I remember reading that functor applications are runtime operations, but I wonder what is the overhead. Best Thomas On Wed, Mar 26, 2014 at 9:11 PM, Leo White wrote: > 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/ > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs