1{-# LANGUAGE CPP #-} 2{-# LANGUAGE DefaultSignatures #-} 3{-# LANGUAGE Trustworthy #-} 4 5-- | 6-- Module : System.Random 7-- Copyright : (c) The University of Glasgow 2001 8-- License : BSD-style (see the file LICENSE in the 'random' repository) 9-- Maintainer : libraries@haskell.org 10-- Stability : stable 11-- 12-- This library deals with the common task of pseudo-random number generation. 13module System.Random 14 ( 15 -- * Introduction 16 -- $introduction 17 18 -- * Usage 19 -- $usagepure 20 21 -- * Pure number generator interface 22 -- $interfaces 23 RandomGen(..) 24 , uniform 25 , uniformR 26 , genByteString 27 , Random(..) 28 , Uniform 29 , UniformRange 30 -- ** Standard pseudo-random number generator 31 , StdGen 32 , mkStdGen 33 34 -- ** Global standard pseudo-random number generator 35 -- $globalstdgen 36 , getStdRandom 37 , getStdGen 38 , setStdGen 39 , newStdGen 40 , randomIO 41 , randomRIO 42 43 -- * Compatibility and reproducibility 44 -- ** Backwards compatibility and deprecations 45 -- $deprecations 46 47 -- ** Reproducibility 48 -- $reproducibility 49 50 -- * Notes for pseudo-random number generator implementors 51 -- ** How to implement 'RandomGen' 52 -- $implementrandomgen 53 54 -- * References 55 -- $references 56 ) where 57 58import Control.Arrow 59import Control.Monad.IO.Class 60import Data.ByteString (ByteString) 61import Data.Int 62import Data.IORef 63import Data.Word 64import Foreign.C.Types 65import GHC.Exts 66import System.IO.Unsafe (unsafePerformIO) 67import System.Random.Internal 68import qualified System.Random.SplitMix as SM 69 70-- $introduction 71-- 72-- This module provides type classes and instances for the following concepts: 73-- 74-- [Pure pseudo-random number generators] 'RandomGen' is an interface to pure 75-- pseudo-random number generators. 76-- 77-- 'StdGen', the standard pseudo-random number generator provided in this 78-- library, is an instance of 'RandomGen'. It uses the SplitMix 79-- implementation provided by the 80-- <https://hackage.haskell.org/package/splitmix splitmix> package. 81-- Programmers may, of course, supply their own instances of 'RandomGen'. 82-- 83-- $usagepure 84-- 85-- In pure code, use 'uniform' and 'uniformR' to generate pseudo-random values 86-- with a pure pseudo-random number generator like 'StdGen'. 87-- 88-- >>> :{ 89-- let rolls :: RandomGen g => Int -> g -> [Word] 90-- rolls n = take n . unfoldr (Just . uniformR (1, 6)) 91-- pureGen = mkStdGen 137 92-- in 93-- rolls 10 pureGen :: [Word] 94-- :} 95-- [4,2,6,1,6,6,5,1,1,5] 96-- 97-- To run use a /monadic/ pseudo-random computation in pure code with a pure 98-- pseudo-random number generator, use 'runGenState' and its variants. 99-- 100-- >>> :{ 101-- let rollsM :: StatefulGen g m => Int -> g -> m [Word] 102-- rollsM n = replicateM n . uniformRM (1, 6) 103-- pureGen = mkStdGen 137 104-- in 105-- runStateGen_ pureGen (rollsM 10) :: [Word] 106-- :} 107-- [4,2,6,1,6,6,5,1,1,5] 108 109------------------------------------------------------------------------------- 110-- Pseudo-random number generator interfaces 111------------------------------------------------------------------------------- 112 113-- $interfaces 114-- 115-- Pseudo-random number generators come in two flavours: /pure/ and /monadic/. 116-- 117-- ['RandomGen': pure pseudo-random number generators] These generators produce 118-- a new pseudo-random value together with a new instance of the 119-- pseudo-random number generator. 120-- 121-- Pure pseudo-random number generators should implement 'split' if they 122-- are /splittable/, that is, if there is an efficient method to turn one 123-- generator into two. The pseudo-random numbers produced by the two 124-- resulting generators should not be correlated. See [1] for some 125-- background on splittable pseudo-random generators. 126-- 127-- ['System.Random.Stateful.StatefulGen': monadic pseudo-random number generators] 128-- See "System.Random.Stateful" module 129-- 130 131-- | Generates a value uniformly distributed over all possible values of that 132-- type. 133-- 134-- This is a pure version of 'System.Random.Stateful.uniformM'. 135-- 136-- ====__Examples__ 137-- 138-- >>> import System.Random 139-- >>> let pureGen = mkStdGen 137 140-- >>> uniform pureGen :: (Bool, StdGen) 141-- (True,StdGen {unStdGen = SMGen 11285859549637045894 7641485672361121627}) 142-- 143-- @since 1.2.0 144uniform :: (RandomGen g, Uniform a) => g -> (a, g) 145uniform g = runStateGen g uniformM 146 147-- | Generates a value uniformly distributed over the provided range, which 148-- is interpreted as inclusive in the lower and upper bound. 149-- 150-- * @uniformR (1 :: Int, 4 :: Int)@ generates values uniformly from the set 151-- \(\{1,2,3,4\}\) 152-- 153-- * @uniformR (1 :: Float, 4 :: Float)@ generates values uniformly from the 154-- set \(\{x\;|\;1 \le x \le 4\}\) 155-- 156-- The following law should hold to make the function always defined: 157-- 158-- > uniformR (a, b) = uniformR (b, a) 159-- 160-- This is a pure version of 'System.Random.Stateful.uniformRM'. 161-- 162-- ====__Examples__ 163-- 164-- >>> import System.Random 165-- >>> let pureGen = mkStdGen 137 166-- >>> uniformR (1 :: Int, 4 :: Int) pureGen 167-- (4,StdGen {unStdGen = SMGen 11285859549637045894 7641485672361121627}) 168-- 169-- @since 1.2.0 170uniformR :: (RandomGen g, UniformRange a) => (a, a) -> g -> (a, g) 171uniformR r g = runStateGen g (uniformRM r) 172 173-- | Generates a 'ByteString' of the specified size using a pure pseudo-random 174-- number generator. See 'uniformByteString' for the monadic version. 175-- 176-- ====__Examples__ 177-- 178-- >>> import System.Random 179-- >>> import Data.ByteString 180-- >>> let pureGen = mkStdGen 137 181-- >>> unpack . fst . genByteString 10 $ pureGen 182-- [51,123,251,37,49,167,90,109,1,4] 183-- 184-- @since 1.2.0 185genByteString :: RandomGen g => Int -> g -> (ByteString, g) 186genByteString n g = runStateGenST g (uniformByteStringM n) 187{-# INLINE genByteString #-} 188 189-- | The class of types for which uniformly distributed values can be 190-- generated. 191-- 192-- 'Random' exists primarily for backwards compatibility with version 1.1 of 193-- this library. In new code, use the better specified 'Uniform' and 194-- 'UniformRange' instead. 195class Random a where 196 197 -- | Takes a range /(lo,hi)/ and a pseudo-random number generator 198 -- /g/, and returns a pseudo-random value uniformly distributed over the 199 -- closed interval /[lo,hi]/, together with a new generator. It is unspecified 200 -- what happens if /lo>hi/. For continuous types there is no requirement 201 -- that the values /lo/ and /hi/ are ever produced, but they may be, 202 -- depending on the implementation and the interval. 203 {-# INLINE randomR #-} 204 randomR :: RandomGen g => (a, a) -> g -> (a, g) 205 default randomR :: (RandomGen g, UniformRange a) => (a, a) -> g -> (a, g) 206 randomR r g = runStateGen g (uniformRM r) 207 208 -- | The same as 'randomR', but using a default range determined by the type: 209 -- 210 -- * For bounded types (instances of 'Bounded', such as 'Char'), 211 -- the range is normally the whole type. 212 -- 213 -- * For fractional types, the range is normally the semi-closed interval 214 -- @[0,1)@. 215 -- 216 -- * For 'Integer', the range is (arbitrarily) the range of 'Int'. 217 {-# INLINE random #-} 218 random :: RandomGen g => g -> (a, g) 219 default random :: (RandomGen g, Uniform a) => g -> (a, g) 220 random g = runStateGen g uniformM 221 222 -- | Plural variant of 'randomR', producing an infinite list of 223 -- pseudo-random values instead of returning a new generator. 224 {-# INLINE randomRs #-} 225 randomRs :: RandomGen g => (a,a) -> g -> [a] 226 randomRs ival g = build (\cons _nil -> buildRandoms cons (randomR ival) g) 227 228 -- | Plural variant of 'random', producing an infinite list of 229 -- pseudo-random values instead of returning a new generator. 230 {-# INLINE randoms #-} 231 randoms :: RandomGen g => g -> [a] 232 randoms g = build (\cons _nil -> buildRandoms cons random g) 233 234 235-- | Produce an infinite list-equivalent of pseudo-random values. 236-- 237-- ====__Examples__ 238-- 239-- >>> import System.Random 240-- >>> let pureGen = mkStdGen 137 241-- >>> (take 4 . buildRandoms (:) random $ pureGen) :: [Int] 242-- [7879794327570578227,6883935014316540929,-1519291874655152001,2353271688382626589] 243-- 244{-# INLINE buildRandoms #-} 245buildRandoms :: RandomGen g 246 => (a -> as -> as) -- ^ E.g. '(:)' but subject to fusion 247 -> (g -> (a,g)) -- ^ E.g. 'random' 248 -> g -- ^ A 'RandomGen' instance 249 -> as 250buildRandoms cons rand = go 251 where 252 -- The seq fixes part of #4218 and also makes fused Core simpler. 253 go g = x `seq` (x `cons` go g') where (x,g') = rand g 254 255-- Generate values in the Int range 256instance Random Integer where 257 random = first (toInteger :: Int -> Integer) . random 258instance Random Int8 259instance Random Int16 260instance Random Int32 261instance Random Int64 262instance Random Int 263instance Random Word 264instance Random Word8 265instance Random Word16 266instance Random Word32 267instance Random Word64 268#if __GLASGOW_HASKELL >= 802 269instance Random CBool 270#endif 271instance Random CChar 272instance Random CSChar 273instance Random CUChar 274instance Random CShort 275instance Random CUShort 276instance Random CInt 277instance Random CUInt 278instance Random CLong 279instance Random CULong 280instance Random CPtrdiff 281instance Random CSize 282instance Random CWchar 283instance Random CSigAtomic 284instance Random CLLong 285instance Random CULLong 286instance Random CIntPtr 287instance Random CUIntPtr 288instance Random CIntMax 289instance Random CUIntMax 290instance Random CFloat where 291 randomR (CFloat l, CFloat h) = first CFloat . randomR (l, h) 292 random = first CFloat . random 293instance Random CDouble where 294 randomR (CDouble l, CDouble h) = first CDouble . randomR (l, h) 295 random = first CDouble . random 296 297instance Random Char 298instance Random Bool 299instance Random Double where 300 randomR r g = runStateGen g (uniformRM r) 301 random g = runStateGen g (uniformRM (0, 1)) 302instance Random Float where 303 randomR r g = runStateGen g (uniformRM r) 304 random g = runStateGen g (uniformRM (0, 1)) 305 306------------------------------------------------------------------------------- 307-- Global pseudo-random number generator 308------------------------------------------------------------------------------- 309 310-- $globalstdgen 311-- 312-- There is a single, implicit, global pseudo-random number generator of type 313-- 'StdGen', held in a global variable maintained by the 'IO' monad. It is 314-- initialised automatically in some system-dependent fashion. To get 315-- deterministic behaviour, use 'setStdGen'. 316-- 317-- Note that 'mkStdGen' also gives deterministic behaviour without requiring an 318-- 'IO' context. 319 320-- |Sets the global pseudo-random number generator. 321setStdGen :: MonadIO m => StdGen -> m () 322setStdGen = liftIO . writeIORef theStdGen 323 324-- |Gets the global pseudo-random number generator. 325getStdGen :: MonadIO m => m StdGen 326getStdGen = liftIO $ readIORef theStdGen 327 328theStdGen :: IORef StdGen 329theStdGen = unsafePerformIO $ SM.initSMGen >>= newIORef . StdGen 330{-# NOINLINE theStdGen #-} 331 332-- |Applies 'split' to the current global pseudo-random generator, 333-- updates it with one of the results, and returns the other. 334newStdGen :: MonadIO m => m StdGen 335newStdGen = liftIO $ atomicModifyIORef' theStdGen split 336 337{- |Uses the supplied function to get a value from the current global 338random generator, and updates the global generator with the new generator 339returned by the function. For example, @rollDice@ gets a pseudo-random integer 340between 1 and 6: 341 342> rollDice :: IO Int 343> rollDice = getStdRandom (randomR (1,6)) 344 345-} 346getStdRandom :: MonadIO m => (StdGen -> (a, StdGen)) -> m a 347getStdRandom f = liftIO $ atomicModifyIORef' theStdGen (swap . f) 348 where swap (v, g) = (g, v) 349 350 351-- | A variant of 'randomR' that uses the global pseudo-random number 352-- generator. 353randomRIO :: (Random a, MonadIO m) => (a, a) -> m a 354randomRIO range = liftIO $ getStdRandom (randomR range) 355 356-- | A variant of 'random' that uses the global pseudo-random number 357-- generator. 358randomIO :: (Random a, MonadIO m) => m a 359randomIO = liftIO $ getStdRandom random 360 361------------------------------------------------------------------------------- 362-- Notes 363------------------------------------------------------------------------------- 364 365-- $implementrandomgen 366-- 367-- Consider these points when writing a 'RandomGen' instance for a given pure 368-- pseudo-random number generator: 369-- 370-- * If the pseudo-random number generator has a power-of-2 modulus, that is, 371-- it natively outputs @2^n@ bits of randomness for some @n@, implement 372-- 'genWord8', 'genWord16', 'genWord32' and 'genWord64'. See below for more 373-- details. 374-- 375-- * If the pseudo-random number generator does not have a power-of-2 376-- modulus, implement 'next' and 'genRange'. See below for more details. 377-- 378-- * If the pseudo-random number generator is splittable, implement 'split'. 379-- If there is no suitable implementation, 'split' should fail with a 380-- helpful error message. 381-- 382-- === How to implement 'RandomGen' for a pseudo-random number generator with power-of-2 modulus 383-- 384-- Suppose you want to implement a [permuted congruential 385-- generator](https://en.wikipedia.org/wiki/Permuted_congruential_generator). 386-- 387-- >>> data PCGen = PCGen !Word64 !Word64 388-- 389-- It produces a full 'Word32' of randomness per iteration. 390-- 391-- >>> import Data.Bits 392-- >>> :{ 393-- let stepGen :: PCGen -> (Word32, PCGen) 394-- stepGen (PCGen state inc) = let 395-- newState = state * 6364136223846793005 + (inc .|. 1) 396-- xorShifted = fromIntegral (((state `shiftR` 18) `xor` state) `shiftR` 27) :: Word32 397-- rot = fromIntegral (state `shiftR` 59) :: Word32 398-- out = (xorShifted `shiftR` (fromIntegral rot)) .|. (xorShifted `shiftL` fromIntegral ((-rot) .&. 31)) 399-- in (out, PCGen newState inc) 400-- :} 401-- 402-- >>> fst $ stepGen $ snd $ stepGen (PCGen 17 29) 403-- 3288430965 404-- 405-- You can make it an instance of 'RandomGen' as follows: 406-- 407-- >>> :{ 408-- instance RandomGen PCGen where 409-- genWord32 = stepGen 410-- split _ = error "PCG is not splittable" 411-- :} 412-- 413-- 414-- === How to implement 'RandomGen' for a pseudo-random number generator without a power-of-2 modulus 415-- 416-- __We do not recommend you implement any new pseudo-random number generators without a power-of-2 modulus.__ 417-- 418-- Pseudo-random number generators without a power-of-2 modulus perform 419-- /significantly worse/ than pseudo-random number generators with a power-of-2 420-- modulus with this library. This is because most functionality in this 421-- library is based on generating and transforming uniformly pseudo-random 422-- machine words, and generating uniformly pseudo-random machine words using a 423-- pseudo-random number generator without a power-of-2 modulus is expensive. 424-- 425-- The pseudo-random number generator from 426-- <https://dl.acm.org/doi/abs/10.1145/62959.62969 L’Ecuyer (1988)> natively 427-- generates an integer value in the range @[1, 2147483562]@. This is the 428-- generator used by this library before it was replaced by SplitMix in version 429-- 1.2. 430-- 431-- >>> data LegacyGen = LegacyGen !Int32 !Int32 432-- >>> :{ 433-- let legacyNext :: LegacyGen -> (Int, LegacyGen) 434-- legacyNext (LegacyGen s1 s2) = (fromIntegral z', LegacyGen s1'' s2'') where 435-- z' = if z < 1 then z + 2147483562 else z 436-- z = s1'' - s2'' 437-- k = s1 `quot` 53668 438-- s1' = 40014 * (s1 - k * 53668) - k * 12211 439-- s1'' = if s1' < 0 then s1' + 2147483563 else s1' 440-- k' = s2 `quot` 52774 441-- s2' = 40692 * (s2 - k' * 52774) - k' * 3791 442-- s2'' = if s2' < 0 then s2' + 2147483399 else s2' 443-- :} 444-- 445-- You can make it an instance of 'RandomGen' as follows: 446-- 447-- >>> :{ 448-- instance RandomGen LegacyGen where 449-- next = legacyNext 450-- genRange _ = (1, 2147483562) 451-- split _ = error "Not implemented" 452-- :} 453-- 454-- $deprecations 455-- 456-- Version 1.2 mostly maintains backwards compatibility with version 1.1. This 457-- has a few consequences users should be aware of: 458-- 459-- * The type class 'Random' is only provided for backwards compatibility. 460-- New code should use 'Uniform' and 'UniformRange' instead. 461-- 462-- * The methods 'next' and 'genRange' in 'RandomGen' are deprecated and only 463-- provided for backwards compatibility. New instances of 'RandomGen' should 464-- implement word-based methods instead. See below for more information 465-- about how to write a 'RandomGen' instance. 466-- 467-- * This library provides instances for 'Random' for some unbounded types 468-- for backwards compatibility. For an unbounded type, there is no way 469-- to generate a value with uniform probability out of its entire domain, so 470-- the 'random' implementation for unbounded types actually generates a 471-- value based on some fixed range. 472-- 473-- For 'Integer', 'random' generates a value in the 'Int' range. For 'Float' 474-- and 'Double', 'random' generates a floating point value in the range @[0, 475-- 1)@. 476-- 477-- This library does not provide 'Uniform' instances for any unbounded 478-- types. 479-- 480-- $reproducibility 481-- 482-- If you have two builds of a particular piece of code against this library, 483-- any deterministic function call should give the same result in the two 484-- builds if the builds are 485-- 486-- * compiled against the same major version of this library 487-- * on the same architecture (32-bit or 64-bit) 488-- 489-- $references 490-- 491-- 1. Guy L. Steele, Jr., Doug Lea, and Christine H. Flood. 2014. Fast 492-- splittable pseudorandom number generators. In Proceedings of the 2014 ACM 493-- International Conference on Object Oriented Programming Systems Languages & 494-- Applications (OOPSLA '14). ACM, New York, NY, USA, 453-472. DOI: 495-- <https://doi.org/10.1145/2660193.2660195> 496 497-- $setup 498-- 499-- >>> import Control.Monad (replicateM) 500-- >>> import Data.List (unfoldr) 501