如何随机选择 Haskell 中的列表

Question

我正在尝试使用随机数随机排列任意列表。我在这里问这个的原因是因为我已经做了一个函数，但我不知道为什么它不起作用。

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 用于 pick，但是 ls 被定义为 [a]?

如果我不明白这有什么根本性的错误，是否有另一种方法可以如此简单地在 Haskell 中随机排列列表？最好没有任何进口。

Answer 1

您可能正在寻找如下函数：

shuffle :: [a] -> <b>IO</b> [a]
shuffle [] = return []
shuffle ls = do
    x <- pick ls
    fmap (x:) (shuffle (remove x ls))

因此，您首先从 ls 中选择一个元素，然后在列表的列表中递归。然后我们可以 return 一个列表 (x:xs).

以上可以做得更优雅。我把它留作练习。例如，每次迭代计算列表的 length 通常不是一个好主意，因为这使得算法 O(n²)。此外，您可能希望将 pick 重写为 return 项目和删除后的列表的函数。

Answer 2

发生的事情是 shuffle 的类型签名暗示其 do 块具有类型 [IO a]。这意味着这个 do 块的 monad 不是你想要的 IO，而是列表 [] 的 monad 实例，因为这里是 "outermost" 类型构造函数。因此，do 块要求表达式 pick ls 具有某种类型 t 的类型 [t]，但 pick 的类型签名意味着 pick ls 具有某种类型 a 的类型 IO a。 GHC 抱怨它期望 pick ls 有一个列表类型 [a] （因为 do-block 的类型）但它的实际类型是 IO a （因为类型签名 pick).

我认为您犯的概念错误是您将 IO 视为一种类型的修饰符，使其对 IO 友好。因此，如果 IO a 是可以使用有效的 IO 计算生成的 a，那么 [IO a] 一定是 a 的列表，每个列表都可以使用有效的 IO 计算生成。但这是错误的！

相反，您应该将 IO a 视为一个 IO 动作（就像一个食谱），在执行时可以产生一个 a。如果你想要一个这样的 a 的列表，你不需要 actions/recipes 的列表，每个列表产生一个 a（即，你不想要 [IO a]).相反，您需要一个生成 a 列表的单个 action/recipe，因此您需要一个 IO [a].

所以，shuffle 应该有类型签名：

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

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

(return x) : shuffle y

这里的问题来自于相同的概念错误：您正在使用（微不足道的）action/recipe 来生成 x 并尝试创建 actions/recipes 的列表（尽管现在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 a 约束来随机播放，因为它需要调用 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]

如何随机选择 Haskell 中的列表

How to shuffle a list in Haskell using random selection

random

haskell

functional-programming

shuffle

list