OCaml directed graphs vertex module

Question

I have seen some graphs vertex signatures and even come up with my own:

module type VERTEX = sig
    type t
    type label

    val equal : t -> t -> bool
    val create : label -> t
    val label : t -> label  
end

But I have completely no idea how to implement it as a module. What types should t and label be? How can I create a t based on a label? And how do I get the label from a t?

Answer 1

Implementing a module based on a signature is like a mini puzzle. Here's how I would analyze it:

The first remark I have when reading that signature, is that there is no way in that signature to build values of type label. So, our implementation will need to be a bit larger, maybe by specifying type label = string.

Now, we have:

val create : label -> t
val label : t -> label

Which is a bijection (the types are "equivalent"). The simplest way to implement that is by defining type t = label, so that it's really only one type, but from the exterior of the module you don't know that.

The rest is

type t
val equal: t -> t -> bool

We said that label = string, and t = label. So t = string, and equal is the string equality.

Boom! here we are:

module String_vertex : VERTEX with type label = string = struct
  type label = string
  type t = string

  let equal = String.equal

  let create x = x
  let label x = x
end

The VERTEX with type label = string part is just if you want to define it in the same file. Otherwise, you can do something like:

(* string_vertex.ml *)
type label = string
type t = string

let equal = String.equal

let create x = x
let label x = x

and any functor F that takes a VERTEX can be called with F(String_vertex). It would be best practice to create string_vertex.mli with contents include VERTEX with type label = string, though.