Sto cercando di implementare l'algoritmo di Dijkstra in Haskell. Ho già implementato un heap binario utilizzando un albero. Nell'algoritmo, le chiavi del vertice corrente devono essere aggiornate nell'heap. Come posso emulare il puntatore sul valore nell'heap in Haskell? Come posso accedere rapidamente agli elementi nell'heap, mentre lo heap cambia dopo ogni operazione?Come posso emulare i puntatori in Haskell?
Controlla i pacchetti Data.IORef e Data.STRef che ti danno accesso a riferimenti mutabili. Usa IORefs se devi anche eseguire IO e STRef se non lo fai.
Tuttavia, il mio sospetto è che probabilmente stai sbagliando. È completamente possibile implementare l'algoritmo di Dijkstra senza lo stato mutabile (anche se è necessario fare un po 'di attenzione, poiché si può facilmente far esplodere il tempo di esecuzione asintotico se si stanno continuamente ricalcolando le valutazioni delle funzioni che potrebbero essere memorizzate nella cache).
Probabilmente stai cercando Data.Vector.Mutable dal pacchetto vector, che potresti voler combinare con la monade ST o IO.
È possibile utilizzare Data.FingerTree.PSQueue che supporta un'operazione adjust per aggiornare l'heap. In questo caso non hai bisogno di puntatori ai valori nell'heap perché li aggiorni tramite le loro chiavi.
FWIW, ci sono eccellenti code di priorità su hackage e gli heap di pairing sono più facili da implementare rispetto agli heap binari, ma nonostante ciò sono abbastanza potenti. Per quanto riguarda la mutazione: no. Probabilmente c'è un modo per aggirarlo, e anche se esiste una memoria mutevole, usarlo estremamente brutto per ricordarti che non dovresti farlo;) – delnan
Probabilmente otterrai risposte migliori se chiederai come fare velocemente Dijkstra in Haskell (che sembra essere il tuo vero problema) piuttosto che una possibile soluzione. – Pubby
@ElectricHedgehog, ci sono molte code di priorità asintoticamente ottimali che possono essere implementate funzionalmente, in particolare le code binomiali. Scopri pacchetti come [pqueue] (http://hackage.haskell.org/package/pqueue). –