有没有一个开源的 F# 树数据结构？

Question

我需要一个像这样简单的树形结构，带有所有调整 -

type 'a Tree =
    | Leaf of 'a
    | Branch of 'a Tree list

肯定有类似的东西已经存在，包括添加、删除、映射、筛选、折叠等函数，但我找不到。甚至从OCaml也没有一个我可以移植的...如果必要，我可以自己编写。

编辑：更改树结构以使其更明显。

- Bryan Edds

---

我很惊讶FSharpx没有这个。 - Daniel

不知道这是否有帮助——我发现一个基本的Tree<_>类型，带有ofSeq和toSeq函数，在大多数情况下已经足够了。然后，您可以按照以下基本顺序利用Seq模块中的map、reduce等函数：toSeq > Seq.(op) > ofSeq。这还使得更改遍历顺序（DFS、BFS）变得更容易，而不是将其嵌入到每个函数中。 - Daniel

你的树对我来说有点奇怪。你可以有 Branch(_, [Empty, Empty, Empty, ...]) 吗？ - Daniel

是的，我认为还差一点。但是，今天是星期五，我的大脑很疼...只要我能清楚地表达我想要的东西就可以了 :) - Bryan Edds

如果您想分享您的计划，我们可以提供更具体的建议。 - Daniel

Answer 1

我认为困难在于一个简单的树（例如add Tree Tree）不会被任何人使用。如果没有指定更具体的树类型，您将不得不通过扫描来实现所有这些方法，从而降低性能。

此外，不可变树的原地更新非常昂贵，因为在典型设计中共享数据结构很少。

最后，如果允许任何形式的回溯，则必须完全重写不可变树。

- Guvante

---

是的，我想我会从叶子到根构建我的树，所以也许添加函数并不太有用。不过，当适当使用数据结构时，我仍然看到一些很好的通用用途。 - Bryan Edds

@BryanEdds：问题在于没有一个好的折中方案。如果你包含了一堆无用的函数，那么没有人会使用它们；如果你不包含这些函数，那么你就不能提供任何价值了。 - Guvante