[Haskell-cafe] Refactoring from State monad to ST monad, for STUArray

[Derek Elkins]

On Sat, 2008-02-02 at 12:33 -0500, Denis Bueno wrote:
> Is it possible to use the ST monad as a (drop-in) replacement for the
> State monad in the following situation?  If not, is there a "best
> practice" for refactoring?
> 
> I have a bunch of functions that return state actions:
> 
>     type MyState = ...
> 
>     foo1 :: T1 -> State MyState a
>     foo2 :: T2 -> State MyState a
>     ...
>     foon :: Tn -> State MyState a
> 
> And I'd like to refactor this to use the ST monad, mechanically, if
> possible.  All uses of the MyState inside State are single-threaded.
> 
> In my application, MyState is a record with 5 or so fields.  One of
> those fields uses a list to keep track of some information, and I'd
> like to change that to STUArray, because it changes my bottleneck
> operations from O(n) to O(1).  This, of course, requires having the ST
> monad around, in order to achieve the proper time complexity.
> 
> Is there an easy way to do this?  In the future, should I *start out*
> with the ST monad if I suspect I'll need to use an imperative data
> structure for efficiency reasons?  I started out with State because
> I'm modeling a transition system, so it seemed natural.
> 
> Any advice is appreciated.

%s/State MyState/MyMonad s/g

type MyState s = ... s ...

type MyMonad s = StateT (MyState s) (ST s)