Haskell不可变数据结构 - Map数据类型

Question

我对Haskell - Map中的这种数据类型感到困惑.特别是,有一个函数调用插入(来自Data.Map模块),它允许您将新值附加到Map数据结构.所以,这是我的困惑.如果haskell数据结构是不可变的,那么如何将新数据插入到现有的Map数据结构中？

Answer 1

insert实际上并没有修改输入Map.它返回一个新的 Map,包含与原始条目相同的条目Map,以及您要插入的条目.

但是,在引擎盖下,编译器可能实际上不必将所有旧条目复制到新条目中Map; 如果它确定没有其他东西在使用输入,它可以重用原始文件Map.不变性是语言的一种属性,不一定是语言的实现.

如果编译器可以确定没有对旧值进行引用,则允许编译器*就地修改值,但据我所知,它们都没有*做*.但并非所有都丢失了:`Map`是作为树实现的,未改变的子树可以(和)在旧的`Map`和新的`之间共享.这是允许的,是否有其他东西使用输入`Map`(因为不变性保证共享不会导致别名问题). (4认同)
实际上,在基于BST的平衡实现中,`insert`只需要复制树的O(log N)节点,并重用大部分旧的(不可变的)树. (2认同)