将Haskell列表随机化

Question

我想写一个Haskell程序，它将"ramdomize"列表中的元素：

import System.Random (getStdGen, randomRIO)
import Data.List (permutations)
rndElem :: [a] -> IO a
rndElem xs = do
  index <- randomRIO (0, length xs - 2)
  return $ xs !! index
rndPermutation :: [a] -> IO [a]
rndPermutation xs = rndElem . permutations $ xs

然而，运行此操作似乎并没有完全随机化列表。由于某些原因，它只对其他元素进行随机化，例如[1,2,3,4,5,6]->[5,2,1,4,3,6]。该算法的每次运行都将奇数索引（2，4，6）元素保持在同一位置。。上述算法的索引是否存在逻辑错误？

Answer 1

尝试运行以下代码：

import System.Random (getStdGen, randomRIO)
import Data.List (permutations)
rndElem :: [a] -> IO Int
rndElem xs = do
  index <- randomRIO (0, length xs - 7)
  return index

然后将7改为6改为5，依此类推

希望这能解释我关于"2"的问题，也许这会帮助你弄清楚代码在做什么。

Answer 2

随机化有限列表的一个非常好的算法是Fisher Yates shuffle，也就是Knuth shuffle。这是来自罗塞塔代码的Haskell版本：

import System.Random
import Data.List
import Control.Monad
mkRands = mapM (randomRIO.(,)0 ). enumFromTo 1. pred
replaceAt :: Int -> a -> [a] -> [a]
replaceAt i c l = let (a,b) = splitAt i l in a++c:(drop 1 b)
swapElems :: (Int, Int) -> [a] -> [a]
swapElems (i,j) xs | i==j = xs
                   | otherwise = replaceAt j (xs!!i) $ replaceAt i (xs!!j) xs
knuthShuffle :: [a] -> IO [a]
knuthShuffle xs =
  liftM (foldr swapElems xs. zip [1..]) (mkRands (length xs))