CODEWITHSUNDEEP
haskellheapdijkstra
ElectricHedgehog
ElectricHedgehog

Reputation: 173

How can I emulate pointers in Haskell?

I am trying to implement Dijkstra's algorithm in Haskell. I have already implemented a binary heap using a tree. In the algorithm neighbours keys of the current vertex should be updated in the heap. How can I emulate pointer to value in the heap in Haskell? How can I have fast access to elements in the heap, while the heap is changing after each operation?

Upvotes: 9

Views: 607

Answers (3)

Daniel
Daniel

Reputation: 27559

You can use Data.FingerTree.PSQueue which supports an adjust operation to update the heap. In this case you don't need pointers to the values in the heap because you update them through their keys.

Upvotes: 0

comonad
comonad

Reputation: 5241

You are probably looking for Data.Vector.Mutable from the vector package, which you might want to combine with the ST or IO monad.

Upvotes: 0

Chris Taylor
Chris Taylor

Reputation: 47392

Check out the packages Data.IORef and Data.STRef which give you access to mutable references. Use IORefs if you also need to perform IO, and STRefs if you don't.

However, my suspicion is that you're probably doing it wrong. It is entirely possible to implement Dijkstra's algorithm without mutable state (although you need to be a little careful, as you can easily cause the asymptotic running time to blow up if you are continually recomputing function evaluations that could be cached).

Upvotes: 12

Related Questions