[Haskell-cafe] using mutable data structures in pure functions

[wren ng thornton]

On 3/11/12 11:52 PM, Ben Gamari wrote:
> That being said, there are some cases where you really do want to be
> able to utilize a mutable data structure inside of an otherwise pure
> algorithm. This is precisely the use of the ST monad. ST serves to allow
> the use of mutable state inside of a function while hiding the fact from
> the outside world.

Do note, however, that in certain cases the ST approach can be much 
slower than the obvious immutable approach (i.e., the State monad--- 
especially when implemented directly via argument passing, rather than 
using the monadic interface). I have some closed-source code where that 
assumption bit me; the ST code was over 4x slower.

One reason this can happen is that, since Haskell is predominantly pure, 
a whole lot of work has gone into optimizing the pure case. Another 
reason is that, if the compiler can see that it's pure, then it knows a 
bunch of safe optimizations the programmer may not have thought about. A 
final major reason is that often the rearrangements necessary to get 
things into state-passing form turn out to optimize the algorithm 
anyways (e.g., by ensuring linear access to inputs, etc)

So don't just assume that ST/mutability == fast.

-- 
Live well,
~wren