函数式编程:不可变的数据结构效率

rom*_*run 18 functional-programming

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

例如,在树中插入操作,它必须在添加新节点之前复制整个树并返回复制的树,而不是仅需要添加指向新节点的命令式couterpart.如果插入操作运行数百万次,则需要占用大量内存,并且当树更大时,复制将越来越慢.FP编译器如何实际优化这个?

Bri*_*ian 16

您不必复制整个树来进行更改; 你可以分享大部分结构.请参阅此博客中的图表,或者Rich Hickey在Clojure上的演讲(请参阅有关哈希尝试的讨论).


Ada*_*ode 7

编译器不会真正优化它,它是你必须在编码时专门编程的东西.在优秀的纯功能数据结构(书籍,论文)中解释了这样做的技术.