functional-programming - 函数式编程:不变的数据结构效率

Question

我不明白，FP编译器如何使代码快速处理不可变数据结构，而不会炸毁堆栈等。

例如，在树中插入操作，它必须在添加新节点之前复制整个树并返回复制的树，而命令式的couterpart只需要向新节点添加指针。如果插入操作运行了数百万次，则将占用大量内存，并且当树较大时，复制将越来越慢。 FP编译器实际上如何对此进行优化？

Answer 1

您不必复制整个树即可进行更改；您可以共享大部分结构。参见例如this blog或Rich Hickey在Clojure上的this talk中的图表（请参阅有关哈希尝试的讨论）。