OCaml submodules with anonymous signatures in module types

Question

I am trying to implement a Trie that is generic over the types of its keys and values using Map.Make. This functor takes a Map.OrderedType and produces a module with a bunch of Map utilities defined inside it. However, the return module type of Map.Make is anonymous. I want to expose the particular Map implementation that my Trie is using under the hood in my TrieType module type.

Is there a way to refer to the return module type of Map.Make? Alternatively, is it possible to use something similar to transparent ascription in SML to expose the module M without insisting on a particular module type for it or hiding any of its members?

module OrderedStringType : Map.OrderedType = struct
    type t = string
    let compare = String.compare
end

module type TrieType = sig

    (* I want to expose the M submodule in the interface, but its
     * module type is anonymous *)
    (* here is some strawman syntax *)
    (* module M : Map.Make(Set.OrderedType) *)
    type 'a t
end

module Trie(X : Map.OrderedType) : TrieType = struct
    module M = Map.Make(X)

    type 'a t = EmptyTrie | Trie of 'a tChild
    and 'a tChild = {value : 'a option ; children : 'a t M.t}
end


module TruncatedTrie(X : TrieType) = struct
    (* Implementation to follow *)
end

Your example code is very hard to understand. The comments mention a Key submodule, which isn't present in the code. The module OrderedStringType appears to be unused in the code. (Furthermore you don't need to write your own compare function. There is a function String.compare. The < and > operators are no less polymorphic than the polymorphic compare function.) OCaml has a construct module type of ... that might do what you want, but I can't tell. — Jeffrey Scofield
I'm sorry. I should have cleaned this up a better before posting it, I'll try to make it more clear. What I am after is a way of referring to the signature that results when Map.Make is applied to a module satisfying Map.OrderedType. It sounds like using module type of I could recover it using a particular instance of Map.OrderedType ... — Gregory Nisbet

ivg ivg · Accepted Answer · 2015-12-25T19:55:03

The type of module produced by a Map.Make functor is not anonymous, but actually has a name: Map.S. You can extend or even hide fields from the signature:

module type Trie = sig
  include Map.S
  val new_method : t -> int
end

To hide a method, you can redefine it with some uninhabited type:

module type Trie = sig
  include Map.S
  val length : [> `trie_doesn't_have_length_method ]
end

The latter can be considered as a hack, since much cleaner approach would be to define you own signature.

OCaml submodules with anonymous signatures in module types

1 Answers