如何使用随机选择在Haskell中随机播放列表

Question

我正在尝试使用随机数对任何a的列表进行洗牌。我在这里问这个问题的原因是因为我已经创建了一个函数，但无法弄清楚为什么它确实不起作用。

pick :: [a] -> IO a
pick xs = do
    n <- randomRIO (0, length xs - 1)
    return $ xs !! n

shuffle :: [a] -> [IO a]
shuffle ls = do
    x <- pick ls
    let y = remove x ls
    (return x) : shuffle y

-- Remove an element from a list (Only first appearance)
remove :: (Eq a) => a -> [a] -> [a]
remove _ []     = []
remove r (x:xs) = if x == r then xs else x : remove r xs

我得到的错误：

num.hs:31:10: error:
    * Couldn't match type `IO' with `[]'
      Expected type: [a]
        Actual type: IO a
    * In a stmt of a 'do' block: x <- pick ls
      In the expression:
        do x <- pick ls
           let y = remove x ls
           (return x) : shuffle y
      In an equation for `shuffle':
          shuffle ls
            = do x <- pick ls
                 let y = ...
                 (return x) : shuffle y
   |
31 |     x <- pick ls
   |          ^^^^^^^

对我来说没有意义的是，它说接收到的是类型[a]而不是IO a，但是ls定义为[a]？

如果存在我根本不了解的根本错误，是否有另一种简单的方法可以在Haskell中随机排列列表？最好不要进口。

Answer 1

发生的情况是的类型签名shuffle暗示其do-block具有type [IO a]。这意味着此do-block的monad不是IO您想要的，而是list的monad实例[]，因为这是这里的“最外”类型构造函数。pick ls因此，do-block要求表达式具有[t]某种类型的类型t，但是的类型签名pick意味着pick ls具有IO a某种类型的类型a。GHC抱怨它期望pick ls具有列表类型[a]（由于do-block的类型），但其实际类型却是IO a（由于的类型签名pick）。

我相信您在概念上犯的错误是，您正在考虑将其IO视为对IO友好的类型的修饰符。因此，如果IO a是a可以使用有效IO计算生成的，那么必须是s [IO a]的列表，并且a每个列表都可以使用有效IO计算生成。但这是错误的！

相反，您应该将其IO a视为IO 操作（例如配方），该操作在执行时会产生a。如果您想要这样的列表a，则不需要动作/配方的列表，每个动作/配方都会产生一个a（即，您不需要[IO a]）。相反，您需要一个操作/配方来生成一个as 列表，因此您需要一个IO [a]。

因此，shuffle应具有类型签名：

shuffle :: [a] -> IO [a]

进行此更改将导致最后一个表达式的另一个错误：

(return x) : shuffle y

这里的问题来自同一个概念上的错误：您正在使用（琐碎的）动作/食谱来生成x并尝试创建动作/食谱列表（尽管现在shuffle y不再是列表，因此存在类型不匹配）。相反，您希望将其替换为：

xs <- shuffle y  -- use `shuffle y :: IO [a]` action to get `xs :: [a]`
return (x:xs)    -- make an action to return the whole list (type `IO [a]`)

您还会发现您需要为Eq ashuffle 添加约束，因为需要调用它remove；另外，除非您正确处理空列表情况，否则此操作将挂起。最终版本为shuffle：

shuffle :: (Eq a) => [a] -> IO [a]
shuffle [] = return []
shuffle ls = do
    x <- pick ls
    let y = remove x ls
    xs <- shuffle y
    return (x:xs)

那应该工作：

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