Haskell中的复杂数据结构-它们是如何工作的？
Haskell中的复杂数据结构-它们是如何工作的？
提问于 2011-01-05 02:57:14
据我所知，Haskell中的变量是不可变的(因此，它们不是真正的“变量”)。
在这种情况下，如果我们有一个复杂的大数据结构，比如红黑树，我们应该如何实现真正改变数据结构的操作呢？
是否在每次插入或删除元素时创建树的副本？
回答 2
Stack Overflow用户
回答已采纳
发布于 2011-01-05 03:08:34
是的，解决方案是返回一个表示修改后的值的新数据结构，但是对于您的示例来说，不需要复制整个结构(红黑树)，因为您只需将路径上的节点从根复制到插入的节点即可。这允许插入操作具有与命令式版本相同的复杂性。
Chris Okasaki的Purely functional data structures包含了许多不可变数据结构的实现-这本书是他的phD论文的修改版本，您可以在这里找到here
Stack Overflow用户
发布于 2011-01-05 03:19:16
你对复制的直觉正是你应该思考的正确方向。然而，“复制”是由Haskell运行时智能实现的。例如，给定
data Tree = Empty | Branch Tree Integer Tree您可以实现一个函数来替换左分支：
replaceLeft :: Tree -> Tree -> Tree
replaceLeft (Branch _ i r) newLeft = Branch newLeft i r结果并不是您创建了新树的整个副本，因为这是不必要的。值i以及树r和newLeft没有变化，因此我们不必将它们的内容复制到新的内存中。
创建的新Branch (这是本例中唯一的实际分配:创建结构以保存Integer上的左/右树)仍然引用来自旧分支的完全相同的值，不需要复制！
由于数据结构是不可变的，因此这样做没有什么坏处。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4597262
复制相关文章
相似问题