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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to