如何打乱列表？

如何从一组数字（[1, 2, 3]）直到我击中x？ 我的计划是重新调整列表[1, 2, 3]并把它砍在x:

-- chopAt 3 [2, 3, 1] == [2, 3]
-- chopAt 3 [2, 1, 3] == [2, 1, 3]
-- chopAt 3 [3, 1, 2] == [3]
chopAt _ [] = []
chopAt x (y:ys)
  | x /= y    = y : chopAt x ys
  | otherwise = [y]

然而我不知道如何洗牌列表（或理解 Monads）。

-- sample without replacement from [1, 2, 3] until one hits a 3
-- x <- shuffle [1, 2, 3]
-- print (chopAt 3 x)
main = do
-- shuffle [1, 2, 3]
  print (chopAt 3 [1, 3, 2])

Use random http://hackage.haskell.org/packages/archive/random/1.0.0.3/doc/html/System-Random.html甚至也许莫纳德随机 http://hackage.haskell.org/packages/archive/MonadRandom/0.1.3/doc/html/Control-Monad-Random.html来实施你的洗牌。存在一些好的答案here http://www.haskell.org/haskellwiki/Random_shuffle

但这确实是可操作的。这是幕后发生的事情。

I.

随机性是 Haskell 中你首先遇到并且必须处理杂质的地方之一——这似乎很令人反感，因为洗牌和样本看起来很简单，而且感觉它们不应该与打印到物理屏幕或发射核武器，但经常purity == referentially transparent和参照透明的随机性将毫无用处 https://xkcd.com/221/.

random = 9 -- a referentially transparent random number

所以我们需要对随机性有一个不同的想法来使其纯粹。

II.

科学代码中用于增强再现性的典型“作弊”（非常重要）是修复实验的随机种子，以便其他人可以验证他们得到的结果完全相同的结果每次运行代码时。这正是引用透明度！我们来试试吧。

type Seed = Int
random :: Seed -> (Int, Seed)
random s = (mersenneTwisterPerturb s, splitSeed s)

where mersenneTwisterPerturb是一个伪随机映射Seeds to Int and splitSeed是一个伪随机映射Seeds to Seeds。请注意，这两个函数都是完全确定性的（并且引用透明），因此random也是如此，但我们可以像这样创建一个无限的、惰性的伪随机流

randomStream :: Seed -> [Int]
randomStram s = mersenneTwisterPerturb s : randomStream (splitSeed s)

同样，该流是确定性的，基于Seed值，但是只看到流而不看到种子的观察者应该无法预测其未来值。

III.

我们可以使用随机整数流来打乱列表吗？当然我们可以，通过使用模运算。

shuffle' :: [Int] -> [a] -> [a]
shuffle' (i:is) xs = let (firsts, rest) = splitAt (i `mod` length xs) xs
                     in (head rest) : shuffle' is (firsts ++ tail rest)

或者，为了使其更加独立，我们可以预先组合流生成函数以获得

shuffle :: Seed -> [a] -> [a]
shuffle s xs = shuffle' (randomStream s) xs

另一个“种子消耗”引用透明的“随机”函数。

IV.

所以这似乎是一个重复的趋势。事实上，如果你浏览该模块System.Random你会看到很多像我们上面写的那样的函数（我专门设计了一些类型类）

random :: (Random a) => StdGen -> (a, StdGen)
randoms :: (Random a) => StdGen -> [a]

where Random是可以随机生成的事物的类型类别StdGen是一种Seed。这已经是足够的实际工作代码来编写必要的洗牌函数。

shuffle :: StdGen -> [a] -> [a]
shuffle g xs = shuffle' (randoms g) xs

还有一个IO功能newStdGen :: IO StdGen这将让我们构建一个随机种子。

main = do gen <- newStdGen
          return (shuffle gen [1,2,3,4,5])

但你会注意到一些烦人的事情：如果我们想要制作，我们需要不断改变生成不同的随机排列

main = do gen1 <- newStdGen
          shuffle gen1 [1,2,3,4,5]
          gen2 <- newStdGen
          shuffle gen2 [1,2,3,4,5]

          -- using `split :: StdGen -> (StdGen, StdGen)`
          gen3 <- newStdGen
          let (_, gen4) = split gen3
          shuffle gen3 [1,2,3,4,5]
          let (_, gen5) = split gen4
          shuffle gen4 [1,2,3,4,5]

这意味着你要么必须做很多StdGen如果你想要不同的随机数，记账或留在 IO 中。这“有意义”，因为引用透明度再次——一组随机数必须是随机的相对于彼此因此您需要将每个随机事件的信息传递到下一个随机事件。

不过，这确实很烦人。我们可以做得更好吗？

V.

好吧，通常我们需要的是一种让函数接受随机种子然后输出一些“随机”结果和next seed.

withSeed :: (Seed -> a) -> Seed -> (a, Seed)
withSeed f s = (f s, splitSeed s)

结果类型withSeed f :: Seed -> (a, Seed)是一个相当普遍的结果。让我们给它起个名字

newtype Random a = Random (Seed -> (a, Seed))

我们知道我们可以创造有意义的Seeds in IO，所以有一个明显的函数可以转换Random类型为IO

runRandom :: Random a -> IO a
runRandom (Random f) = do seed <- newSeed
                          let (result, _) = f seed
                          return result

现在感觉我们已经得到了一些有用的东西——类型随机值的概念a, Random a只是一个函数Seeds 返回下一个Seed以便以后Random值不会全部相同。我们甚至可以制作一些机器来组合随机值并执行此操作Seed-自动通过

sequenceRandom :: Random a -> Random b -> Random b
sequenceRandom (Random fa) (Random fb) = 
    Random $ \seed -> let (_aValue, newSeed) = fa seed in fb newSeed

但这有点愚蠢，因为我们只是扔掉_aValue。让我们组合它们，使第二个随机数实际上很大程度上取决于第一个随机值。

bindRandom :: Random a -> (a -> Random b) -> Random b
bindRandom (Random fa) getRb = 
    Random $ \seed -> let (aValue, newSeed) = fa seed
                          (Random fb)       = getRb aValue
                      in fb newSeed

我们还应该注意到，我们可以做“纯粹”的事情Random值，例如，将随机数乘以 2：

randomTimesTwo :: Random Int -> Random Int
randomTimesTwo (Random f) = Random $ \seed -> let (value, newSeed) = f seed
                                              in (value*2, newSeed)

我们可以将其抽象为 Functor 实例

instance Functor Random where
  fmap f (Random step) = Random $ \seed -> let (value, newSeed) = step seed
                                           in (f value, newSeed)

现在我们可以创建很酷的随机效果，例如布朗运动

brownianMotion :: Random [Int]
brownianMotion = 
   bindRandom random $ \x -> 
       fmap (\rest -> x : map (+x) rest) brownianMotion

VI.

这触及了我一直在写的整个问题的核心。随机性可以存在于IOmonad 非常好，但它也可以作为一个更简单的对象单独存在Random单子。我们可以立即编写实例。

instance Monad Random where
  return x = Random (\seed -> (x, seed))
  rx >>= f = bindRandom rx f

因为它是一个单子，所以我们得到了自由do符号

brownianMotion' = do x <- random
                     rest <- brownianMotion'
                     return $ x : map (+x) rest

你甚至可以打电话给runRandom单子同态，但这是一个非常不同的话题。

所以，回顾一下

1. 引用透明语言中的随机性需要Seeds
2. carting Seed很烦人
3. “提升”和“绑定”随机值有一个常见的模式，用于路由Seed自然而然地在身边
4. 该模式形成一个单子

真正简短的答案是您可能想要使用random http://hackage.haskell.org/packages/archive/random/1.0.0.3/doc/html/System-Random.html甚至也许莫纳德随机 http://hackage.haskell.org/packages/archive/MonadRandom/0.1.3/doc/html/Control-Monad-Random.html来实施你的洗牌。通常，它们对于“采样”会派上用场。

Cheers!