Map.Make with polymorphic variant

Learning
1

Is there a way to instantiate the Map.Make functor with polymorphic variant ?
Without writing by hand a module like

module Keys = struct
   type t= `Foo | `Bar
   let compare a b = match a, b with
      | `Foo, `Bar -> 1
      | `Foo, `Foo -> 0
      | `Bar, `Bar -> 0
      | `Bar, `Foo -> -1
end
module KeysMap = Map.Make(Keys)

the compare function is heavy, is there to way to make better ?

2

If you just need any comparison function, you can use Stdlib.compare.

Cheers,
Nicolas

2 Likes
3

Thank you !
This is exactly what I was looking for

4

Polymorphic comparison is considered harmful but in that case, yes it works.
Another trade-off will be given a function [Foo | Bar] -> int :

let to_int = function 
  | `Bar -> 0 
  | `Foo -> 1

And after that you can relay on Int.compare :

module Keys_map = Map.Make (struct 
  type t = [`Foo | `Bar]
  let compare a b = Int.compare (to_int a) (to_int b)
end)
5

Most of those harmful points don’t really apply here for such a simple type though.
Sure, using Stdlib.compare blindly is a problem, but in this case structural comparison is exactly the goal (and it’s very simple structure).

The good way to use it here is to monomorphize it:

let compare (a: t) (b: t) = Stdlib.compare a b

Now the compiler can produce very efficient code that doesn’t require calling the generic caml_compare function from the runtime. This can be quickly seen with Godbolt: Compiler Explorer (compare3 is longer than the red highlighting seems to suggest).

An alternative approach which is convenient but less error-prone is to use a PPX such as: GitHub - ocaml-ppx/ppx_deriving: Type-driven code generation for OCaml.

2 Likes
6

Strongly agree here! There is a big difference between the polymorphic comparison C primitive (caml_compare, implemented in runtime/compare.c) and the lambda primitive %compare (Stdlib.compare is this latter one). It’s a shame to end up writing masses of code (and often generating more complex code) rather than a simple type annotation.

There’s a long tale of trying to get a warning into OCaml to be emitted when caml_compare is used instead of a monomorphised version in Warn on polymorphic comparisons by kit-ty-kate · Pull Request #9928 · ocaml/ocaml · GitHub.

2 Likes
7

@sim642 and @dra27
Thanks a lot for the clarification! I was not aware about that subtility!