How to use `getBounds' with STArray?

arrays, haskell, random, shuffle

Solution

Below is one way of implementing an in-place Fisher-Yates (I think that is called a Durstenfeld or Knuth Shuffle). Notice that `runST` is never called, but `runSTArray` instead, and it is only called once.

import Data.Array
import Data.Array.ST
import Control.Monad.ST
import Control.Monad
import System.Random

fisherYates :: (RandomGen g,Ix ix, Random ix) => g -> Array ix e -> Array ix e
fisherYates gen a' = runSTArray $ do
  a <- thaw a'
  (bot,top) <- getBounds a
  foldM (\g i -> do
    ai <- readArray a i
    let (j,g') = randomR (bot,i) g
    aj <- readArray a j
    writeArray a i aj
    writeArray a j ai
    return g') gen (range (bot,top))    
  return a

Note that although the algorithm is performed in-place, the function first copies the array given in the input (a result of using the function `thaw`) before performing the algorithm on the copy. In order to avoid copying the array you have at least two options:

Use `unsafeThaw`, which is (as the name suggests) unsafe and can only be used if you are sure that the input array will never be used again. This is not trivial to guarantee because of lazy evaluation.

Let `fisherYates` have the type `(RandomGen g,Ix ix, Random ix) => g -> STArray s ix e -> ST s (STArray s ix e)` and perform the whole operation that requires an in-place fisher-yates algorithm inside the `ST` monad and only give the final answer with `runST`.

Problem

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.

Original source