Shuffle vector

gistfile1.hs

module Shuffle where

import Control.Monad
import Control.Monad.ST
import System.Random
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV


-- | Shuffles a vector in linear time using inside out Fisher-Yates.
--
-- Returns a new vector.
shuffle :: RandomGen g => g -> V.Vector a -> V.Vector a
shuffle gen src = runST $ do
  a <- MV.new n
  foldM_ 
    (\g i -> do
      let (j, g') = randomR (0, i) g
      unless (i == j) 
        (MV.read a j >>= MV.write a i)
      MV.write a j (src V.! i)
      return g'
    ) gen [0 .. n - 1]
  V.unsafeFreeze a -- safe since we never use a again
 where
   n = V.length src