据我所知,Haskell中的变量是不可变的(因此,它们不是真正的“变量”)。
在这种情况下,如果我们有一个复杂的大数据结构,比如红黑树,我们应该如何实现真正改变数据结构的操作呢?
是否在每次插入或删除元素时创建树的副本?
发布于 2011-01-05 03:08:34
是的,解决方案是返回一个表示修改后的值的新数据结构,但是对于您的示例来说,不需要复制整个结构(红黑树),因为您只需将路径上的节点从根复制到插入的节点即可。这允许插入操作具有与命令式版本相同的复杂性。
Chris Okasaki的Purely functional data structures包含了许多不可变数据结构的实现-这本书是他的phD论文的修改版本,您可以在这里找到here
发布于 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
上的左/右树)仍然引用来自旧分支的完全相同的值,不需要复制!
由于数据结构是不可变的,因此这样做没有什么坏处。
https://stackoverflow.com/questions/4597262
复制相似问题