module System.Random.Shuffle.FisherYates (
shuffle
, shuffle'
) where
import Control.Applicative (pure)
import Control.Monad
import Control.Monad.ST
import Data.STRef
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import System.Random.TF
import System.Random.TF.Instances
import System.Random.Rando.Internal (inIO)
shuffle :: [x] -> IO [x]
shuffle l = inIO $ shuffle' l
shuffle' :: [x] -> TFGen -> ([x], TFGen)
shuffle' list gen0 =
runST $ do
genVar <- newSTRef gen0
v <- V.thaw $ V.fromList list
let vLen = VM.length v
forM_ [vLen - 1, vLen - 2 .. 1] $ \n -> do
indexToSwap <- randSTFromZero genVar n
VM.unsafeSwap v indexToSwap n
final <- V.unsafeFreeze v
finalGen <- readSTRef genVar
pure (V.toList final, finalGen)
randSTFromZero :: STRef s TFGen -> Int -> ST s Int
randSTFromZero genVar maxVal = do
g0 <- readSTRef genVar
let (x, g1) = randomR (0, maxVal) g0
writeSTRef genVar g1
pure x