haskell - Haskell:RandomGen丢弃一半的值

我正在基于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？

最佳答案

这与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

randomGen

haskell - Haskell:RandomGen丢弃一半的值