module - OCaml: ツリー関数

Question

木を扱うためのモジュールや関数はありますか? 次のようなタイプがあります。

    type t =
        Leaf of string (* todo: replace with 'a *)
      | Node of string * t list

サブツリーの挿入、削除などに苦労しています。

グーグルを使用しましたが、何も見つかりません。

Answer 1

過去に、私はocamlgraphを使用しました。これは簡単なライブラリではありませんが、ノードを挿入してパスを変更する必要がある場合は、それがうまくいく可能性があります.

そして、言語ドキュメントから抽出:

バリアント型の最も一般的な使用法は、再帰的なデータ構造を記述することです。たとえば、二分木のタイプを考えてみましょう。

#type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;;
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree

この定義は次のようになります: 'a 型 (任意の型) の値を含む二分木は、空であるか、'a 型の値を 1 つ含み、'a 型の値を含む 2 つのサブツリー、つまり 2 つの値を含むノードです。 'a btree.

二分木の操作は、型定義自体と同じ構造に従う再帰関数として自然に表現されます。たとえば、次の関数は、順序付けられたバイナリ ツリーでルックアップと挿入を実行します (要素は左から右に増加します)。

#let rec member x btree =
   match btree with
     Empty -> false
   | Node(y, left, right) ->
       if x = y then true else
       if x < y then member x left else member x right;;
val member : 'a -> 'a btree -> bool = <fun>

#let rec insert x btree =
   match btree with
     Empty -> Node(x, Empty, Empty)
   | Node(y, left, right) ->
       if x <= y then Node(y, insert x left, right)
                 else Node(y, left, insert x right);;
val insert : 'a -> 'a btree -> 'a btree = <fun>

お役に立てれば

Answer 2

OCaml 標準ライブラリのソースにあるモジュール Set の実装を読んでください。それらは二分木で実装されており、あなたのものより少しだけ洗練されています。

（定義したように見える子のリストを持つのではなく、二分木から始めることをお勧めします）

Answer 3

Matt McDonnellによるPtreeデータ型があり、必要なことを実行すると思います。

Answer 4

実際には、要素間に順序がある場合など、ツリーを機能させる方法によって異なります。

それ以外の場合は、ツリーで既知のアルゴリズムを使用できます。たとえば、C や Java などの他の言語での方法がわかれば、それを OCAML に変換するのを手伝うことができます。