我需要生成一个无限的随机整数流,数字范围在[1..n]之间。然而,每个数字p_i的概率提前给出,因此分布不是均匀的。
在Haskell中是否有库函数可以实现这一功能?
正如其他人指出的那样,Control.Monad.Random
中有一个函数,但它的复杂度相当差。这里是一些代码,今天早上我巧合地写了它。它使用了美妙的Alias算法。
module Data.Random.Distribution.NonUniform(randomsDist) where
import Data.Array
import Data.List
import System.Random
genTable :: (Num a, Ord a) => [a] -> (Array Int a, Array Int Int)
genTable ps =
let n = length ps
n' = fromIntegral n
(small, large) = partition ((< 1) . snd) $ zip [0..] $ map (n' *) ps
loop ((l, pl):ls) ((g, pg):gs) probs aliases =
let prob = (l,pl)
alias = (l,g)
pg' = (pg + pl) - 1
gpg = (g, pg')
in if pg' < 1 then loop (gpg:ls) gs (prob:probs) (alias:aliases)
else loop ls (gpg:gs) (prob:probs) (alias:aliases)
loop ls gs probs aliases = loop' (ls ++ gs) probs aliases
loop' [] probs aliases = (array (0,n-1) probs, array (0,n-1) aliases)
loop' ((g,_):gs) probs aliases = loop' gs ((g,1):probs) ((g, -1):aliases)
in loop small large [] []
-- | Generate an infinite list of random values with the given distribution.
-- The probabilities are scaled so they do not have to add up to one.
--
-- Uses Vose's alias method for generating the values.
-- For /n/ values this has O(/n/) setup complexity and O(1) complexity for each
-- generated item.
randomsDist :: (RandomGen g, Random r, Fractional r, Ord r)
=> g -- | random number generator
-> [(a, r)] -- | list of values with the probabilities
-> [a]
randomsDist g xps =
let (xs, ps) = unzip xps
n = length xps
axs = listArray (0, n-1) xs
s = sum ps
(probs, aliases) = genTable $ map (/ s) ps
(g', g'') = split g
is = randomRs (0, n-1) g'
rs = randoms g''
ks = zipWith (\ i r -> if r <= probs!i then i else aliases!i) is rs
in map (axs!) ks
Control.Monad.Random
提供了函数fromList
:: MonadRandom m => [(a, Rational)] -> m a
,可以用来生成由给定列表中的元素随机生成一个单一的值。
在IO
Monad中使用它的方法如下:
import Control.Monad.Random
-- ...
someNums <- evalRandIO . sequence . repeat . fromList $ [(1, 0.3), (2, 0.2), (3, 0.5)]
print $ take 200 someNums
在该软件包中,您可以看到运行Rand
Monad的其他方式。权重不必相加为1。
编辑: 显然Rand
比我想象的更懒惰,因此可以用sequence . repeat
替换replicateM n
,如@shang所建议。
扩展dflemstr的答案,您可以使用Control.Monad.Random创建一个加权值的无限列表,如下所示:
import Control.Monad.Random
import System.Random
weightedList :: RandomGen g => g -> [(a, Rational)] -> [a]
weightedList gen weights = evalRand m gen
where m = sequence . repeat . fromList $ weights
并像这样使用它:
> let values = weightedList (mkStdGen 123) [(1, 2), (2, 5), (3, 10)]
> take 20 values
[2,1,3,2,1,2,2,3,3,3,3,3,3,2,3,3,2,2,2,3]
这不需要使用IO单子,但是您需要提供用于流的随机数生成器。
还有 System.Random.Distributions.frequency
frequency :: (Floating w, Ord w, Random w, RandomGen g) => [(w, a)] -> g -> (a, g)
请查看https://hackage.haskell.org/package/Euterpea-1.0.0/docs/System-Random-Distributions.html