Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 877
ElectricHedgehog Avatar asked Jun 27 '12 09:06

ElectricHedgehog


1 Answers

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).

like image 53
Chris Taylor Avatar answered Oct 25 '22 06:10

Chris Taylor