Haskellでリストをシャッフル

何を書いたか

HaskellのRandomモジュールでリストのシャッフル関数が無かったので少しQiitaで調べてみた。するとArray版やVector版は見つかったがどちらもIO[a]といった結果が返ってきていた。なので[a]が返ってくるようなshuffle関数を作りたくなった。そしてできたので投稿することにした。コード全体(というよりData/Random/Shuffle.hsさえあれば十分)はこちら。実行速度は気にしない。

コード

Data/Random/Shuffle.hs

module Data.Random.Shuffle(
  shuffle
, autoShuffle
)where

import System.Random
import Data.List (nub, sortOn)
import Control.Applicative ((<$>), (<*>))

getNubRandomRs :: RandomGen g => g -> (Int, Int) -> [Int]
getNubRandomRs g (l, h) = take (abs (h - l) + 1) $ nub $ randomRs (l, h) g

shuffle :: RandomGen g => g -> [a] -> [a]
shuffle _ [] = []
shuffle g xs = map fst $ sortOn snd $ zip xs rs
    where
        rs = getNubRandomRs g (1, length xs)

autoShuffle ::[a] -> IO [a]
autoShuffle [] = pure []
autoShuffle xs = shuffle <$> newStdGen <*> (pure xs)

何をしているか

まずgetNubRandomRs関数について説明します。この関数はrandomパッケージ内にあるrandomRs関数によって得た結果を重複をなくして出力する関数。つまりlからhまでをランダムに並び替える関数です。これでも目的を達成しそうですがこの関数ですと連続した範囲内でしかシャッフルできない。なので目的は達成できない。
次にshuffle関数について説明します。この関数は先ほど紹介したgetNubRandomRs関数によって得たシャッフルしたいリストと同じ長さのシャッフルされたインデックスのリストを基にシャッフルする関数です。つまりそのインデックスリストをソート関数のソート条件に与えてやることで、基のリストがシャッフルされる実装になっている。そしていちいち乱数のタネgを与えるのは面倒なのでnewStdGenを使うことで使うたびにタネを与えずにshuffleを使えるようにした関数がautoShuffle関数です。newStdGenを使う弊害として結果がIOで包まれています。

使用例

*Data.Random.Shuffle> shuffle (mkStdGen 12) [1 .. 10]
[3,7,6,10,4,9,8,5,2,1]
*Data.Random.Shuffle> shuffle (mkStdGen 12) [1 .. 10]
[3,7,6,10,4,9,8,5,2,1]
*Data.Random.Shuffle> shuffle (mkStdGen 12) [1 .. 10]
[3,7,6,10,4,9,8,5,2,1]
*Data.Random.Shuffle> autoShuffle [1 .. 10]
[7,10,9,6,8,3,4,2,5,1]
*Data.Random.Shuffle> autoShuffle [1 .. 10]
[10,8,6,7,2,9,1,5,3,4]
*Data.Random.Shuffle> autoShuffle [1 .. 10]
[2,1,4,10,8,9,7,6,5,3]
*Data.Random.Shuffle> autoShuffle [1 .. 10]
[7,9,3,8,2,4,1,10,6,5]
*Data.Random.Shuffle> data TTT = A | B | C | Dderiving Show
*Data.Random.Shuffle> shuffle (mkStdGen 12) [A, B, C, D]
[D,A,B,C]

まとめ

Haskellでトランプゲーム等のシャッフル関数作成の一助になればいいなと思います。