Yitzchak Gale wrote:
Well, it turns out that using Data.Sequence or Data.IntMap to shuffle a list becomes prohibitive if you might have more than about 10^5 elements in your list. So in that case you will need to use a mutable array, and you now need ST. [..]
Wouldn't it be nice if instead you could just write:
shuffle :: (RandomGen g, MonadState g m) => [a] -> m [a] shuffle = stToState . shuffleST
and then just use that directly inside a calculation that is otherwise purely non-ST?
It seems, what you really want is shuffleST :: RandomGen g => [a] -> StateT g ST [a]
Actually, I tried that. It didn't help - it was just one more layer I had to peel away to get at the ST inside.
There seems to be no way to avoid the fact that you think about state in two very different ways in these two monads. Every program is written in either one style or the other. Occasionally, you require an isolated use of the opposite style, and I am looking for ways of simplifying the resulting mess. "StateT st ST" and "MonadST" look like ways of combining the two, but in practice I find that they just seem to get in the way.
I don't get what exactly you want. If you want to carry your state named "MyState" (f.i. type MyState = [Cards,Players]) around in a monad, you use "Control.Monad.State MyState". If (and only if) you have an algorithm (like depth-first search) that carries an array as state around (nodes already visited) and you know that this array is used in a single threaded fashion, it might be worth to update the array in place. For that, you use Control.Monad.ST and Data.Array.ST and you can be confident that the state carrying has been strictness analyzed and fine tuned to match the machine. In short, you get updates in place without selling your soul to IO, runST is your protection from evil and will keep you pure. ST does not really have more uses than this one (besides being the foundation for IO). For more info on ST, see http://research.microsoft.com/Users/simonpj/Papers/state-lasc.ps.gz Note that the you can now achieve the array thing as well with Data.Array.Diff. This is a purely functional interface to an array type that uses destructible updates internally and keeps a history to become persistent. However, I doubt that an array makes a difference over Data.IntMap for all but the most special cases.
I am starting to be convinced that the only way to write the function I want is by using unsafeRunST. Or type it as
stToState :: MonadState st m => (st -> ST s (a, st)) -> m a
and then write in the documentation that the user is require to write
do r <- newSTRef x ... y <- readSTRef r return (z, y)
by hand every time. Yuck.
If the programmer needs to adhere to a policy, the type system may well enforce it for him. No unsafeRunST. It's far better to struggle with the safety device than to discover the hard way that running without it will directly lead into the debugging hell. Regards, apfelmus