を向ける私は署名頂点いくつかのグラフを見ても、私自身が出ている：OCamlはグラフの頂点モジュール
module type VERTEX = sig
type t
type label
val equal : t -> t -> bool
val create : label -> t
val label : t -> label
end
をしかし、私は完全にモジュールとしてそれを実装する方法は考えています。どのような種類のラベルを付ける必要がありますか？ラベルに基づいてtを作成するにはどうすればよいですか？そして、私はどのようにラベルをtから得るのですか？
署名に基づいてモジュールを実装することは、ミニパズルのようなものです。
このシグネチャを読み取ったときの最初の発言は、そのシグネチャにはタイプlabelの値を作成する方法がないということです。ですから、私たちの実装は少し大きくする必要があります。おそらくtype label = stringを指定してください。
は今、私たちは持っている：
val create : label -> t
val label : t -> label
全単射（タイプは "同等" です）です。これを実装する最も簡単な方法は、type t = labelを定義することです。実際には1つのタイプにすぎませんが、モジュールの外側からはそれは分かりません。
残りの部分は、我々はlabel = string、およびt = labelと言っ
type t
val equal: t -> t -> bool
です。したがって、t = string、およびequalは、文字列の等価です。
ブーム！ここでは、次のとおりです。
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
VERTEX with type label = string部分は、あなたが同じファイルにそれを定義したいだけの場合です。
(* string_vertex.ml *)
type label = string
type t = string
let equal = String.equal
let create x = x
let label x = x
とF(String_vertex)で呼び出すことができVERTEXを取る任意のファンクタF：そうでなければ、あなたのような何かを行うことができます。 string_vertex.mliをコンテンツinclude VERTEX with type label = stringで作成することをお勧めします。
私はGraphlibの著者です。私はこの質問が私の心に直接当たるので、私は渡すことができません。正直なところ、私はこの質問に何百万回もオフラインで尋ねられ、決して良い答えを出すことはできませんでした。
実際の問題は、OCamlGraphライブラリのグラフインターフェイスがすべて乱されていることです。私たちはGraphlibを修正しようと試みました。しかし、OCamlGraphはGraphアルゴリズムの貴重なリポジトリであるため、OCamlGraphインターフェイスと互換性があるという制約があります。私たちにとっての主な問題は、基本的にはラベルのセットとノードのセットの間に双射を確立するこのVertexインターフェースでした。これは理にかなっていないので、人々は通常これに遭遇します。なぜなら、同じものであれば、ラベルと頂点の2種類が必要なのはなぜですか？実際
、VERTEXインタフェースの最も単純な実装では、その場合には、次のモジュール
module Int : VERTEX with type label = int = struct
type t = int
type label = int
let create x = x
let label x = x
end
で、我々は、実際のラベルのセットと頂点の集合との間の（アイデンティティendofunctor介して）些細な全単射を有します。
しかし、より深い表情は、全単射は1対1のマッピングであるとして署名
val create : label -> t
val label : t -> label
は、本当に全単射ではないことを私たちに示しています。これは実際には型システムによって要求されたり強制されたりしません。例えば、create関数は、をtに投射することができます。ここで、labelは、頂点ファミリのいくつかの特有の要素です。それに対応して、labelの機能は、特有のラベルを返し、他のすべてを忘れるファンクタを忘れる可能性があります。このアプローチを考える
は、我々は別の実装持つことができます。その実装では
module Labeled = struct
type label = int
type t = {
label : label;
data : "";
}
let create label = {label; data = ""}
let label n = n.label
let data n = n.data
let with_data n data = {n with data}
let compare x y = compare x.label y.label
end
を、我々は、ノードのIDとしてラベルを使用して、任意の属性は、ノードに接続することができます。この解釈では、create機能は、すべてのノードセットをequivalence classesのセットに分割します。クラスのすべてのメンバーは同じアイデンティティーを共有します。すなわち、それらは異なる時間またはスペースで同じ実世界エンティティを表します。たとえば、
type color = Red | Yellow | Green
module TrafficLight = struct
type label = int
type t = {
id : label;
color : color
}
let create id = {id; color=Red}
let label t = t.id
let compare x y = compare x.id y.id
let switch t color = {t with color}
let color t = t.color
end
このモデルでは、トラフィックライトをID番号で表します。 color属性は信号機のアイデンティティには影響しません（信号機のライトが別の色に切り替わっても、それは同じ交通信号ですが、関数型プログラミング言語では2つの異なるオブジェクトで表されます）。
上記の表現の主な問題は、すべてのグラフの教科書では、ラベルが逆の意味で使用されるということです - 不透明な属性として。教科書では、交通標識の色をラベルとして参照します。ノード自体はintとして表現されます。だからこそ、私はOCamlGraphのインターフェースが混乱していると言います（そして、結果的にGraphlibインターフェースも）。したがって、教科書との矛盾を避けたい場合は、ラベルなしのグラフを使用する必要があります（intはおそらくノードの最も良い表現です）。また、ノードにアトリビュートを追加する必要がある場合は、外部有限マップ、つまり配列、マップ、連想リスト、またはその他の辞書を使用できます。それ以外の場合、ラベルはラベルではなく、ノードであることを覚えておく必要があります。このすべて言ったでは
は、のは、グラフの頂点のためのより良いインターフェースを指定してみましょう：
module type VERTEX = sig
type id
type label
type t
val create : id -> t
val id : t -> id
val label : t -> label
val with_label : t -> label -> label
end
提唱しているインタフェースは（したがってOCamlGraph付き）あなたのインタフェースと互換性があり、それは名前の変更同型を法であるとして（すなわちlabelをidに改名しました。また、効率の良いラベルなしノードを作成することもできます。ここでは、外部マッピングに頼ることなく任意の情報をノードに付加することができます。id = t