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类型需要提供成员来读取left和right字段。编写此类对象的最惯用的 F# 方法是使用：

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)

但是，有什么理由（即 C# 兼容性）为什么不使用 F# 可区分联合？这样，您可以非常轻松地定义树数据结构并免费获得模式匹配：

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

Node(None, Some ..., 42)然后，您可以使用您编写的模式通过写入和模式匹配来构造节点。

于 2012-09-12T08:25:09.247 回答