Haskell 中的复杂数据结构 - 它们如何工作？
正如我所发现的，Haskell 中的变量是不可变的（因此，它们并不是真正的“变量”）。
在这种情况下，如果我们有一个复杂的大数据结构，比如红黑树，我们应该如何实现实际改变数据结构的操作？
每次插入或删除元素时都创建树的副本吗？
As I figured out, variables in Haskell are immutable (thus, they are not really `variables').
In this case, if we have a complex and big data structure, like a red-black tree, how are we supposed to implement operations that actually change the data structure?
Create a copy of the tree each time an element is inserted or deleted?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，解决方案是返回一个表示修改值的新数据结构，但是不需要复制示例的整个结构（红黑树），因为您只需将路径上的节点从根复制到插入的节点。这使得插入操作具有与命令式版本相同的复杂性。
克里斯·冈崎的 纯函数式数据结构包含许多不可变数据结构的实现 - 这本书是他的博士论文的修改版本，你可以找到此处
Yes, the solution is to return a new data structure which represents the modified value, however there is no requirement to copy the entire structure for your example (red-black trees) since you can just copy the nodes on the path from the root to the inserted node. This allows the insert operation to be the same complexity as the imperative version.
Chris Okasaki's Purely functional data structures contains a number of implementations of immutable data structures - this book is a modified version of his phD thesis which you can find here
你对复制的直觉正是你应该思考的正确方向。然而，“复制”是由 Haskell 运行时智能实现的。例如，假设
您可以实现一个函数来替换左分支：
结果并不是您创建新树的完整副本，因为这是没有必要的。值
i以及树r和newLeft保持不变，因此我们不必将它们的内容复制到新内存中。创建的新
Branch（这是本例中唯一真正的分配：创建用于保存Integer上左/右树的结构）仍然引用与旧分支完全相同的值，无需复制！由于数据结构是不可变的，因此这样做没有什么害处。
Your intuition about copying is exactly the right direction you should be thinking. However, the 'copying' intelligently implemented by the Haskell runtime. For example, given
You could implement a function to replace the left branch:
The result isn't that you create a entire copy of the new tree, as that isn't necessary. The value
iand the treesrandnewLeftare unchanged so we don't have to copy their contents into fresh memory.The new
Branchthat is created (this is the only real allocation in this example: the creation of the structure to hold the left/right trees on theInteger) still references the exact same values from the old branch, no copying needed!Since the data structures are immutable, there's no harm in doing this.