函数式编程：一成不变的数据结构效率

Question

我不明白，FP编译器怎么能有不可变的数据结构处理速度快，不炸掉堆栈中的代码等

例如，插入操作树，它有在添加新节点并返回复制的树之前复制整个树，而不需要将指针添加到新节点的命令式couterpart。如果插入操作运行数百万次，则会占用大量内存，并且树越大，复制越慢。 FP编译器如何实际优化这个？

Answer 1

您不必复制整棵树来进行更改;你可以分享大部分的结构。见例如Rich Hickey在Clojure上的this blog或this talk中的图表（请参阅关于中途散列尝试的讨论）。

Answer 2

看一看Zipper data structure。

Answer 3

编译器不会真的优化它，它是编码时必须编程的东西。在优秀的纯功能数据结构（book,thesis）中解释了这样做的技术。

Answer 4

如果垃圾收集器正在完成其工作，那么旧数据结构的副本在不再使用时将被收回。