函数式编程：不变的数据结构效率 [英] functional programming: immutable data structure efficiency

问题描述

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

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

您不必复制整个树来进行更改;你可以分享大部分的结构。见例如此博客中的图表或 Rich Hickey在Clojure上的这个演讲（参见关于中途散列尝试的讨论） / p>

I don't understand, how FP compilers make the code dealing with immutable data structures fast, not blow up stack, etc.

For example, insert operation in tree, it has to copy the whole tree before adding the new node and return the copied tree, versus the imperative couterpart that only needs to add a pointer to the new node. If the insert operation is run millions times, it would take a load of memory, and copying will be slower and slower when the tree is bigger. How do FP compilers actually optimize this ?

解决方案

You don't have to copy the whole tree to make a change; you can share most of the structure. See e.g. the diagrams in this blog, or this talk by Rich Hickey on Clojure (see discussion of hash tries about halfway through).

这篇关于函数式编程：不变的数据结构效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！