如何随机播放列表? [英] How to shuffle a list?
问题描述
在打x之前，如何在不替换一组数字([1, 2, 3])的情况下进行采样?
我的计划是将列表[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])
使用此处
但这确实是可行的.这就是幕后发生的事情.
I.
随机性是您在Haskell遇到的第一个必须处理杂质的地方之一-这似乎令人反感，因为混洗和样本看起来是如此简单，并且不觉得应该将它们与打印捆绑在一起物理屏幕或发射核武器，但通常purity == referentially transparent和参照透明的随机性将是无用的.
random = 9 -- a referentially transparent random number
所以我们需要关于随机性的另一种想法以使其纯净.
II.
用于增强可重复性的科学代码中的一个典型骗子"(非常重要)是修复您的实验随机种子，以便其他人每次可以验证自己得到的结果完全相同代码运行.这正是参照透明性！试试吧.
type Seed = Int
random :: Seed -> (Int, Seed)
random s = (mersenneTwisterPerturb s, splitSeed s)
其中，mersenneTwisterPerturb是从Seed s到Int的伪随机映射，而splitSeed是从Seed s到Seed s的伪随机映射.请注意，这两个函数都是完全确定性的(并且是参照透明的)，因此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 (last firsts) : shuffle is (init firsts ++ 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]
其中，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])
但是您会发现一些烦人的事情:如果我们想使不同随机排列
，则需要不断改变genmain = 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.再次具有参照透明性，因此这是有意义的"-一组随机数必须相对于彼此是随机的，因此您需要将信息从每个随机事件传递到下一个事件. /p>
这确实很烦人.我们可以做得更好吗?
V.
好吧，通常我们需要一种让函数接受随机种子然后输出一些随机"结果和 next 种子的方法.
withSeed :: (Seed -> a) -> Seed -> (a, Seed)
withSeed f s = (f s, splitSeed s)
结果类型withSeed s :: Seed -> (a, Seed)是相当普通的结果.我们给它起个名字
newtype Random a = Random (Seed -> (a, Seed))
我们知道我们可以在IO中创建有意义的Seed，因此有一个明显的功能可以将Random类型转换为IO
runRandom :: Random a -> IO a
runRandom (Random f) = do seed <- newSeed
let (result, _) = f seed
return result
现在感觉好像我们有了一些有用的东西--a类型的随机值的概念，Random a只是Seed上的一个函数，它返回下一个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.
这成为我一直在写的整个问题的核心. IO monad可以很好地存在随机性，但是它也可以作为更简单的Random monad单独存在.我们可以立即编写实例.
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为monad同构，但这是一个非常不同的主题.
所以，回顾一下
-
引用透明语言中的
- 随机性需要
Seeds - 刻画
Seed很烦人 - 存在一种常见的模式来提升"和绑定"随机值，从而自然地绕过
Seeds - 该图案形成一个单子
Use random and maybe even MonadRandom to implement your shuffles. A few good answers exist here
But that's really operational. Here's what's going on behind the scenes.
I.
Randomness is one of the first places in Haskell that you encounter and have to handle impurity---which seems offensive, because shuffles and samples seem so simple and don't feel like they ought to be bundled up with printing to a physical screen or launching nukes, but often purity == referentially transparent and referentially transparent randomness would be useless.
random = 9 -- a referentially transparent random number
So we need a different idea about randomness to make it pure.
II.
A typical "cheat" in scientific code used to enhance reproducibility—super important—is to fix your random seed of an experiment so that others can verify that they get exactly the same results every time your code is run. This is exactly referential transparency! Let's try it.
type Seed = Int
random :: Seed -> (Int, Seed)
random s = (mersenneTwisterPerturb s, splitSeed s)
where mersenneTwisterPerturb is a pseudorandom mapping from Seeds to Int and splitSeed is a pseudorandom mapping from Seeds to Seeds. Note that both of these functions are totally deterministic (and referentially transparent), so random is as well, but we can create an infinite, lazy pseudorandom stream like so
randomStream :: Seed -> [Int]
randomStram s = mersenneTwisterPerturb s : randomStream (splitSeed s)
Again, this stream is deterministic based on the Seed value, but an observer who sees only the stream and not the seed should be unable to predict its future values.
III.
Can we shuffle a list using a random stream of integers? Sure we can, by using modular arithmetic.
shuffle' :: [Int] -> [a] -> [a]
shuffle' (i:is) xs = let (firsts, rest) = splitAt (i `mod` length xs) xs
in (last firsts) : shuffle is (init firsts ++ rest)
Or, to make it more self-contained, we can precompose our stream generating function to get
shuffle :: Seed -> [a] -> [a]
shuffle s xs = shuffle' (randomStream s) xs
another "seed consuming" referentially transparent "random" function.
IV.
So this seems to be a repeating trend. In fact, if you browse the module System.Random you'll see lots of functions like what we wrote above (I've specialized some type classes)
random :: (Random a) => StdGen -> (a, StdGen)
randoms :: (Random a) => StdGen -> [a]
where Random is the type class of things which can be generated randomly and StdGen is a kind of Seed. This is already enough actual working code to write the necessary shuffling function.
shuffle :: StdGen -> [a] -> [a]
shuffle g xs = shuffle' (randoms g) xs
and there's an IO function newStdGen :: IO StdGen which will let us build a random seed.
main = do gen <- newStdGen
return (shuffle gen [1,2,3,4,5])
But you'll notice something annoying: we need to keep varying the gen if we want to make different random permutations
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]
This means you'll either have to do lots of StdGen bookkeeping or stay in IO if you want different random numbers. This "makes sense" because of referential transparency again---a set of random numbers have to be random with respect to each other so you need to pass information from each random event on to the next.
It's really annoying, though. Can we do better?
V.
Well, generally what we need is a way to have a function take in a random seed then output some "randomized" result and the next seed.
withSeed :: (Seed -> a) -> Seed -> (a, Seed)
withSeed f s = (f s, splitSeed s)
The result type withSeed s :: Seed -> (a, Seed) is a fairly general result. Let's give it a name
newtype Random a = Random (Seed -> (a, Seed))
And we know that we can create meaningful Seeds in IO, so there's an obvious function to convert Random types to IO
runRandom :: Random a -> IO a
runRandom (Random f) = do seed <- newSeed
let (result, _) = f seed
return result
And now it feels like we've got something useful---a notion of a random value of type a, Random a is just a function on Seeds which returns the next Seed so that later Random values won't all be identical. We can even make some machinery to compose random values and do this Seed-passing automatically
sequenceRandom :: Random a -> Random b -> Random b
sequenceRandom (Random fa) (Random fb) =
Random $ \seed -> let (_aValue, newSeed) = fa seed in fb newSeed
but that's a little silly since we're just throwing away _aValue. Let's compose them such that the second random number actually depends materially on the first random value.
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
We also ought to note that we can do "pure" things to Random values, for instance, multiplying a random number by 2:
randomTimesTwo :: Random Int -> Random Int
randomTimesTwo (Random f) = Random $ \seed -> let (value, newSeed) = f seed
in (value*2, newSeed)
which we can abstract out as a Functor instance
instance Functor Random where
fmap f (Random step) = Random $ \seed -> let (value, newSeed) = step seed
in (f value, newSeed)
and now we can create cool random effects like Brownian motion
brownianMotion :: Random [Int]
brownianMotion =
bindRandom random $ \x ->
fmap (\rest -> x : map (+x) rest) brownianMotion
VI.
And this gets to the heart of the whole matter that I've been writing up to. Randomness can exist in the IO monad perfectly well, but it can also exist on its own as a simpler Random monad. We can write the instance immediately.
instance Monad Random where
return x = Random (\seed -> (x, seed))
rx >>= f = bindRandom rx f
And since it's a monad, we get free do notation
brownianMotion' = do x <- random
rest <- brownianMotion'
return $ x : map (+x) rest
and you could even get fancy and call runRandom a monad homomorphism, but that's a very different topic.
So, to recap
- randomness in a referentially transparent language needs
Seeds - carting
Seeds are is annoying - there's a common pattern to "lifting" and "binding" random values which routes the
Seeds around naturally - that pattern forms a monad
And the really short answer is that you probably want to be using random and maybe even MonadRandom to implement your shuffles. They'll come in handy for "sampling" generally.
Cheers!
这篇关于如何随机播放列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
