Haskell:RandomGen 下降了一半的值

Question

我正在编写一个简单的确定性随机数生成器，基于 xorshift 。这里的目标不是获得密码安全或统计上完美的(伪)随机数生成器，而是能够跨编程语言获得相同的确定性半随机数序列。

我的 Haskell 程序如下所示:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module SimpleRNG where

import Data.Word (Word32)
import Data.Bits (xor, shift)
import System.Random (RandomGen(..))
import Control.Arrow

(|>) :: a -> (a -> b) -> b
(|>) x f = f x
infixl 0 |>

newtype SeedState = SeedState Word32
  deriving (Eq, Show, Enum, Bounded)

seed :: Integral a => a -> SeedState
seed = SeedState . fromIntegral

rand_r :: SeedState -> (Word32, SeedState)
rand_r (SeedState num) = (res, SeedState res)
  where
    res = num
      |> xorshift 13
      |> xorshift (-17)
      |> xorshift 5
    xorshift :: Int -> Word32 -> Word32
    xorshift amount x = x `xor` (shift x amount)

instance RandomGen SeedState where
  next seed_state = (first fromIntegral) $ rand_r seed_state
    where
  genRange seed_state = (fromEnum (minBound `asTypeOf` seed_state),
                fromEnum (maxBound `asTypeOf` seed_state))

  split seed_state@(SeedState num) =  (seed_state', inverted_seed_state')
    where
      (_, seed_state') = next seed_state
      (_, inverted_seed_state') = next inverted_seed_state
      inverted_seed_state = SeedState (maxBound - num)

现在，由于某种原因，在运行时

take 10 $ System.Random.randoms (seed 42) :: [Word32]

与以下 Python 程序的输出相比，它仅返回“奇数”结果:

class SeedState(object):
    def __init__(self, seed = 42):
        self.data = seed

def rand_r(rng_state):
    num = rng_state.data
    num ^= (num << 13) % (2 ** 32)
    num ^= (num >> 17) % (2 ** 32)
    num ^= (num << 5) % (2 ** 32)
    rng_state.data = num
    return num


__global_rng_state = SeedState(42)

def rand():
    global __global_rng_state
    return rand_r(__global_rng_state)

def seed(seed):
    global __global_rng_state
    __global_rng_state = SeedState(seed)

if __name__ == '__main__':
    for x in range(0, 10):
        print(rand())

似乎 System.Random 模块的内部对生成器的返回结果做了一些奇怪的处理(调用

map fst $ take 10 $ iterate (\(_, rng) -> rand_r rng) (rand_r $ seed 42)

给出了我期望的结果。

这很奇怪，因为生成器返回的类型已经是 Word32，因此它可以/应该不改变地传递，而不会发生任何重新映射。

这里发生了什么，有没有办法将这个 xorshift-generator 插入到 System.Random 中并返回相同的结果？

Answer 1

这与 System.Random.randoms 的行为有关，它重复地将random应用于RandomGen，而不是next。

class Random a where
    ...
    random :: (RandomGen g) => g -> (a, g)

Random 类允许您在不同的枚举中重用 RandomGen 实例，以及 Word32 的实例(以及几乎所有其他类型)定义为

instance Random Word32     where randomR = randomIvalIntegral; random = randomBounded

randomBounded 只是调用 randomR，因此 random 的行为由 `

决定

 randomIvalIntegral (l,h) = randomIvalInteger (toInteger l, toInteger h)

randomIvalInteger是一个有趣的函数，你可以阅读源码here 。它实际上导致了您的问题，因为该函数将根据生成器的范围和生成的范围丢弃一定数量的中间值。

要获取所需的值，您只需使用 next - 最简单的方法就是定义

randoms' g = x : (randoms' g') where (x, g') = next g