haskell - 插入新绑定(bind)时是否复制了整个 map ？

Question

我想更好地了解例如实习生。数据. map 。当我在 Map 中插入一个新绑定(bind)时，由于数据的不变性，我得到一个与旧数据结构相同的新数据结构加上新绑定(bind)。

我想了解这是如何实现的。编译器最终是否通过复制整个数据结构来实现这一点，例如数以百万计的绑定(bind)？通常可以说可变数据结构/数组(例如 Data.Judy)或命令式编程语言在这种情况下表现更好吗？在字典/键值存储方面，不可变数据有什么优势吗？

Answer 1

Map建立在树数据结构之上。基本上，一个新的Map value 被构造，但它几乎完全被指向旧结构的指针填充。由于 Haskell 中的值永远不会改变，这是一种安全且非常重要的优化，称为共享。

这意味着您可以拥有相同数据结构的许多相似版本，但只有不同的树的分支会被重新存储；其余的只是指向分支原始副本的指针。当然，如果你扔掉旧的 Map ，您更改的分支将被垃圾收集器回收。

共享是不可变数据结构性能的关键。您可能会发现 this Wikipedia article有帮助的；它有一些启发性的图表，显示了修改后的数据如何通过共享来表示。