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

[John Carr <jfc@MIT.EDU>]

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