[Haskell-cafe] Composing functions with runST

[Yitzchak Gale]

I wrote:
>> It seems to me that a natural notion of a state transformer
>> in the ST monad is the type:
>> STRef s st -> ST s a

Udo Stenzel wrote:
> Are there any useful functions of this type?

Sure. Anything that can be written as a pure state
transformer can be written this way, of course.
In addition, you can use mutable arrays for speed.

Here is a concrete example:

Let's say you want to shuffle a large list randomly,
within a larger application that lives inside some
MTL monad stack. Among other things, your monad
m satisfies (RandomGen g, MonadState g m), perhaps
after a lift.

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.

Combining ST and MTL can be messy, even in this simple
case. You will probably write something with a type like

RandomGen g => [a] -> g -> ST s ([a], g)

apply runST (tiptoeing carefully around the paradoxes
mentioned in this thread), and then build an MTL state
thing out of it.

Wouldn't it be nice if instead you could just write:

shuffle :: (RandomGen g, MonadState g m) => [a] -> m [a]
shuffle = stToState . shuffleST

> I guess, your intention is that this "transformer" makes
> no other use of the ST monad than reading
> or writing a single variable.

Well, it can do whatever it wants inside, but it needs to expose
any state that is shared externally. If that state is complex,
you can use the same techniques that you would use for
a State monad - either build the complexity into the state
type using, say, records, or compose several transformers.
In this case composition would be:

STRef s st1 -> STRef s st2 -> ST s a

> It seems, every such function better have
> a purely functional interface anyway,

Yes, that is the intended use.

> even if it makes use of runST internally.

You would not need to, stToState would take care
of runST.

>> stToState :: MonadState st m => (STRef s st -> ST s a) -> m a
>> The type signatures above do ensure (as far as I can see)
>> that the opacity of the ST state thread is not violated.

> I doubt that.  The "transformer" you pass in could have captured
> references from a different state thread, which is exactly the problem
> the rank-2 type should prevent.

Hmm, you're right.

> I guess, the type signature you want is
> stToState :: MonadState st m => (forall s . STRef s st -> ST s a) -> m a

Or use some opaque type or monad and do something unsafe inside.

> > Any ideas? A better approach?

> Uhm... use MonadState in the first place?

You mean use ST in the first place. Yes, but I
want to avoid that.

> The converse is comparatively
> easily accomplished...

Yes.

Regards,
Yitz