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