Comparator_witness compatibility for maps and sets

Learning
1

Hello!

Would appreciate very much if someone could help me understand the behavior of this OCaml snippet:

open Core

module IntSet = Set.Make(Int)

module IntMap = Map.Make(Int)

let test = fun (x : IntSet.t) -> (IntMap.of_key_set x)

(* this quite literally expands the definition of Set.Make and Map.Make *)

module MakeSet (Elt : Set.Elt) = Set.Make_using_comparator(struct 
  include Elt
  include Comparator.Make(Elt)
end)

module MakeMap (Key : Map.Key) = Map.Make_using_comparator(struct 
  include Key
  include Comparator.Make(Key)
end)

module IntSet = MakeSet(Int) 
module IntMap = MakeMap(Int) 

let test = fun (x : IntSet.t) -> (IntMap.of_key_set x)

Basically, this explores the compatibility of the Key type of a Map with int keys and a set with int elements, which comes up eg. when creating a map from a set. The first test is the “naive” way to create the set and map, using the Make functors. It fails, because the phantom comparator_witness types created by Set.Make and Map.Make are deemed to be different. I don’t really get why , because both Make functors create these witness types in the exact same way on the exact same argument, and I have ascribed neither IntSet or IntMap to hide anything about comparator_witness.

The second method quite literally expands the definition of Set.Make and Map.Make from the library source, and now all of a sudden the test works. So what is it about Make that is causing OCaml to “forget” that the comparator_witness types are in fact the same…

Thank you!

2

The difference comes from the signature of Make in core:

module Make (Key : Key) : S with type Key.t = Key.t

which doesn’t the share the identity of the comparator witness type.

Contrarily, the type of your inlined version will be inferred with all type equality visible. In particular, the module type will contains at least the second equality in

module MapMake (Key : Key) : 
  S with type Key.t = Key.t
     and type Key.comparator_witness = Comparator.Make(Key).comparator_witness
1 Like