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

问题描述

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

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

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

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 ?

推荐答案

您不必复制整个树来进行更改；您可以共享大部分结构.见例如本博客中的图表，或本次演讲 由 Rich Hickey 在 Clojure 上(请参阅关于哈希尝试的讨论大约进行到一半).

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屋！