[Haskell-cafe] Composing functions with runST

Udo Stenzel u.stenzel at web.de
Wed Jan 3 08:03:20 EST 2007

Yitzchak Gale wrote:
> 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)

But why would you even want to do this?  It's ugly and cumbersome.
You'd plug a runST in there and get 

shuffle :: RandomGen g => [a] -> g -> ([a], g)

or lift it into a state monad.  Telling the world that you messed with
imperative code inside is completely pointless, since the only thing you
could possibly do with the result anyway is apply runST to it.

> Wouldn't it be nice if instead you could just write:
> shuffle :: (RandomGen g, MonadState g m) => [a] -> m [a]
> shuffle = stToState . shuffleST

It seems, what you really want is

shuffleST :: RandomGen g => [a] -> StateT g ST [a]

No need to stick the generator into a mutable variable.  Maybe you even
want a MonadST class, analogous to MonadIO.

> >Uhm... use MonadState in the first place?
> You mean use ST in the first place.

No, I don't.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070103/2050bdf2/attachment.bin

More information about the Haskell-Cafe mailing list