0

次の型を使用して、F# でツリー データ構造を表現しようとしています。

type Node = 
 val mutable left: Node option
 val mutable right: Node option
 val mutable value: int 

 new (l, r, v) = {left = l; right = r; value = v}

次のようなツリーを作成できます。

let root = new Node (Some (new Node (None, None, 2)), Some (new Node (None, None, 3)), 1)

パターン マッチングを使用してトラバースしたいと考えています。ただし、一致オブジェクトをパターン化する方法がわかりません。私はこのようなことを試しました：

let rec traverse r =
  match r with
  | Node (None, None, v) -> printfn "%d" v

パターンマッチングが間違っているため、そこで停止しました。

編集: Petricek の回答の後、識別された共用体やその他のクラス機能についてまだ読んでいないため、彼の提案をすべて使用しませんでした。これらのことについて詳しく知ったら、実装します。しかし、当分の間、これはどのように見えるかです：

type Node = 
 val left: Node option
 val right: Node option
 val value: int 

 new (l, r, v) = {left = l; right = r; value = v}

let (|Node|) (nd: Node) = (nd.left, nd.right, nd.value)

let root = new Node (Some (new Node (None, None, 2)), Some (new Node (None, None, 3)), 1)

let rec traverseLRtR r =
  match r with
  | Node (None, None, v) -> printfn "%d" v
  | Node (left, right, v) -> traverseLRtR left.Value; traverseLRtR right.Value; printfn "%d" v; 

traverseLRtR root

出力は次のとおりです。

2
3
1
4

1 に答える 1

3

タイプは、およびフィールドNodeを読み取るためのメンバーを提供する必要があります。このようなオブジェクトを作成する最も慣用的なF＃の方法は、次を使用することです。leftright

type Node(left:Node option, right:Node option, value : int) =
  member x.Left = left
  member x.Right = right

mutable例ではフィールドを変更していないため、フィールドの属性を削除しました（ただし、必要に応じて、 get＆setプロパティを使用して変更可能にすることができます）。また、より単純な暗黙のコンストラクター構文を使用するようにコードを変更しました。

次のステップとして、ノードのコンポーネントを返すアクティブなパターンを書くことができます。

 let (|Node|) (nd:Node) = (nd.Left, nd.Right)

ただし、F＃の識別された共用体を使用しない理由（つまり、C＃の互換性）はありますか？このようにして、ツリーデータ構造を非常に簡単に定義でき、パターンマッチングを無料で取得できます。

type Node = Node of Node option * Node option * int

Node(None, Some ..., 42)次に、作成したパターンを使用して、書き込みとパターンマッチングによってノードを構築できます。

于 2012-09-12T08:25:09.247 に答える