[Haskell-cafe] Re: Composing functions with runST

[apfelmus at quantentunnel.de]

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