From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <john@coherentgraphics.co.uk>
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 BE5D97F890
	for <caml-list@sympa.inria.fr>; Wed, 26 Mar 2014 16:58:50 +0100 (CET)
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  john@coherentgraphics.co.uk) identity=pra;
  client-ip=188.64.184.41;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="john@coherentgraphics.co.uk";
  x-sender="john@coherentgraphics.co.uk";
  x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  john@coherentgraphics.co.uk) identity=mailfrom;
  client-ip=188.64.184.41;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="john@coherentgraphics.co.uk";
  x-sender="john@coherentgraphics.co.uk";
  x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@bluechip4.ukhost4u.com) identity=helo;
  client-ip=188.64.184.41;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="john@coherentgraphics.co.uk";
  x-sender="postmaster@bluechip4.ukhost4u.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AjYCANb4MlO8QLgpemdsb2JhbABZg0HEaRYOAQELBw0JPIJTEUAjGhYYAwIBAgFLiBABnmqxf5MwBJ8ajxQ
X-IPAS-Result: AjYCANb4MlO8QLgpemdsb2JhbABZg0HEaRYOAQELBw0JPIJTEUAjGhYYAwIBAgFLiBABnmqxf5MwBJ8ajxQ
X-IronPort-AV: E=Sophos;i="4.97,736,1389740400"; 
   d="scan'208";a="64866195"
Received: from bluechip4.ukhost4u.com ([188.64.184.41])
  by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 26 Mar 2014 16:58:50 +0100
Received: from [46.64.58.219] (port=54677 helo=[192.168.1.165])
	by bluechip4.ukhost4u.com with esmtpsa (TLSv1:DHE-RSA-CAMELLIA256-SHA:256)
	(Exim 4.82)
	(envelope-from <john@coherentgraphics.co.uk>)
	id 1WSqE4-000lVT-Jb
	for caml-list@inria.fr; Wed, 26 Mar 2014 15:58:48 +0000
Message-ID: <5332F937.1030303@coherentgraphics.co.uk>
Date: Wed, 26 Mar 2014 15:58:47 +0000
From: John Whitington <john@coherentgraphics.co.uk>
User-Agent: Postbox 3.0.9 (Macintosh/20140129)
MIME-Version: 1.0
To: "caml-list@inria.fr" <caml-list@inria.fr>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-AntiAbuse: This header was added to track abuse, please include it with any abuse report
X-AntiAbuse: Primary Hostname - bluechip4.ukhost4u.com
X-AntiAbuse: Original Domain - inria.fr
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain - coherentgraphics.co.uk
X-Get-Message-Sender-Via: bluechip4.ukhost4u.com: authenticated_id: john@coherentgraphics.co.uk
Subject: [Caml-list] Wrapping up the Set module in another

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/