[Haskell-cafe] using mutable data structures in pure functions
wren ng thornton
wren at freegeek.org
Thu Mar 15 01:50:52 CET 2012
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.
More information about the Haskell-Cafe