- OCamlのを

Question

私は最初intは任意のタグであるタイプ

type lazy_node_t = LazyNode of int * lazy_node_t Lazy.t list;; 

のノードとの（有向）グラフがあると、リストはリストであります現在のノードからアクセス可能な遅延ノード。

これをグラフのtype node_t = Node of int * node_t list,に変更する方法はありますか。変更可能な値は一切使用しません。？例えば、配列を使って可能であることが分かります。

ありがとうございます！

Answer 1

なぜ私は可変値を避けたいのかわかりませんが、その理由は効率が問題ではないことを意味していると思います。

原則として、変更可能な値を使用するアルゴリズムを変更しないアルゴリズムに切り替えることができます。特に配列の場合、代わりにMap.Make(Int).tを使用できます。Intはstruct type t=int let compare=compare endです。

UPDATE：

だけ明確にする：私は心の中でモジュールIntの整数をグラフタグとは何の関係もありませんしたもので。それらは配列の代わりのインデックスです。

私の答えは、中間構造としてのみ配列が必要であるという前提に基づいています。つまり、配列node_t = Node of int * node_t listの望ましい値を出力する配列を使用するソリューションがあります。ジェフリースコフィールドの答えは、私が誤解している可能性があることを示唆している。タイプnode_t = Node of int * node_t arrayの値を出力するソリューションしかありません。その場合、私の答えは役に立たない。

Answer 2

結果に含まれるすべてのノードに名前をバインドできる場合は、let recで循環構造を作成できます。一般的な場合、すべてのノードに名前を付けることはできません。したがって、変更のない循環構造を作る方法はありません。これは、少なくとも、私が締結したものです。

Answer 3

私の2番目の解釈によれば、2番目の答えです。

方法はありますが、醜いです。

次に、変更可能性は値の内部表現に影響を与えないという事実を利用します。したがって、以下のタイプは、node_immutableと内部的に区別できません。だから我々はそうのようなグラフの変更可能なバージョンを作成することができます

let rec mutable_node1 = {tag_mutable=1; out_neighbours_mutable=[mutable_node2];} 
    and mutable_node2 = {tag_mutable=2; out_neighbours_mutable=[mutable_node3];} 
    and mutable_node3 = {tag_mutable=3; out_neighbours_mutable=[mutable_node1];} 

、その後、マーシャリングを通じて不変のコピーを作成します。

let node1 = (
    Marshal.from_string (Marshal.to_string mutable_node1 []) 0 
    : node_immutable)