haskell - 如何在 Haskell 中模拟指针？

Question

我正在尝试在 Haskell 中实现 Dijkstra 的算法。我已经使用树实现了一个二叉堆。在算法中，当前顶点的邻居键应该在堆中更新。如何在 Haskell 中模拟指向堆中值的指针？如何在每次操作后堆都发生变化时快速访问堆中的元素？

Answer 1

查看Data.IORef和Data.STRef包，它们使您可以访问可变引用。如果您还需要执行 IO，请使用 IORefs，如果不需要，请使用 STRefs。

但是，我怀疑您可能做错了。完全可以在没有可变状态的情况下实现 Dijkstra 算法（尽管您需要小心一点，因为如果您不断地重新计算可以缓存的函数评估，您很容易导致渐近运行时间爆炸）。

Answer 2

您可能正在从矢量包中寻找Data.Vector.Mutable，您可能希望将其与ST或 IO monad 结合使用。

Answer 3

您可以使用支持调整操作的Data.FingerTree.PSQueue来更新堆。在这种情况下，您不需要指向堆中值的指针，因为您通过它们的键更新它们。