纯函数自底向上树算法
假设我想编写一个处理不可变树数据结构的算法，该数据结构以叶子列表作为输入。它需要返回一棵新树，并对旧树从这些叶子向上进行更改。
我的问题是，如果不重建整个树检查叶子是否在列表中，似乎没有办法做到这一点纯粹的功能，因为你总是需要返回一个完整的新树作为操作的结果，并且你可以' t 改变现有的树。
这是函数式编程中的一个基本问题，只能通过使用更适合的算法来避免，还是我错过了一些东西？
编辑：我不仅想避免重新创建整个树，而且功能算法应该具有与变异变体相同的时间复杂度。
Say I wanted to write an algorithm working on an immutable tree data structure that has a list of leaves as its input. It needs to return a new tree with changes made to the old tree going upwards from those leaves.
My problem is that there seems to be no way to do this purely functional without reconstructing the entire tree checking at leaves if they are in the list, because you always need to return a complete new tree as the result of an operation and you can't mutate the existing tree.
Is this a basic problem in functional programming that only can be avoided by using a better suited algorithm or am I missing something?
Edit: I not only want to avoid to recreate the entire tree but also the functional algorithm should have the same time complexity than the mutating variant.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
到目前为止我见过的最有希望的（诚然不是很长......）是 Zipper数据结构：它基本上保留了一个单独的结构，即从节点到根的反向路径，并对这个单独的结构进行本地编辑。
它可以进行多次本地编辑，其中大部分都是恒定时间，并将它们一次性写回树（重建到根的路径，这是唯一需要更改的节点）。
Zipper 是 Clojure 中的标准库（请参阅标题Zippers - 功能树编辑 ）。
还有原始版本Huet 的论文，并在 OCaml 中实现。
免责声明：我已经编程很长时间了，但几周前才开始函数式编程，直到上周才听说过树的函数式编辑问题，所以我很可能还有其他解决方案不知道。
尽管如此，Zipper 看起来还是能满足人们的大部分愿望。如果 O(log n) 或以下还有其他替代方案，我想听听。
The most promising I have seen so far (which admittedly is not very long...) is the Zipper data structure: It basically keeps a separate structure, a reverse path from the node to root, and does local edits on this separate structure.
It can do multiple local edits, most of which are constant time, and write them back to the tree (reconstructing the path to root, which are the only nodes that need to change) all in one go.
The Zipper is a standard library in Clojure (see the heading Zippers - Functional Tree Editing).
And there's the original paper by Huet with an implementation in OCaml.
Disclaimer: I have been programming for a long time, but only started functional programming a couple of weeks ago, and had never even heard of the problem of functional editing of trees until last week, so there may very well be other solutions I'm unaware of.
Still, it looks like the Zipper does most of what one could wish for. If there are other alternatives at O(log n) or below, I'd like to hear them.
您可能会喜欢阅读
http://lorgonblog.spaces.live.com/博客/cns!701679AD17B6D310!248.entry
You may enjoy reading
http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!248.entry
这取决于您的函数式编程语言。例如，在 Haskell 中，它是一种 Lazy 函数式编程语言，结果是在最后一刻计算的;当真正需要它们时。
在您的示例中，假设是因为您的函数创建了一棵新树，所以必须处理整个树，而实际上该函数只是传递到下一个函数，并且仅在必要时执行。
惰性计算的一个很好的例子是 Haskell 中的 erastothenes 筛，它通过以下方式创建素数消除数字列表中当前数字的倍数。请注意，数字列表是无限的。摘自此处
This depends on your functional programming language. For instance in Haskell, which is a Lazy functional programming language, results are calculated at the last moment; when they are acutally needed.
In your example the assumption is that because your function creates a new tree, the whole tree must be processed, whereas in reality the function is just passed on to the next function and only executed when necessary.
A good example of lazy evaluation is the sieve of erastothenes in Haskell, which creates the prime numbers by eliminating the multiples of the current number in the list of numbers. Note that the list of numbers is infinite. Taken from here
我最近编写了一个算法，它完全符合您的描述 - https://medium.com/hibob-engineering/from-list-to-immutable-hierarchy-tree-with-scala-c9e16a63cb89
它分两个阶段工作：
一些注意事项：
没有节点突变，结果是一个不可变树
复杂度为O( n)
忽略传入列表中的循环引用
I recently wrote an algorithm that does exactly what you described - https://medium.com/hibob-engineering/from-list-to-immutable-hierarchy-tree-with-scala-c9e16a63cb89
It works in 2 phases:
Some caveats:
No Node mutation, The result is an Immutable-tree
The complexity is O(n)
Ignores cyclic referencing in the incoming list