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

[Thomas Braibant <thomas.braibant@gmail.com>]

Hi,

I really like this trick of wrapping the module and an actual set
together. Do you have any idea of the runtime cost? I remember reading
that functor applications are runtime operations, but I wonder what is
the overhead.

Best
Thomas

On Wed, Mar 26, 2014 at 9:11 PM, Leo White <lpw25@cam.ac.uk> wrote:
> 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/
>
> --
> 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