Re: [Haskell-cafe] Being impure within a 'pure' function

Am Donnerstag 23 April 2009 14:15:16 schrieb Max Rabkin:

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.

I have occasionally, and I can confirm that often set/map based algorithms give quite usable performance. But usually ST-based implementations are significantly faster. If the algorithm demands a lot of updates and performance is important, I recommend sacrificing the ease and elegance of coding with sets/maps for ST's uglier but faster code (but verify that set/map performance is unsatisfactory first).

--Max