How to use `getBounds' with STArray?

Question

I'm trying to write a Fisher-Yates shuffle algorithm using STArray. Unlike all the other examples I've found on the net, I am trying to avoid using native lists. I just want to shuffle an array, in-place.

This is what I have:

randShuffleST arr gen = runST $ do
    _ <- getBounds arr
    return (arr, gen)

arr is the STArray and gen will be a generator state of type (RandomGen g).

I was hoping I could rely on the (MArray (STArray s) e (ST s)) instance declaration defined in MArray for being able to use MArray's getBounds but GHCi cannot infer the type of randShuffleST. It fails with:

Could not deduce (MArray a e (ST s))
  arising from a use of `getBounds'
from the context (Ix i)
  bound by the inferred type of
           randShuffleST :: Ix i => a i e -> t -> (a i e, t)
  at CGS/Random.hs:(64,1)-(66,25)
Possible fix:
  add (MArray a e (ST s)) to the context of
    a type expected by the context: ST s (a i e, t)
    or the inferred type of
       randShuffleST :: Ix i => a i e -> t -> (a i e, t)
  or add an instance declaration for (MArray a e (ST s))
In a stmt of a 'do' block: _ <- getBounds arr
In the second argument of `($)', namely
  `do { _ <- getBounds arr;
        return (arr, gen) }'
In the expression:
  runST
  $ do { _ <- getBounds arr;
         return (arr, gen) }

Interestingly, if I remove the call to `runST' like so:

randShuffleST arr gen = do
    _ <- getBounds arr
    return (arr, gen)

it compiles fine, with the type signature

randShuffleST :: (Ix i, MArray a e m) => a i e -> t -> m (a i e, t)

. I'm using GHC 7.4.2 on Arch Linux.

Please give explicit type signatures in your responses to help me understand your code, thank you.

EDIT: I really like Antal S-Z's answer, but I cannot select it because frankly I do not fully understand it. Maybe once I understand my own problem better I'll answer my own question in the future... thanks.

Answer 1

You probably shouldn't use runST in your function. runST should be used once, on the outside of some computation that uses mutation internally but has a pure interface. You probably want your shuffle function, which shuffles the array in-place, to have a type like STArray s i e -> ST s () (or possibly a more general type), and then have a different function that uses runST to present a pure interface, if you want that (that function would probably need to copy values, though). In general the goal of ST is that STRefs and STArrays can never escape from one runST invocation and be used in another.

The type inferred for your function without runST is fine, just more polymorphic (it'll work for IO arrays, ST arrays, STM arrays, unboxed arrays, etc.). You'll have an easier time with inference errors if you specify explicit type signatures, though.