functional-programming - 如果我在 OCaml 中使用列表创建图形数据结构/算法会有效吗？

Question

我现在开始写graph相关data structure的algorithms。OCaml

我愿意尝试在 OCaml 中以函数式的方式编写它们，即避免使用array、可变类型等。

但是，如果我使用 编写所有这些list，它会有效还是有意义？

Answer 1

您不需要对所有内容都使用列表。库中还有许多其他不可变的数据结构，或者您可以定义自己的。您可以将图视为从节点到后继列表的映射。我已经使用这种表示在 OCaml 中编写了大量的图形处理代码，而且我总是对结果非常满意。

更新

这是我正在谈论的表示的草图。它假设您使用 uniqe 字符串标记您的节点。请注意（正如 monniaux 评论的那样）使用后继列表可能更适合稀疏图而不是密集图。

type label = string
module GMap = Map.Make(struct type t = label let compare = compare end)
type 'a node = label * 'a * label list
type 'a graph = 'a node GMap.t

let empty = GMap.empty

let add (label: label) (contents: 'a) successors (graph: 'a graph) : 'a graph =
    GMap.add label (label, contents, successors) graph

制作一个只包含长度为 2 的循环的图：

# let g = add "a" () ["b"] (add "b" () ["a"] empty);;
val g : unit graph = <abstr>

Answer 2

这一切都取决于您希望实现的算法类型以及您是否希望考虑稀疏图或密集图。密集图通常由矩阵表示（顺便说一句，矩阵可以保持不变并在功能上使用）。

如果您需要具有 O(1) 更新的数组（例如用于标记节点），您仍然可以通过使用将数组呈现为可更新结构的包装库以功能方式使用它们，每次都提供一个新数组。诀窍是通过将可变数组保持为“头”版本并将过去的版本保持为“头”的增量来实现这些更新。这将所有必要的问题都包含在一个模块中，至少在语义上，一个功能接口。

如果您有稀疏图，通常会谈论“邻接表”。我认为使用它们是一个坏主意，除非图形非常稀疏（绝对意义上的小度节点），因为它们具有 O(n) 访问权限。我认为二叉树Set更合适，因为它们允许在 O(log n) 中进行测试。