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 276C77F890 for ; Wed, 26 Mar 2014 18:04:36 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of jfc@MIT.EDU) identity=pra; client-ip=18.9.25.13; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jfc@mit.edu"; x-sender="jfc@MIT.EDU"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of jfc@mit.edu designates 18.9.25.13 as permitted sender) identity=mailfrom; client-ip=18.9.25.13; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jfc@mit.edu"; x-sender="jfc@mit.edu"; 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@dmz-mailsec-scanner-2.mit.edu) identity=helo; client-ip=18.9.25.13; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jfc@mit.edu"; x-sender="postmaster@dmz-mailsec-scanner-2.mit.edu"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgcCACQIM1MSCRkNlWdsb2JhbABZg0GsZJZogR0WDgEBAQEJCwkJEiqCJQEBAQMBJ0cLBQsLBxoEIQ82EgYlh1MDCQsKyH0DYYZrF45xB4Q4BJoAlEo X-IPAS-Result: AgcCACQIM1MSCRkNlWdsb2JhbABZg0GsZJZogR0WDgEBAQEJCwkJEiqCJQEBAQMBJ0cLBQsLBxoEIQ82EgYlh1MDCQsKyH0DYYZrF45xB4Q4BJoAlEo X-IronPort-AV: E=Sophos;i="4.97,736,1389740400"; d="scan'208";a="64877967" Received: from dmz-mailsec-scanner-2.mit.edu ([18.9.25.13]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 26 Mar 2014 18:04:35 +0100 X-AuditID: 1209190d-f79776d000000ce9-67-533308a1b4b8 Received: from mailhub-auth-2.mit.edu ( [18.7.62.36]) (using TLS with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by dmz-mailsec-scanner-2.mit.edu (Symantec Messaging Gateway) with SMTP id BA.29.03305.1A803335; Wed, 26 Mar 2014 13:04:33 -0400 (EDT) Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by mailhub-auth-2.mit.edu (8.13.8/8.9.2) with ESMTP id s2QH4WoQ013546; Wed, 26 Mar 2014 13:04:33 -0400 Received: from localhost (contents-vnder-pressvre.mit.edu [18.9.64.11]) (authenticated bits=0) (User authenticated as jfc@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.8/8.12.4) with ESMTP id s2QH4U1f010834; Wed, 26 Mar 2014 13:04:31 -0400 Message-Id: <201403261704.s2QH4U1f010834@outgoing.mit.edu> To: John Whitington cc: "caml-list@inria.fr" In-reply-to: <5332F937.1030303@coherentgraphics.co.uk> References: <5332F937.1030303@coherentgraphics.co.uk> Comments: In-reply-to John Whitington message dated "Wed, 26 Mar 2014 15:58:47 -0000." X-Mailer: MH-E 8.2; nmh 1.3; GNU Emacs 23.3.1 Date: Wed, 26 Mar 2014 13:04:30 -0400 From: John Carr X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrOIsWRmVeSWpSXmKPExsUixG6noruQwzjY4Mp3XYtPOzawWLQ8/cbm wOTRueosk8ekF4dYApiiuGxSUnMyy1KL9O0SuDL+zbzKVtAhUfGp+y5zA+MGwS5GTg4JAROJ gxv+M0PYYhIX7q1n62Lk4hASmM0ksf7DXEaQhJDARkaJc4cMIBK/GCUOLGhgB0nwClhJ3G1Y zgpiiwgYSkw+uxWogYODWUBXovlzAEhYWMBO4sHZPrA5nAJmEtuuLGOGmGkqMW9nI1icWaBC 4tKm6ywQR+hK/Nu/BsxmEVCV+HXmLNh4NgFZiUftXYwTGPkXMDKsYpRNya3SzU3MzClOTdYt Tk7My0st0jXSy80s0UtNKd3ECAojTkneHYzvDiodYhTgYFTi4U24axQsxJpYVlyZe4hRkoNJ SZTXhsU4WIgvKT+lMiOxOCO+qDQntfgQowQHs5II746vQOW8KYmVValF+TApaQ4WJXFeeQ7t YCGB9MSS1OzU1ILUIpisDAeHkgTvLXagoYJFqempFWmZOSUIaSYOTpDhPEDDG0FqeIsLEnOL M9Mh8qcYdTn+dfd0MQqx5OXnpUqJ8wqCFAmAFGWU5sHNgcX/K0ZxoLeEeS+AVPEAUwfcpFdA S5iAlnBVgXxQXJKIkJJqYMy5y/u3UdQ5L+FGUezxf9GLGD+3R9z++DW+UnBb945ZO73+H7t3 b9qpQ6kHShq+xuRZJx1KvaW97Gxyx4N3fzfeuZl5NWLXhLQLiezxt/tlqjR3XTzjMk3ebceU yLi0eYrSq679Tjj49HND4r6s3N0BC5f8D6mMVYtLjvh26JvKUeE0G+1umyglluKMREMt5qLi RACzq9DX2gIAAA== Subject: Re: [Caml-list] Wrapping up the Set module in another I think your distinction between types of polymorphism is correct. Set.S contains monomorphic functions. You want [forall] but Set.Make gives you [exists]. The library needs a different Set.OrderedType module for every type to be stored in a Set.S.t. You only create one such module per call to make_setset. > 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