[Haskell-cafe] Being impure within a 'pure' function
daniel.is.fischer at web.de
Thu Apr 23 09:02:34 EDT 2009
Am Donnerstag 23 April 2009 14:15:16 schrieb Max Rabkin:
> On Wed, Apr 22, 2009 at 10:38 AM, Daniel K. <anmeldemails at gmail.com> 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
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).
More information about the Haskell-Cafe