如何在没有替换数字([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])
使用random甚至MonadRandom来实现你的洗牌。 here存在一些好的答案
但这确实可以运作。这是幕后发生的事情。
随机性是Haskell中你遇到并且必须处理杂质的第一个地方 - 这看起来很冒犯,因为洗牌和样品看起来很简单,并且不觉得它们应该捆绑在一起打印到物理屏幕或发射核武器,但往往purity == referentially transparent
和referentially透明随机性would be useless。
random = 9 -- a referentially transparent random number
所以我们需要一个关于随机性的不同想法来使它变得纯粹。
用于增强可重复性的科学代码中的典型“作弊” - 非常重要 - 是修复实验的随机种子,以便其他人可以验证每次运行代码时它们获得完全相同的结果。这正是参考透明度!我们来试试吧。
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
值的确定性的,但只看到流而不是种子的观察者应该无法预测其未来值。
我们可以使用随机的整数流来混淆列表吗?当然,我们可以通过使用模运算。
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
另一种“种子消费”参考透明“随机”功能。
所以这似乎是一个重复的趋势。事实上,如果你浏览模块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])
但是你会注意到一些令人烦恼的事情:如果我们想要做出不同的随机排列,我们需要不断变化
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。由于再次引用透明度,这“有意义” - 一组随机数必须相互随机,因此您需要将信息从每个随机事件传递到下一个事件。
不过,这真的很烦人。我们可以做得更好吗?
嗯,通常我们需要的是一种方法,让一个函数接受随机种子,然后输出一些“随机”结果和下一个种子。
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))
而且我们知道我们可以在Seed
中创建有意义的IO
s,所以将Random
类型转换为IO
有一个明显的功能
runRandom :: Random a -> IO a
runRandom (Random f) = do seed <- newSeed
let (result, _) = f seed
return result
现在感觉就像我们有一些有用的东西--- a
类型的随机值的概念,Random a
只是Seed
s上的一个函数,它返回下一个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
这就是我一直在写的全部事情的核心。随机性可以很好地存在于IO
monad中,但它也可以作为更简单的Random
monad存在。我们可以立即编写实例。
instance Monad Random where
return x = Random (\seed -> (x, seed))
rx >>= f = bindRandom rx f
因为它是monad,我们获得免费的do
表示法
brownianMotion' = do x <- random
rest <- brownianMotion'
return $ x : map (+x) rest
你甚至可以得到幻想并称runRandom
为monad同态,但这是一个非常不同的话题。
所以,回顾一下
Seed
sSeed
s很烦人Seed
s而真正简短的回答是你可能想要使用random甚至MonadRandom来实现你的洗牌。它们通常会为“抽样”派上用场。
干杯!
你在找permutations吗?
似乎cropAt
可以通过takeWhile
实现。我个人更喜欢手工制作的标准组合器。
你可以从我的Haskell学习开始找到一些简单的解决方案。如果真相被告知,我仍然在开始或稍微落后;-)
import System.Random
import Control.Applicative
shuffle :: [a] -> IO [a]
shuffle [] = return []
shuffle lst = do
(e, rest) <- pickElem <$> getIx
(e:) <$> shuffle rest
where
getIx = getStdRandom $ randomR (1, length lst)
pickElem n = case splitAt n lst of
([], s) -> error $ "failed at index " ++ show n -- should never match
(r, s) -> (last r, init r ++ s)
似乎每个人都曾在某个时间点遇到过这种情况。这是我对问题的快速解决方案:
import System.Random
shuffle :: [a] -> IO [a]
shuffle [] = return []
shuffle xs = do randomPosition <- getStdRandom (randomR (0, length xs - 1))
let (left, (a:right)) = splitAt randomPosition xs
fmap (a:) (shuffle (left ++ right))
请注意,复杂度为O(N ^ 2),因此对于较大的列表而言,这是非常低效的。其他方法是通过使用可变数组(线性复杂度)来实现Fisher-Yates shuffle:
import Data.Array.IO
import System.Random
swapElements_ :: (MArray a e m, Ix i) => a i e -> i -> i -> m ()
swapElements_ arr i j = do a <- readArray arr i
b <- readArray arr j
writeArray arr i b
writeArray arr j a
return ()
shuffle :: [a] -> IO [a]
shuffle xs = do let upperBound = length xs
arr <- (newListArray (1, upperBound) :: [a] -> IO (IOArray Int a)) xs
mapM_ (shuffleCycle arr) [2..upperBound]
getElems arr
where shuffleCycle arr i = do j <- getStdRandom (randomR (1, i))
swapElements_ arr i j
要重新排列列表,请使用random-shuffle库:
import System.Random (newStdGen)
import System.Random.Shuffle (shuffle')
main = do
rng <- newStdGen
let xs = [1,2,3,4,5]
print $ shuffle' xs (length xs) rng