Monomorphic map type

Learning
1

When I type module MapFromInt = Map.Make(Int) I get a module containing a map type along with functions that operate on it. This map uses int as a key, but is polymorphic in the type of the value. How can I create a module containing a map with a fixed non-polymorphic type?

The only way I know of, to create a monomorphic map from, for example, an int to a string, is to do something like this:

module MapFromIntToString = struct
  module MapFromInt = Map.Make(Int)
  type key = int
  type value = string
  type t = string MapFromInt.t
  let empty : t = MapFromInt.empty
  let is_empty : (t -> bool) = MapFromInt.is_empty
  let mem : (int -> t -> bool) = MapFromInt.mem
  let add : (int -> string -> t -> t) = MapFromInt.add
  ...
end

Is there a less tedious way to make a monomorphic map in OCaml?

1 Like
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