Extending OCaml Maps to formattable Maps

Question

I have made a functor for format-able sets, as follows:

module type POrderedType =
  sig
    type t
    val compare : t -> t -> int
    val format : Format.formatter -> t -> unit
  end

module type SET =
  sig
    include Set.S
    val format : Format.formatter -> t -> unit
  end

module MakeSet (P : POrderedType) : SET with type elt = P.t

Implementation of this is straightforward:

module MakeSet (P : OrderedType) =
  struct
    include Set.Make(P)

    let format ff s =
      let rec format' ff = function
        | [] -> ()
        | [v] -> Format.fprintf ff "%a" format v
        | v::tl -> Format.fprintf ff "%a,@ %a" format v format' tl in
      Format.fprintf ff "@[<4>%a@]" format' (elements s)
  end

I wanted to do something similar with maps. POrderedType is fine for keys, but I need a simpler type for values:

module type Printable =
  sig
    type t
    val format : Format.formatter -> t -> unit
  end

Then I wanted to do something similar to what I had done for sets, but I run into the following problem. Map.S values have type +'a t. I can't figure out a way to include the Map.S definition while constraining the 'a to be a Printable.t. What I want is something like the following (ignoring the fact that it is illegal):

module MakeMap (Pkey : POrderedType) (Pval : Printable) :
  MAP with type key = Pkey.t and type 'a t = 'a t constraint 'a = Pval.t

Is there any way to do what I want without copying the entire signature of Map by hand?

Answer 1

I think the cleanest way to propose a printing function for polymorphic maps is to make the map printing function parametric over the values printing function. You can think of it this way:

• functor-defined types are defined at the functor level, so providing functions for them is best done by adding new functor parameters (or enriching existing ones)

• parametric types are bound (generalized) at the value level, so providing functions for them is best done by adding new parameters to the value

In OCaml, convenience tend to make people favor parametric polymorphism over functorization when possible. Functorization is sometimes necessary to enforce some type safety (here it's used to make sure that maps over different comparison functions have incompatible types), but otherwise people rather try to have polymorphism. So you're actually in the lucky situation here.

If you really want to have a functor producing monomorphic maps, well, I'm afraid you will have to copy the whole map interface and adapt it in the momonorphic case -- it's not much work.