3

抱歉，这似乎是一个显而易见的问题。

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

Data.map 是使用二叉树实现的（我读过），所以我只想确认在执行映射操作时（我相信它们将是旋转），解释器不会执行列表的深层副本，只是引用的浅层副本列表对吗？

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

提前致谢。

4

2 回答 2

4

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

有关详细信息，请阅读Boxed 和 Unboxed 类型之间的区别。

于 2013-09-15T12:58:43.413 回答
0

1）Integer那么慢Int

2）如果你有[(Integer, [(Integer, Integer)])]

Data.Map您不仅可以创建，Map Integer [(Integer, Integer)]还可以使用Map Integer (Map Integer Integer)

3）如果您使用Int而不是Integer，您可以使用更快的数据 -IntMap来自Data.IntMap：IntMap (IntMap Int)

4）每个方法的复杂性都写在描述中： Data.IntMap.Strict和这里Data.IntMap.Lazy：

map :: (a -> b) -> IntMap a -> IntMap b
O(n). Map a function over all values in the map.
于 2013-09-17T14:55:42.937 回答