I am trying to implement module for finite bijections. I want to represent bijections as Maps. So for example compostion of bijections should return map, but i do not know how to achieve this, since it is a module, and not data type.

module Make(Key : OrderedType) = struct
type key = Key.t
type t = Map.Make(key)
...
end

So I want type t to be a map, but this is obviously wrong, though I hope you get the idea. Could anyone point me in the right direction?

module Make(Key : Map.OrderedType) = struct
type key = Key.t
type 'a t = 'a Map.Make(Key).t
end

You can also do:

module Make(Key : Map.OrderedType) = struct
module Map = Map.Make(Key)
type key = Key.t
type 'a t = 'a Map.t
end

and the latter is what you should use if you intend on using any values defined by the output of Map.Make.

OCaml consists of multiple languages: the term language, the type language, the module language, and the interface language. Map.Make is a functor, so it belongs to the module language and expects a module as an argument. You simply forward the Key module that you receive as an argument to Map.Make.

Note that OCaml’s functors are applicative (in contrast to generative) meaning that Map.Make(Key).t = Map.Make(Key).t. Any uses of Map.Make(Key), anywhere in the program, contain equal types. In other words, if the client creates an instantiation of Map.Make(Key) for the same (named) input module Key, that module’s types will be compatible with the types defined in the Map.Make(Key) used in your module.

Below you will find a possible approach to representing finite maps using first class modules:

module Fin : sig
type ('a, 'b) t (* Finite maps 'a -> 'b *)
val id: compare:('a -> 'a -> int) -> 'a list -> ('a, 'a) t
(* The identity on a given domain *)
val compose: ('a, 'b) t -> ('b, 'c) t -> ('a, 'c) t
(* [compose f g] is [f] followed by [g]. *)
val make: compare:('a -> 'a -> int) -> ('a * 'b) list -> ('a, 'b) t
(* Define a function by specifying its graph. *)
end = struct
module type S = sig
type a
type b
module K : Map.OrderedType with type t = a
val m: b Map.Make(K).t
end
type ('a, 'b) t = (module S with type a = 'a and type b = 'b)
let compose (type a1 b1 c1) (f : (a1, b1) t) (g : (b1, c1) t) : (a1, c1) t =
let (module F) = f in
let (module G) = g in
let module FG = struct
type a = a1
type b = c1
module K = F.K
module FM = Map.Make(F.K)
module GM = Map.Make(G.K)
let m = FM.fold (fun a b m -> FM.add a (GM.find b G.m) m) F.m FM.empty
end in
(module FG)
let make (type a1 b1) ~(compare : a1 -> a1 -> int) (l : (a1 * b1) list) : (a1, b1) t =
let module F = struct
type a = a1
type b = b1
module K = struct type t = a1 let compare = compare end
module M = Map.Make(K)
let m = List.fold_left (fun m (a, b) -> M.add a b m) M.empty l
end in
(module F)
let id ~compare l =
make ~compare (List.map (fun a -> a, a) l)
end