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

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

I'm afraid I don't have any real idea of the runtime cost.

The main additional cost would come from calling `Set.Make` in
`set_of_list` and creating new modules in `set_of_list` and `insert`.
`Set.Make` has to create a lot of closures which capture the `compare`
function. I think these closures are all allocated at once, but this
still means a lot of assignments. Creating the new modules is a record
allocation and assignment of all the record fields.

The cost of creating modules could probably be reduced a bit by
rewriting it as:

    module type SetS = sig module Ops : Set.S val s : Ops.t end;;

    type 'a t = (module SetS with type Ops.elt = 'a)

    let list_of_set (type elt) ((module S) : elt t) = S.Ops.elements S.s

    let set_of_list (type elt) (l : elt list) : elt t =
      (module struct
        module Ops = Set.Make (struct type t = elt let compare = compare end)
        let s = List.fold_right Ops.add l Ops.empty
      end)

    let member (type elt) (x : elt) ((module S) : elt t) = S.Ops.mem x S.s

    let insert (type elt) (x : elt) ((module S) : elt t) : elt t =
      (module struct
         module Ops = S.Ops
         let s = add x S.s
       end)

    let size (type elt) ((module S) : elt t) = S.Ops.cardinal S.s

There would also be a cost in the other functions for the indirection to
get to the actual set and the functions.

Theoretically it might also be slower than using the result of
`Set.Make` directly since that would be easier for the compiler to
optimise by calling the functions directly or inlining them, although
I'm not sure if the current compiler actually does this.

Regards,

Leo

Thomas Braibant <thomas.braibant@gmail.com> writes:

> 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