[Haskell-beginners] When to use ST

[Ertugrul Soeylemez]

Alex Rozenshteyn <rpglover64 at gmail.com> wrote:

> 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/