Estoy tratando de implementar el algoritmo de Dijkstra en Haskell. Ya he implementado un montón binario usando un árbol. En el algoritmo, las claves vecinas del vértice actual deberían actualizarse en el montón. ¿Cómo puedo emular el puntero al valor en el montón en Haskell? ¿Cómo puedo tener acceso rápido a los elementos en el montón, mientras que el montón está cambiando después de cada operación?¿Cómo puedo emular punteros en Haskell?
Consulte los paquetes Data.IORef y Data.STRef que le dan acceso a referencias mutables. Use IORefs si también necesita realizar IO, y STRefs si no lo hace.
Sin embargo, mi sospecha es que probablemente lo estés haciendo mal. Es totalmente posible implementar el algoritmo de Dijkstra sin estado mutable (aunque es necesario tener un poco de cuidado, ya que puede hacer que el tiempo de funcionamiento asintótico explote fácilmente si continuamente está recalculando las evaluaciones de funciones que podrían almacenarse en caché).
Probablemente esté buscando Data.Vector.Mutable del paquete vector, que es posible que desee combinar con ST o IO mónada.
Puede usar Data.FingerTree.PSQueue que admite una operación adjust para actualizar el montón. En este caso, no necesita punteros a los valores en el montón porque los actualiza a través de sus claves.
FWIW, existen excelentes colas de prioridad en hackage, y los montones de emparejamiento son más fáciles de implementar que los montones binarios, pero sin embargo son un buen golpe. En cuanto a la mutación: No. Probablemente haya una forma de evitarlo, y aunque exista una memoria mutable, usarla extremadamente feo para recordarle que no debe hacerlo;) – delnan
Probablemente obtendrá mejores respuestas si pregunta cómo hacer Dijkstra rápidamente en Haskell (que parece ser su problema real) en lugar de una posible solución. – Pubby
@ElectricHedgehog, hay muchas colas de prioridad asintóticamente óptimas que pueden implementarse funcionalmente, en particular las colas binomiales. Consulte paquetes como [pqueue] (http://hackage.haskell.org/package/pqueue). –