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

Question

我现在开始在OCaml中写graph相关的数据结构和算法。

我愿意尝试在 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>