Alex Rozenshteyn
Does anyone have any guidelines on when to use ST in an algorithm vs looking for a non-monadic, pure solution?
First of all, monadic doesn't mean impure. Impure means IO or ST, and only to a certain degree (you use destructive update, but regarding the type system you don't break referential transparency, as long as you don't unsafePerformIO). Now to answer your question: In general, never use ST. Always implement your algorithm purely using appropriate data structures (vectors, maps, etc.). With the right data structures your algorithms should perform very well. In some cases you really need to pull the last bit per second out of your code. In these cases find the bottleneck in your code and only write that part in ST. For example when working with vectors, use the immutable ones, but in certain spots you can use 'create' or 'modify' and sidestep into ST only for particular operations. In less fixed data structures you generally don't need destructive update at all, because e.g. maps only consume extra memory for the changed paths. Done properly the old paths get garbage-collected immediately, thus immutable maps are very fast in Haskell.
The reason I ask is that I have just implemented an Earley parser for class (in Python) and would like to re-implement it in Haskell. The algorithm makes heavy use of mutable state, some of which can clearly be refactored out, but some of which can't be done so clearly.
If it's just a parser, I suggest, well, writing a parser. Use your favorite parser monad. If you need high efficiency in terms of throughput, try attoparsec, which is a very fast ByteString parser. Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/