How to use Map as a data type inside of other module

Learning
1

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?

2

The following works:

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.

1 Like
3

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

Cheers,
Nicolas

1 Like
4

I was actually able to come up with second solution myself :). I will read up on things You mentioned. Thank You.

5

I managed to solve it using a functor, but our professor suggested first class modules too, so I will look into your solution as well, thank you.