Monomorphic map type

Learning
2

Hi @Ksawery_Nowak.

The following is very similar to what you’ve written, but perhaps makes it clearer that no changes to the implementation are required:

module Int_string_map : sig
  type t
  type key := int
  type data := string

  val empty : t
  val mem : key -> t -> bool
  val add : key -> data -> t -> t
  (* ... *)
end = struct
  include Map.Make(Int)
  type nonrec t = string t
end

In short: one can get a monomorphic map by constraining the polymorphic map to a monomorphic signature (and defining the necessary monomorphic type), but that requires writing the monomorphic signature manually.

The type of Map.S isn’t quite generic enough to let us do this without re-stating the functions we want. As an aside, it is possible to generalise it to a module type that can be monomorphised in O(1) code:

module type S_general = sig
  type 'a t
  type key
  type 'a data

  val empty : 'a t
  val mem : key -> 'a t -> bool
  val add : key -> 'a data -> 'a t -> 'a t
end

(* A map that is polymorphic in values, equivalent to [Map.S] *)
module type S_poly = S_general with type 'a data := 'a

(* A map that has fixed key and value types *)
module type S_mono = sig
  type t
  type data
  include S_general with type 'a t := t and type 'a data := data
end

This can be useful when you’d like a single functor (e.g. Map.Make) to have a return type that is easily coercible into both monomorphic and polymorphic signatures.

4 Likes