配列のシャッフル

Haskell 30分プログラム

30分プログラム、その629。http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_014やnanigac.comにインスパイアされて配列のシャッフルにチャレンジしてみた。

配列のシャッフルはリストの要素のシャッフル - みずぴー日記でもやったけど、上記のサイトでは別の方法でシャッフルを実現してる。

それぞれに1から10までの数値が書かれた10枚のカード。
これをシャッフルするにはどうしたらいいでしょうか。
(中略)
簡単な方法はそれぞれに乱数をくっつけてその乱数でソートすることです。

乱数の振って、それでソートするのはおもしろいね。やってみよう。

使い方

*Main> shuffle [1..10]
[4,3,10,5,9,7,8,2,6,1]
*Main> shuffle [1..10]
[5,9,8,10,3,4,2,7,6,1]

ソースコード

import System.Random
import Control.Monad.State
import Data.List

--shuffle :: [a] -> IO [a]
assignRandom :: RandomGen g => a -> State g (Int,a)
assignRandoms :: RandomGen g => [a] -> State g [(Int,a)]
shuffleS :: RandomGen g => [a] -> State g [a]

assignRandom x = do g <- get
                    (i,g') <- return $ random g
                    put g'
                    return (i,x)
assignRandoms xs = mapM assignRandom xs

shuffleS xs = do ys <- assignRandoms xs
                 let zs = sortBy (\(a,_) (b,_) -> a `compare` b) ys
                 return $ map snd zs

shuffle xs = do g <- newStdGen
                return $ fst $ runState (shuffleS xs) g

参考