[Haskell] Re: ST/STRef vs. IO/IORef

[Wolfgang Jeltsch]

Am Donnerstag, 4. August 2005 10:21 schrieb Axel Simon:
> [...]

> Nowadays, you can use one of the MonadState monad

State transformer monads like State and StateT can be implemented without 
using special language features.  So there was always the opportunity to 
implement something like State or StateT.  So, in a way, we always could use 
the MonadState monads.  If ST could be replaced by MonadState monads, ST had 
never been included in the libraries, I suppose.

> if you want lazy computation (on top of which you can implement state read
> and write accesses similar to IORefs) or IO-enabled computation (if you use
> MonadState.StateT and embed an IO monad at the core).

The point is that the MonadState monads don't give you update-in-place.  
Update-in-place is exactly the reason why ST is there.

> Is this view correct? If not, could there be a comment as to what ST is
> useful (rather than a reference to a full blown paper that pre-dates the
> MonadState,... libraries).

ST is useful if you have to update small parts of an array since you don't 
have to construct a whole new array with ST.  With ST you are able to update 
a single array element in O(1) time.  In comparison, updating a single key's 
value in a finite map via State or StateT takes O(log n) time.

> Axel.

Best regards,
Wolfgang