改变一个已构建的项目列表

Question

请理解我昨天才开始学习F#编程。

我有一个C#算法，其中我有一个节点列表，这些节点有一个子节点列表。

我该如何实现这个算法呢？我知道F#处理不可变类型，改变变量/对象是不被鼓励的。有什么好的方法可以解决这个问题吗？

C#

public class Node
{
    public List<Node> childrenNode = new List<Node>();
    public void AddChildren(Node node)
    {
        childrenNode.Add(node);
        node.Parent(this);
    }
}

F#

type Node(board:Board)=
     let mutable _childrenNode= Set.empty
     new() = Node()
     member AddChildren(node:Node)=

- Taufiq Abdur Rahman

---

你能否再多谈谈这个算法？现有的答案展示了如何逐行在F#中重新实现代码，但那并不是惯用方式-相比于创建节点和添加子节点，你可能希望事先收集所有子节点，然后在拥有完整列表后创建一个节点。 - Tomas Petricek

你的代码假设你创建一个包含空列表的节点，并且稍后添加到节点中的列表。这有点违反F#（和函数式编程）的习惯用法。我们不会创建一个带有占位符并稍后填充它的对象；我们创建内容已经填好的对象。 - Onorio Catenacci

Answer 1

在F#中表示树结构最简单的方法是使用辨别联合类型（discriminated unions）。以下是一个示例，还添加了在每个节点中存储值的功能：

type Tree<'T> =
    | Empty
    | Node of option<'T> * List<Tree<'T>>

因此，Tree类型包括两种情况——它可以是一个空树或者一个具有可选值和子节点列表的节点。

数据类型是不可变的，因此添加函数要求您传递一个现有的树以及一个附加节点的列表：

let addChildren (nodes: list<Tree<'T>>) (tree: Tree<'T>) : Tree<'T> =
    match tree with
    | Empty        -> Node (None, nodes)
    | Node (v,chs) -> Node (v, chs @ nodes)

模式匹配被用来区分Tree值的两种形状。

- esevelos

---

你的回答中隐含着一个观点，即在F#中，我们通常定义一个数据结构和作用于该结构上的函数，而不是像C#（OP试图转录的语言）那样，类包含自己的函数。 - Benjol

Answer 2

试一下这个：

type Node() as this =
    let children = new ResizeArray<Node>()
    let mutable parent : Node = this
    member this.Parent with get() = parent
    member this.AddChild(node : Node) =
       children.Add(node)
       node.Parent <- this

这实际上与您的C#代码相同，尽管正如您所说，这很大程度上违反了F#的思维方式。

- sircodesalot

---

你的代码片段中最后一行使用了等于测试，而非赋值操作。另外，要获取new Node<Node>()，您需要打开System.Collections.Generic——我建议使用F#别名new ResizeList<Node>()代替。 - Tomas Petricek

ResizeList<'T> 定义在哪里？ - sircodesalot

抱歉，我的意思是ResizeArray<'T>。 - Tomas Petricek