list - Data.map 中 haskell 列表的复杂性

Question

抱歉，如果这看起来是一个显而易见的问题。

我正在创建一个列表的 Data.map {实际上是一个整数元组和一个列表 (Integer, [(Integer, Integer)])} 用于为某些图形算法(例如 Dijkstras 和 Prims)实现优先级队列 + 邻接列表,

Data.map 是使用二叉树实现的(我读过)所以我只想确认在进行 map 操作时(我相信它们会旋转)解释器不会对列表进行深度复制，而只会进行浅层复制列表的引用对吗？

我这样做是为了在 haskell 中实现一个 prims 算法，该算法将在 O(nlogn + mlogn) 时间内运行，其中 n = no。顶点和 m = 没有。边缘，以一种纯粹的功能方式，如果列表存储在优先级队列中，则该算法将在该时间运行。我在网上找到的大多数 haskell 实现都没有达到这种复杂性。

提前致谢。

Answer 1

你是正确的，列表不会在你每次创建新的 Map 时被复制，至少如果你使用 GHC(其他实现可能也正确地做到这一点)。这是纯函数式语言的优点之一:因为数据不能被重写，所以不需要复制数据结构来避免你在命令式语言中可能遇到的问题。考虑一下 Lisp 的这段代码:

(setf a (list 1 2 3 4 5))
(setf b a)
; a and b are now both '(1 2 3 4 5).
(setf (cadr a) 0)
; a is now '(1 0 3 4 5).
; Careful though! a and b point to the same piece of memory,
; so b is now also '(1 0 3 4 5). This may or may not be what you expected.

在 Haskell 中，拥有像这样的可变状态的唯一方法是使用一个显式可变的数据结构，例如 State monad 中的某些东西(甚至这是伪造它(这是一件好事))。这种潜在的意外内存重复问题在 Haskell 中是不可想象的，因为一旦你声明 a 是一个特定的列表，它现在和永远都是那个列表。因为它保证永远不会改变，所以为应该相等的事物重用内存是没有危险的，事实上，GHC 正是这样做的。因此，当您创建具有相同值的新 Map 时，只会复制指向值的指针，而不是值本身。

有关更多信息，请阅读 the difference between Boxed and Unboxed types .