如何随机打乱列表

Question

我有随机数生成器

rand :: Int -> Int -> IO Int
rand low high = getStdRandom (randomR (low,high))

以及从列表中删除元素的辅助函数

removeItem _ []                 = []
removeItem x (y:ys) | x == y    = removeItem x ys
                    | otherwise = y : removeItem x ys

我想通过从列表中随机选择一个项目，将其删除并将其添加到列表的前面来打乱给定的列表。我试过了

shuffleList :: [a] -> IO [a]
shuffleList [] = []
shuffleList l = do 
                     y <- rand 0 (length l)
                     return( y:(shuffleList (removeItem  y l) ) )

但无法正常工作。我得到

hw05.hs:25:33: error:
    * Couldn't match expected type `[Int]' with actual type `IO [Int]'
    * In the second argument of `(:)', namely
     ....

有什么想法吗？

谢谢！

Answer 1

自 shuffleList :: [a] -> IO [a] 以来，我们有 shuffleList (xs :: [a]) :: IO [a].

显然，我们不能将 (:) :: a -> [a] -> [a] 一个 a 元素添加到一个 IO [a] 值中，而是我们想将它添加到列表 [a] 中， IO [a] 值描述的计算：

   do
         y <- rand 0 (length l)
         -- return ( y : (shuffleList (removeItem  y l) ) )
         shuffled  <-     shuffleList (removeItem  y l)
         return      y : shuffled

在do表示法中，<-右边的值有M a、M b等类型，对于一些单子M（这里, IO), <- 左边的值有对应的类型 a, b, 等等.

x <- mx 中的 x :: a 绑定到由 M 类型计算生成/计算的类型 a 的纯值，其中值 mx :: M a表示，当计算实际执行时，作为整个do块表示的组合计算的一部分，当那个组合计算作为一个整体进行。

如果例如do 块中的下一行是 y <- foo x，这意味着将纯函数 foo :: a -> M b 应用于 x 并计算结果，该结果是 [= 类型的值21=]，表示 M 类型的计算，然后运行s 并生成/计算类型 b 的纯值，然后名称 y 绑定到该值。

Monad 的本质因此是纯内部/之间 （潜在）不纯 的切片，就是这两条时间线继续进行纯计算和可能不纯的计算，纯世界与现实世界的杂质安全地分离和隔离。或者从另一面看，纯代码是运行由真正的不纯代码与现实世界交互（如果 M 是 IO）。毕竟，这是计算机程序必须做的事情。

你的removeItem是错误的。您应该按位置选择和删除项目，即按索引，而不是按值；并且在任何情况下都不要在从列表中选择一个项目后删除超过一个项目。

y <- rand 0 (length l)中的y确实是一个索引。就这样对待它。重命名为i，作为一个简单的助记符。

Answer 2

一般来说，使用 Haskell 可以更好地最大化 功能性 代码的数量，而牺牲非功能性（IO 或随机性相关）代码。

在您的情况下，您的“最大”功能组件不是 removeItem，而是 shuffleList 的一个版本，它采用输入列表和（如 Will Ness 所述）确定性整数位置。列表函数 splitAt :: Int -> [a] -> ([a], [a]) 在这里可以派上用场。像这样：

funcShuffleList :: Int -> [a] -> [a]
funcShuffleList _ [] = []
funcShuffleList pos ls =
    if (pos <=0) || (length(take (pos+1) ls) < (pos+1))
      then ls -- pos is zero or out of bounds, so leave list unchanged
      else let (left,right) = splitAt pos ls
           in  (head right) : (left ++ (tail right))

测试：

 λ> 
 λ> funcShuffleList  4  [0,1,2,3,4,5,6,7,8,9]
 [4,0,1,2,3,5,6,7,8,9]
 λ> 
 λ> funcShuffleList 5 "@ABCDEFGH"
 "E@ABCDFGH"
 λ>

一旦你掌握了这个，你就可以以更简单的方式引入随机性问题。而且你不需要明确地涉及 IO，因为任何随机友好的 monad 都会这样做：

shuffleList :: MonadRandom mr => [a] -> mr [a]
shuffleList [] = return []
shuffleList ls =
    do
       let maxPos = (length ls) - 1
       pos <- getRandomR (0, maxPos)
       return (funcShuffleList pos ls)

... IO 只是 MonadRandom.

的一个实例

您可以运行使用默认的 IO 托管随机数生成器的代码：

main = do
    let inpList = [0,1,2,3,4,5,6,7,8]::[Integer]

    putStrLn $ "inpList  = " ++ (show inpList)

    -- mr automatically instantiated to IO:
    outList1 <- shuffleList inpList
    putStrLn $ "outList1 = " ++ (show outList1)
    outList2 <- shuffleList outList1
    putStrLn $ "outList2 = " ++ (show outList2)

程序输出：

$ pickShuffle
inpList  = [0,1,2,3,4,5,6,7,8]
outList1 = [6,0,1,2,3,4,5,7,8]
outList2 = [8,6,0,1,2,3,4,5,7]
$ 
$ pickShuffle
inpList  = [0,1,2,3,4,5,6,7,8]
outList1 = [4,0,1,2,3,5,6,7,8]
outList2 = [2,4,0,1,3,5,6,7,8]
$

这里的输出不可重现，因为默认生成器是根据其启动时间（以纳秒为单位）播种的。

如果你需要的是全随机排列，你可以看看here and there - Knuth a.k.a. Fisher-Yates algorithm。

如何随机打乱列表

How to randomly shuffle a list

haskell

do-notation

程序输出：