如何在haskell中洗牌 [英] How to shuffle a list in haskell
问题描述
我如何从一组数字（ [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
|否则= [y]
然而，我无法弄清楚如何洗牌清单（或理解Monads ）。
- 从[1，2，3]中取样无需替换，直到碰到3
- x< - shuffle [1，2，3]
- print（chopAt 3 x）
main = do
- shuffle [1,2,3]
print （chopAt 3 [1，3，2]）
使用随机，甚至可能 MonadRandom 实施你的洗牌。一些好的答案存在这里
但是这真的可以运作。这是后台发生的事情。
I。
随机性是Haskell中的第一个地方之一，你遇到并且必须处理不纯物 - 这似乎是令人讨厌的，因为洗牌和样品看起来很简单，并且不觉得应该将它们打印到物理屏幕或发射核弹，但通常纯度==透明透明和引用透明随机性将毫无用处。
random = 9 - 一个透明的随机数
所以我们需要关于随机性的一个不同的想法来使它变得纯净。
II。
科学代码中用于提高再现性的一个典型欺骗 - 非常重要 - 是修复实验的随机种子，以便其他人可以验证他们每次获得完全相同的结果你的代码运行时间。这完全是参考透明度！让我们试试看。
type Seed = Int
random :: Seed - > （Int，Seed）
random s =（mersenneTwisterPerturb s，splitSeed s）
其中 mersenneTwisterPerturb 是伪随机映射，从种子 s到 Int 和 splitSeed 是从种子 s到种子 s的伪随机映射。请注意，这两个函数都是完全确定性的（并且是引用透明的），所以 random 也是如此，但我们可以创建一个无限的，懒惰的伪随机数据流，就像
randomStream :: Seed - > [Int]
randomStram s = mersenneTwisterPerturb s：randomStream（splitSeed s）
流是基于种子值的确定性，但只能看到流而不看到种子的观察者应该无法预测其未来值。
III。
我们可以使用随机整数流来对列表进行整理吗？当然，我们可以通过使用模块化算术。
shuffle':: [Int] - > [a] - > （首先，休息）= splitAt（我`mod`长度xs）xs
in（last firsts）：shuffle is（init firsts + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++）或者，为了使它更加独立，我们可以将我们的流生成函数进行预组合，以获得
shuffle :: Seed - > [a] - > [a]
shuffle s xs = shuffle'（randomStream s）xs
另一个种子消费引导透明随机功能。
IV。
所以这似乎是一个重复的趋势。实际上，如果你浏览模块 System.Random ，你会看到很多函数，比如我们上面写的（我已经指定了一些类型类）。 b
$ b
random ::（Random a）=> StdGen - > （a，StdGen）
randoms ::（Random a）=> StdGen - > [a]
其中随机是类型类可以随机生成， StdGen 是一种种子。这已经足够实际工作代码来编写必要的洗牌功能。
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]
- 使用`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。
好的，我们需要的是一种具有功能的方法接受随机种子，然后输出一些随机化结果和下一个种子。
withSeed： ：（种子 - > a） - >种子 - > （a，Seed）
withSeed fs =（fs，splitSeed s）
结果类型 withSeed s :: Seed - > （a，种子）是一个相当普遍的结果。让我们给它一个名字
pre $ newtype Random a = Random（Seed - >（a，Seed））
我们知道我们可以在<$中创建有意义的 Seed c $ c> IO ，所以有一个明显的函数可以将 Random 类型转换为 IO
runRandom :: Random a - > IO a
runRandom（Random f）= do seed< - newSeed
let（result，_）= f seed
返回结果
现在感觉我们已经有了一些有用的东西---一个随机值类型 a ，随机一个只是种子的函数，它返回下一个种子，以便稍后随机值不会全部相同。我们甚至可以让一些机器编写随机值，并自动执行 Seed -passing
sequenceRandom :: Random a - >随机b - >随机b
sequenceRandom（随机fa）（随机fb）=
随机$ \seed - > let（_aValue，newSeed）= fa seed in fb newSeed
但这有点愚蠢，因为我们只是扔掉 _aValue 。让我们把它们组合起来，这样第二个随机数实际上取决于第一个随机值。
bindRandom :: Random a - > （a - >随机b） - >随机b
bindRandom（随机fa）getRb =
随机$ \seed - > let（aValue，newSeed）= fa seed
（Random fb）= getRb aValue
in fb newSeed
我们也应该注意到，我们可以对 Random 值做纯事情，例如，将随机数乘以2：
randomTimesTwo :: Random Int - >随机Int
randomTimesTwo（随机f）=随机$ \seed - > let（value，newSeed）= f seed seed
in（value * 2，newSeed）
我们可以把它作为一个Functor实例抽象出来
$ b $ pre $ $ $ $ $ $ $ $ $实例Functor Random其中
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存在。我们可以立即写实例。
pre $实例Monad随机其中
返回x =随机（\ seed - > （x，seed））
rx>> = f = bindRandom rx f
由于这是一个单子，我们可以免费获得 do notation
brownianMotion' = do << - random
rest< - brownianMotion'
return $ x：map（+ x）rest
，你甚至可以看中并称 runRandom 单子同态，但这是一个非常不同的话题。
因此，要用引用透明的语言来回顾
- 随机性，需要
Seeds - carting
种子s很烦人 - 模式到提升和绑定随机值，它们自然地路由
种子s
- 该模式形成一个monad
真正简短的答案是您可能想要使用 random ，甚至可能 MonadRandom 来实现您的洗牌。他们会派上用场来进行取样。
干杯！
How can I sample without replacement from a set of numbers ([1, 2, 3]) until I hit x?
My plan was to shuffle the list [1, 2, 3] and chop it at 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]
However I could not figure out how to shuffle the list (or understand Monads yet).
-- 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 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!
这篇关于如何在haskell中洗牌的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
