Я пытаюсь реализовать алгоритм Дейкстры в Haskell. Я уже реализовал двоичную кучу, используя дерево. В алгоритме соседние ключи текущей вершины должны быть обновлены в куче. Как я могу эмулировать указатель на значение в куче в Haskell? Как я могу получить быстрый доступ к элементам в куче, а куча меняется после каждой операции?Как я могу эмулировать указатели в Haskell?
Ознакомьтесь с пакетами Data.IORef и Data.STRef, которые предоставят вам доступ к изменяемым ссылкам. Используйте IORefs, если вам также нужно выполнить IO и STRef, если вы этого не сделаете.
Однако мое подозрение заключается в том, что вы, вероятно, ошибаетесь. Вполне возможно реализовать алгоритм Дейкстры без изменчивого состояния (хотя вам нужно быть немного осторожным, так как вы можете легко привести к тому, что асимптотическое время работы взорвется, если вы постоянно перекомпонуете оценки функций, которые можно кэшировать).
Возможно, вы ищете Data.Vector.Mutable из пакета vector, который вы можете комбинировать с ST или IO monad.
Вы можете использовать Data.FingerTree.PSQueue, который поддерживает операцию adjust для обновления кучи. В этом случае вам не нужны указатели на значения в куче, потому что вы обновляете их через свои ключи.
FWIW, есть отличные очереди приоритетов при взломе, а спаривание куч легче реализовать, чем двоичные кучи, но, тем не менее, пакет довольно ударил. Что касается мутации: не надо. Вероятно, есть способ обойти его, и хотя существует изменчивая память, использующая его крайне уродливо, чтобы напомнить вам, что вы не должны этого делать;) – delnan
Вероятно, вы получите более качественные ответы, если спросите, как быстро выполнить Dijkstra в Haskell (который кажется вашей реальной проблемой), а не одно из возможных решений. – Pubby
@ ElectricHedgehog существует множество асимптотически оптимальных очередей приоритетов, которые могут быть реализованы функционально, в первую очередь биномиальные очереди. Проверьте пакеты, например [pqueue] (http://hackage.haskell.org/package/pqueue). –