Yes. Use the ST ("State Thread") monad. Data.Array.ST, STRef etc. 2009/4/22 Daniel K. :

Hello,

imagine the following situation: You want to implement e.g. Dijkstra's algorithm to find a shortest path between nodes u and v in a graph. This algorithm relies heavily on mutating arrays, so the type signature would look something like

getDistance :: Graph -> Node -> Node -> IO Int

Not mutating the underlying arrays would probably result in poor performance. BUT: For a constant graph, the distance between two nodes stays the same all the time, so in fact getDistance should be a pure function! So here is my question: Is there a way to write functions in Haskell that do some IO internally, but that are guaranteed to be side-effect free? Of course one would have to make sure that the array that is mutated inside getDistance must not be accessible from outside the function.

Is that possible? If not, wouldn't that be desirable? If not, why not?

Thanks

  Daniel

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

On Wed, Apr 22, 2009 at 10:38 AM, Daniel K. wrote:

Dijkstra's algorithm ... relies heavily on mutating arrays

Well, the imperative implementation does.

Not mutating the underlying arrays would probably result in poor performance.

Indeed. Non-mutable arrays are not very performant for mutations. Tree-like data structures Are Your Friend. I've never compared the performance of an ST-based implementation with a set/map based algorithm, but I've often found the latter usably performant. --Max