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

Question

正如我所知道的，Haskell 中的变量是不可变的(因此，它们并不是真正的“变量”)。

在这种情况下，如果我们有一个复杂的大数据结构，比如一棵红黑树，我们应该如何实现真正改变数据结构的操作呢？

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

Answer 1

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

克里斯冈崎的 Purely functional data structures包含许多不可变数据结构的实现——这本书是他的博士论文的修改版本，你可以找到 here