我该如何在Haskell中模拟指针？

Question

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

- ElectricHedgehog

---

顺便提一句，Hackage 上有很棒的优先队列实现，其中 pairing heaps 比 binary heaps 更易于实现，但是同样非常高效。至于变异：不要这么做。可能会有绕过它的方法，尽管可变内存存在，但使用它极其丑陋，并提醒你不应该这样做 ;) - user395760

如果你询问如何在 Haskell 中实现快速 Dijkstra 算法（这似乎是你真正的问题），那么你可能会得到更好的答案，而不是一个可能的解决方案。 - Pubby

@ElectricHedgehog，有很多渐进最优的函数式优先队列可以实现，其中最著名的是二项队列。可以查看像pqueue这样的软件包。 - Louis Wasserman

@delnan，我能找到的最好的没有指针的解决方案是存储映射{顶点：堆中的位置}，并在每次使用堆后更新它。但这会将渐近乘以O(log(n))。 - ElectricHedgehog

在使用指针和破坏性更新之前，请先创建一个纯版本并检查其速度是否足够快。 - augustss

Answer 1

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

然而，我怀疑您可能做错了。完全有可能在不使用可变状态的情况下实现 Dijkstra 算法（尽管您需要小心一点，因为如果您不断重新计算可以缓存的函数评估，可能会导致渐近运行时间增加）。

- Chris Taylor

Answer 2

你可能正在寻找Data.Vector.Mutable，它来自于vector包，你可能想将其与ST或IO单子结合使用。

- comonad

Answer 3

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

- Daniel