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

Question

正如我所知,Haskell中的变量是不可变的(因此,它们实际上不是"变量").

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

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

Answer 1

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

Chris Okasaki的纯功能数据结构包含许多不可变数据结构的实现 - 这本书是他的博士论文的修改版本,你可以在这里找到

Answer 2

你对复制的直觉正是你应该思考的正确方向.但是,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)仍引用旧分支中完全相同的值,无需复制!

由于数据结构是不可变的,因此这样做没有任何害处.