f# - 通过简单的图形示例在 F# 中使用类型进行设计的一些困难

Question

有定向图:



我们正在向它添加节点和边:



然后删除其他一些(根据算法，这里无关紧要):



我曾尝试在 F# 中这样做，但由于我的经验不足，我无法正确选择架构决策。

open System.Collections.Generic

type Node = Node of int
type OGraph(nodes : Set<Node>,
            edges : Dictionary<Node * int, Node>) =
    member this.Nodes = nodes
    member this.Edges = edges

let nodes = set [Node 1; Node 2; Node 3]
let edges = Dictionary<Node * int, Node>()
Array.iter edges.Add [|
    (Node 1, 10), Node 2;
    (Node 2, 20), Node 3;
|]
let myGraph = OGraph(nodes, edges)

myGraph.Nodes.Add (Node 4)
myGraph.Edges.Add ((Node 2, 50), Node 4)

myGraph.Edges.Remove (Node 2, 20)
myGraph.Nodes.Remove (Node 3)

如何添加空节点？我的意思是，它可能是 3 或 4 甚至 100500。如果我们添加没有数字的节点，那么我们如何使用它来创建边缘？ myGraph.Edges.Add ((Node 2, 50), ???)在命令式范式中，由于使用命名引用和空值，这很简单，我们可以创建 Node newNode = new Node()然后使用此引用 newNode ，但似乎在 F# 中这是一个不好的做法。

我应该指定单独的类型 Node 和 Edge 还是使用简单类型？或者可能是其他一些更复杂的表示？

使用常见的 .NET 可变集合(HashSet、Dictionary 等)还是特殊的 F# 集合(Set、Map 等)更好？如果集合很大，每次更改集合时都复制整个集合在性能方面可以接受吗？

Answer 1

图本身很容易建模。你可以这样定义它:

type Graph = { Node : int option; Children : (int * Graph) list }

如果愿意，您可以使用类型别名或自定义类型代替原始类型 int 对其进行更多修饰。值(value)观，但这是基本思想。

您可以对 OP 中描绘的三个图形进行建模，如下所示。我使用的格式看起来很冗长，但我特意用这种方式格式化值以使结构更清晰；如果您愿意，您可以以更紧凑的形式编写这些值。

let x1 =
    {
        Node = Some 1;
        Children =
            [
                (
                    10,
                    {
                        Node = Some 2;
                        Children =
                            [
                                (
                                    20,
                                    {
                                        Node = Some 3;
                                        Children = []
                                    }
                                )
                            ]
                    }
                )
            ]
        }
let x2 =
    {
        Node = Some 1;
        Children =
            [
                (
                    10,
                    {
                        Node = Some 2;
                        Children =
                            [
                                (
                                    20,
                                    {
                                        Node = Some 3;
                                        Children = []
                                    }
                                );
                                (
                                    50,
                                    {
                                        Node = None;
                                        Children = []
                                    }
                                )
                            ]
                    }
                )
            ]
        }
let x3 =
    {
        Node = Some 1;
        Children =
            [
                (
                    10,
                    {
                        Node = Some 2;
                        Children =
                            [
                                (
                                    50,
                                    {
                                        Node = Some 3;
                                        Children = []
                                    }
                                )
                            ]
                    }
                )
            ]
        }

注意 int option的使用捕获节点是否具有值。
Graph type 是 F# 记录类型，并使用 F# 主力 list为了 child 。这将是我的默认选择，只有当性能成为问题时，我才会考虑其他数据类型。列表很容易使用。