Haskell中的复杂数据结构 - 它们如何工作？

问题描述

根据我的想法，Haskell中的变量是不可变的（因此，它们不是真正的'变量'）。在这种情况下，如果我们有一个复杂而大的数据结构，就像一个红黑树，我们应该如何实现实际改变数据结构的操作？

每次插入或删除元素时，创建树的副本？

解决方案

是的，解决方案是返回一个表示修改值的新数据结构，但是不需要复制您的示例的全部结构（红黑树），因为您只需将路径上的节点从根复制到插入的节点。这允许插入操作与命令版本相同的复杂性。

Chris Okasaki的

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?

解决方案

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中的复杂数据结构 - 它们如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！