type +'a t in Ocaml Map Library?

Question

I'm working with Ocaml's built-in Map library for a problem set, and I'm having trouble accessing the datatype of a map itself. This is supposed to be the third implementation of a dictionary (the first two being a list and an unbalanced binary search tree), and part of the functor I have to implement is "type dict", which is the datatype of the actual dictionary. For list, type dict was (D.key * D.value) list; for the tree, type dict was Empty | Branch((D.key * D.value), dict, dict). The Ocaml documentation says:

type +'a t 
The type of maps from type key to type 'a.

This seems like what I need, but I can't seem to use it correctly. M is my Map.Make module, by the way. I've tried

type dict = M.t
type dict = M.+D.value t
type dict = M.+

But I keep getting error messages. Can anyone help? Thanks so much!

Answer 1

+ is a variance annotation, it is not part of the name. The syntax of parametrized type is param type or (param, param, ...) type in OCaml : int list, (int, string) Hashbl.t. What you want here is D.value M.t.

Answer 2

You can find out yourself by asking the ocaml compiler: ocamlc -i file.ml

To create a map via Map.Make from the standard ocaml library, this file would look like this (for a map from int to 'a):

module Intmap = Map.Make (struct
   type t = int
   let compare = Pervasives.compare
end)

The ocaml compiler will give you something like this (when calling ocamlc -i mymap.ml):

module Intmap :
   sig
      type key = int
      type +'a t
      val empty : 'a t
      ...
end