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

[Leo White <lpw25@cam.ac.uk>]

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", <module>); ("Sets", <module>)]

Regards,

Leo

John Whitington <john@coherentgraphics.co.uk> 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/