[Caml-list] Wrapping up the Set module in another

[John Whitington <john@coherentgraphics.co.uk>]

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/