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

Question

我对Haskell中的数据类型Map感到困惑。特别是，Data.Map模块中的insert函数允许将新值附加到Map数据结构中。因此，我很疑惑。如果Haskell的数据结构是不可变的，那么如何将新数据插入到现有的Map数据结构中呢？

- phage

---

你不能直接修改原来的地图，而是要创建一个包含新键的新地图。 - Willem Van Onsem

Answer 1

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

在幕后，编译器可能并不需要将所有旧条目复制到新的 Map 中；如果它确定没有其他内容使用输入的 Map，则可以重用原始的 Map。不可变性是语言的属性，而不一定是语言的实现。

- chepner

---

实际上，在基于平衡二叉搜索树的实现中，insert 只需要复制 O(log N) 个节点，并重用大部分旧（不可变）树。 - chi

如果编译器可以确定旧值没有被引用，它们允许就地修改值，但据我所知，它们没有这样做。但并非一切都失去了：Map 作为一棵树实现，未更改的子树可以（也确实）在旧 Map 和新 Map 之间共享。无论是否有其他内容正在使用输入的 Map，这是允许的（因为不可变性保证了共享不会导致别名问题）。 - Daniel Wagner

Answer 2

或许一个例子会更加清晰明了。

Prelude> let map1 = empty
Prelude> map1
fromList []

Prelude> let map2 = insert "Lemon" 6 map1
Prelude> map2
fromList [("Lemon", 6)]

Prelude> map1
fromList []

Prelude> let map3 = insert "Lime" 7 map2
Prelude> map3
fromList [("Lime", 7), ("Lemon", 6)]

Prelude> map2
fromList [("Lemon", 6)]

Prelude> map1
fromList []

每次我们定义一个新变量（map1，map2，map3），之前版本的Map完全保持不变。一旦我们定义了（例如）map1包含键"Lemon"，就再也不能更改该定义。我们可以创建一个包含其他键（或更少键）的新映射，但我们无法更改map1本身。

- MathematicalOrchid