Próbuję zaimplementować algorytm Dijkstry w Haskell. Zaimplementowałem już binarną stertę przy użyciu drzewa. W sąsiedzie algorytmu klucze bieżącego wierzchołka powinny zostać zaktualizowane w stercie. Jak mogę emulować wskaźnik do wartości w stercie w Haskell? Jak mogę uzyskać szybki dostęp do elementów w stercie, podczas gdy sterta zmienia się po każdej operacji?Jak mogę emulować wskaźniki w Haskell?
Sprawdź pakiety Data.IORef i Data.STRef, które dają dostęp do zmiennych referencji. Użyj IORefs, jeśli musisz wykonać IO, a także STRefs, jeśli tego nie zrobisz.
Podejrzewam jednak, że prawdopodobnie robisz to źle. Całkiem możliwe jest zaimplementowanie algorytmu Dijkstry bez stanu zmiennego (chociaż musisz być trochę ostrożny, ponieważ możesz łatwo spowodować wzrost asymptotycznego czasu działania, jeśli ciągle przeliczasz oceny funkcji, które mogą być buforowane).
Prawdopodobnie szukasz Data.Vector.Mutable z paczki vector, którą możesz połączyć z ST lub Monadą IO.
Możesz użyć Data.FingerTree.PSQueue, który obsługuje operację adjust, aby zaktualizować stertę. W tym przypadku nie potrzebujesz wskaźników do wartości w stercie, ponieważ aktualizujesz je za pomocą kluczy.
FWIW, istnieją doskonałe kolejki priorytetowe w hakowaniu, a stosy parowania są łatwiejsze do wdrożenia niż stosy dwupoziomowe, ale mimo to spakowują cios. Jeśli chodzi o mutację: Nie rób tego. Prawdopodobnie istnieje sposób obejścia go i nawet jeśli istnieje zmienna pamięć, używając go wyjątkowo brzydko, aby przypomnieć ci, że nie powinieneś tego robić;) – delnan
Prawdopodobnie uzyskasz lepsze odpowiedzi, jeśli zapytasz jak zrobić szybki Dijkstra w Haskell (który wydaje się być twoim faktycznym problemem) zamiast jednego możliwego rozwiązania. – Pubby
@ElectricHedgehog, jest mnóstwo asymptotycznie optymalnych kolejek priorytetowych, które można zaimplementować funkcjonalnie, w szczególności dwumianowe kolejki. Sprawdź pakiety, takie jak [pqueue] (http://hackage.haskell.org/package/pqueue). –