Haskell

【Haskell】リストをシャッフルする関数

More than 1 year has passed since last update.

module Main where

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

main :: IO ()
main = do
print =<< shuffle [1..10] -- [7,8,5,1,6,2,4,9,10,3]
print =<< shuffle [1..10] -- [8,4,10,3,1,5,9,7,2,6]
print =<< shuffle [1..10] -- [7,8,6,3,5,2,9,1,4,10]
print =<< shuffle [1..10] -- [1,4,2,3,9,10,6,7,8,5]
print =<< shuffle [1..10] -- [5,8,3,6,2,10,9,7,1,4]

shuffle :: [Int] -> IO [Int]
shuffle list = do
let l = length list
arr <- newListArray (1, l) list
forM_ [l,(l-1)..1] $ \i ->
swap arr i =<< getStdRandom (randomR (1, i))
getElems arr

swap :: IOUArray Int Int -> Int -> Int -> IO ()
swap arr i j = do
t <- readArray arr i
writeArray arr i =<< readArray arr j
writeArray arr j t

shuffle関数にリストを渡すと、シャッフルされたリストがIOモナドに包まれて返ってくる。シャッフルの時間を測ったところ、家のパソコンでは要素数100万のリストのシャッフルに4~5秒かかり、1000万だと40~50秒かかった。もっと縮めたいところ。