OCamlでエッジリストを使用してグラフデータを作成する方法は？

Question

私は、分離した結合とレコードを使ってグラフを表現しようとしています。次のコードは構文エラーの原因となります。彼らがお互いを参照するときに2つの変数を定義する方法は？

type 'a vertex = 
    |Empty 
    |Vertex of 'a * 'a list;; (*a tuple consisting of any type of element and a list of vertex*); 

let v0 = Vertex(0,[v1]) in 
let v1=Vertex(1,[v0]);; 

私はへのコードを修正した場合：

let rec v0 = Vertex(0,[v1]) and v1=Vertex(1,[v0]);; 

私はV0を取得します：

[Vertex (1, 
    [Vertex (0, 
    [Vertex (1, 
     [Vertex (0, 
     [Vertex (1, 
      [Vertex (0, 
      [Vertex (1, 
       [Vertex (0, 
       [Vertex (1, 
        [Vertex (0, 
        [Vertex (1, 
         [Vertex (0, 
         [Vertex (1, 
          [Vertex (0, 
          [Vertex (1, 
           [Vertex (0, 
           [Vertex (1, 
            [Vertex (0, 
            [Vertex (1, 
             [Vertex (0, 
             [Vertex (1, 
              [Vertex (0, 
              [Vertex (1, 
               [Vertex (0, 
               [Vertex (1, 
                [Vertex (0, 
                [Vertex (1, 
                 [Vertex (0, 
                 [Vertex (1, 
                  [Vertex (0, 
                  [Vertex (1, 
                   [Vertex (0, 
                   [Vertex (1, 
                    [Vertex (0, 
                    [Vertex 
                    (1, 
                    [Vertex 
                    (0, 
                    [Vertex 
                    (1, 
                    [Vertex 
                    (0, 
                    [Vertex 
                    (1, 
                    [Vertex 
                    (0, 
                    [Vertex 
                    (1, 
                    [Vertex 
                    (0, 
                    [Vertex 
                    (1, 
                    [Vertex 
                    (0, 
                    [Vertex 
                    (1, 
                    [Vertex 
                    (0, 
                    [Vertex 
                    (1, 
                    [Vertex 
                    (0, 
                    [Vertex 
                    (1, 
                    [Vertex 
                    (0, 
                    [...])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])] 

です

何...私が欲しいものではない表示されますベスト・ウェイ頂点のリストまたは配列を含むグラフ・レコードを定義するには？あなたのタイプの定義に誤りがあり

Error: The type constructor array expects 1 argument(s), 
     but is here applied to 0 argument(s) 

Answer 1

：私は、次のメッセージが表示されます

type graph = { 
    vertex_set:array};; 

：もちろん、私はこれを行うことはできません。

type 'a vertex = 
    |Empty 
    |Vertex of 'a * 'a vertex list 

あなたはlet recを使用して、このタイプの値を定義することができます：

let rec v0 = Vertex(0, [v1]) and v1 = Vertex(1, [v0]) 

私の経験では、それはこの種の値に対処することは困難です私は、あなたが望むものをかなり確信しています。 OCamlは熱心な言語なので、循環値を計算するのは難しいです。

2番目の質問では、コンパイラはarray自体が型ではないことを伝えようとしています。配列がであると言う必要があります。あなたは頂点のリストではなく、配列（おそらく良いアイデアを）したい場合は

type 'a vertices = { 
    vertex_set: 'a vertex array; 
} 

、それは次のようになります。

type 'a vertices = { 
    vertex_set: 'a vertex list; 
} 

二つの問題を持っている私には思えます。まず、OCamlで型と値を指定する方法を学ぶ必要があります。これはあまり難しくないので、ここで良いアドバイスを受けることができます。次に、グラフを表現するために使用するデータ構造を決定する必要があります。これは難しく、全体的に最良の方法はありません。おそらく、それ自体がグラフであるデータ構造（上記のようなもの）を使用したくないでしょう。より現実的な可能性は、隣接行列、またはそれらの出て行くエッジのリストを持つ頂点の集合です。循環構造の作成を避けるには、をエッジリストに直接含めるのではなく、を頂点に参照することができます。たとえば、頂点が配列内にある場合は、配列インデックスを参照することができます。

ocamlgraphという名前のライブラリがありますが、これは私が思いつくものよりも優れたアイデアです。