/usr/lib/hugs/packages/base/System/Random.hs is in libhugs-base-bundled 98.200609.21-5.3ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 | -----------------------------------------------------------------------------
-- |
-- Module : System.Random
-- Copyright : (c) The University of Glasgow 2001
-- License : BSD-style (see the file libraries/base/LICENSE)
--
-- Maintainer : libraries@haskell.org
-- Stability : stable
-- Portability : portable
--
-- Random numbers.
--
-----------------------------------------------------------------------------
module System.Random
(
-- $intro
-- * The 'RandomGen' class, and the 'StdGen' generator
RandomGen(next, split, genRange)
, StdGen
, mkStdGen
-- * The 'Random' class
, Random ( random, randomR,
randoms, randomRs,
randomIO, randomRIO )
-- * The global random number generator
-- $globalrng
, getStdRandom
, getStdGen
, setStdGen
, newStdGen
-- * References
-- $references
) where
import Prelude
import System.CPUTime ( getCPUTime )
import System.Time ( getClockTime, ClockTime(..) )
import Data.Char ( isSpace, chr, ord )
import System.IO.Unsafe ( unsafePerformIO )
import Data.IORef
import Numeric ( readDec )
-- The standard nhc98 implementation of Time.ClockTime does not match
-- the extended one expected in this module, so we lash-up a quick
-- replacement here.
{- $intro
This library deals with the common task of pseudo-random
number generation. The library makes it possible to generate
repeatable results, by starting with a specified initial random
number generator; or to get different results on each run by using the
system-initialised generator, or by supplying a seed from some other
source.
The library is split into two layers:
* A core /random number generator/ provides a supply of bits. The class
'RandomGen' provides a common interface to such generators.
* The class 'Random' provides a way to extract particular values from
a random number generator. For example, the 'Float' instance of 'Random'
allows one to generate random values of type 'Float'.
This implementation uses the Portable Combined Generator of L'Ecuyer
["System.Random\#LEcuyer"] for 32-bit computers, transliterated by
Lennart Augustsson. It has a period of roughly 2.30584e18.
-}
-- | The class 'RandomGen' provides a common interface to random number
-- generators.
class RandomGen g where
-- |The 'next' operation returns an 'Int' that is uniformly distributed
-- in the range returned by 'genRange' (including both end points),
-- and a new generator.
next :: g -> (Int, g)
-- |The 'split' operation allows one to obtain two distinct random number
-- generators. This is very useful in functional programs (for example, when
-- passing a random number generator down to recursive calls), but very
-- little work has been done on statistically robust implementations of
-- 'split' (["System.Random\#Burton", "System.Random\#Hellekalek"]
-- are the only examples we know of).
split :: g -> (g, g)
-- |The 'genRange' operation yields the range of values returned by
-- the generator.
--
-- It is required that:
--
-- * If @(a,b) = 'genRange' g@, then @a < b@.
--
-- * 'genRange' is not strict.
--
-- The second condition ensures that 'genRange' cannot examine its
-- argument, and hence the value it returns can be determined only by the
-- instance of 'RandomGen'. That in turn allows an implementation to make
-- a single call to 'genRange' to establish a generator's range, without
-- being concerned that the generator returned by (say) 'next' might have
-- a different range to the generator passed to 'next'.
genRange :: g -> (Int,Int)
-- default method
genRange g = (minBound,maxBound)
{- |The "System.Random" library provides one instance of 'RandomGen', the
abstract data type 'StdGen'.
The 'StdGen' instance of 'RandomGen' has a 'genRange' of at least 30 bits.
The result of repeatedly using 'next' should be at least as statistically
robust as the /Minimal Standard Random Number Generator/ described by
["System.Random\#Park", "System.Random\#Carta"].
Until more is known about implementations of 'split', all we require is
that 'split' deliver generators that are (a) not identical and
(b) independently robust in the sense just given.
The 'Show' and 'Read' instances of 'StdGen' provide a primitive way to save the
state of a random number generator.
It is required that @'read' ('show' g) == g@.
In addition, 'read' may be used to map an arbitrary string (not necessarily one
produced by 'show') onto a value of type 'StdGen'. In general, the 'read'
instance of 'StdGen' has the following properties:
* It guarantees to succeed on any string.
* It guarantees to consume only a finite portion of the string.
* Different argument strings are likely to result in different results.
-}
data StdGen
= StdGen Int Int
instance RandomGen StdGen where
next = stdNext
split = stdSplit
genRange _ = stdRange
instance Show StdGen where
showsPrec p (StdGen s1 s2) =
showsPrec p s1 .
showChar ' ' .
showsPrec p s2
instance Read StdGen where
readsPrec _p = \ r ->
case try_read r of
r@[_] -> r
_ -> [stdFromString r] -- because it shouldn't ever fail.
where
try_read r = do
(s1, r1) <- readDec (dropWhile isSpace r)
(s2, r2) <- readDec (dropWhile isSpace r1)
return (StdGen s1 s2, r2)
{-
If we cannot unravel the StdGen from a string, create
one based on the string given.
-}
stdFromString :: String -> (StdGen, String)
stdFromString s = (mkStdGen num, rest)
where (cs, rest) = splitAt 6 s
num = foldl (\a x -> x + 3 * a) 1 (map ord cs)
{- |
The function 'mkStdGen' provides an alternative way of producing an initial
generator, by mapping an 'Int' into a generator. Again, distinct arguments
should be likely to produce distinct generators.
Programmers may, of course, supply their own instances of 'RandomGen'.
-}
mkStdGen :: Int -> StdGen -- why not Integer ?
mkStdGen s
| s < 0 = mkStdGen (-s)
| otherwise = StdGen (s1+1) (s2+1)
where
(q, s1) = s `divMod` 2147483562
s2 = q `mod` 2147483398
createStdGen :: Integer -> StdGen
createStdGen s
| s < 0 = createStdGen (-s)
| otherwise = StdGen (fromInteger (s1+1)) (fromInteger (s2+1))
where
(q, s1) = s `divMod` 2147483562
s2 = q `mod` 2147483398
-- FIXME: 1/2/3 below should be ** (vs@30082002) XXX
{- |
With a source of random number supply in hand, the 'Random' class allows the
programmer to extract random values of a variety of types.
Minimal complete definition: 'randomR' and 'random'.
-}
class Random a where
-- | Takes a range /(lo,hi)/ and a random number generator
-- /g/, and returns a random value uniformly distributed in the closed
-- interval /[lo,hi]/, together with a new generator. It is unspecified
-- what happens if /lo>hi/. For continuous types there is no requirement
-- that the values /lo/ and /hi/ are ever produced, but they may be,
-- depending on the implementation and the interval.
randomR :: RandomGen g => (a,a) -> g -> (a,g)
-- | The same as 'randomR', but using a default range determined by the type:
--
-- * For bounded types (instances of 'Bounded', such as 'Char'),
-- the range is normally the whole type.
--
-- * For fractional types, the range is normally the semi-closed interval
-- @[0,1)@.
--
-- * For 'Integer', the range is (arbitrarily) the range of 'Int'.
random :: RandomGen g => g -> (a, g)
-- | Plural variant of 'randomR', producing an infinite list of
-- random values instead of returning a new generator.
randomRs :: RandomGen g => (a,a) -> g -> [a]
randomRs ival g = x : randomRs ival g' where (x,g') = randomR ival g
-- | Plural variant of 'random', producing an infinite list of
-- random values instead of returning a new generator.
randoms :: RandomGen g => g -> [a]
randoms g = (\(x,g') -> x : randoms g') (random g)
-- | A variant of 'randomR' that uses the global random number generator
-- (see "System.Random#globalrng").
randomRIO :: (a,a) -> IO a
randomRIO range = getStdRandom (randomR range)
-- | A variant of 'random' that uses the global random number generator
-- (see "System.Random#globalrng").
randomIO :: IO a
randomIO = getStdRandom random
instance Random Int where
randomR (a,b) g = randomIvalInteger (toInteger a, toInteger b) g
random g = randomR (minBound,maxBound) g
instance Random Char where
randomR (a,b) g =
case (randomIvalInteger (toInteger (ord a), toInteger (ord b)) g) of
(x,g) -> (chr x, g)
random g = randomR (minBound,maxBound) g
instance Random Bool where
randomR (a,b) g =
case (randomIvalInteger (toInteger (bool2Int a), toInteger (bool2Int b)) g) of
(x, g) -> (int2Bool x, g)
where
bool2Int False = 0
bool2Int True = 1
int2Bool 0 = False
int2Bool _ = True
random g = randomR (minBound,maxBound) g
instance Random Integer where
randomR ival g = randomIvalInteger ival g
random g = randomR (toInteger (minBound::Int), toInteger (maxBound::Int)) g
instance Random Double where
randomR ival g = randomIvalDouble ival id g
random g = randomR (0::Double,1) g
-- hah, so you thought you were saving cycles by using Float?
instance Random Float where
random g = randomIvalDouble (0::Double,1) realToFrac g
randomR (a,b) g = randomIvalDouble (realToFrac a, realToFrac b) realToFrac g
mkStdRNG :: Integer -> IO StdGen
mkStdRNG o = do
ct <- getCPUTime
(TOD sec _) <- getClockTime
return (createStdGen (sec * 12345 + ct + o))
randomIvalInteger :: (RandomGen g, Num a) => (Integer, Integer) -> g -> (a, g)
randomIvalInteger (l,h) rng
| l > h = randomIvalInteger (h,l) rng
| otherwise = case (f n 1 rng) of (v, rng') -> (fromInteger (l + v `mod` k), rng')
where
k = h - l + 1
b = 2147483561
n = iLogBase b k
f 0 acc g = (acc, g)
f n acc g =
let
(x,g') = next g
in
f (n-1) (fromIntegral x + acc * b) g'
randomIvalDouble :: (RandomGen g, Fractional a) => (Double, Double) -> (Double -> a) -> g -> (a, g)
randomIvalDouble (l,h) fromDouble rng
| l > h = randomIvalDouble (h,l) fromDouble rng
| otherwise =
case (randomIvalInteger (toInteger (minBound::Int), toInteger (maxBound::Int)) rng) of
(x, rng') ->
let
scaled_x =
fromDouble ((l+h)/2) +
fromDouble ((h-l) / realToFrac intRange) *
fromIntegral (x::Int)
in
(scaled_x, rng')
intRange :: Integer
intRange = toInteger (maxBound::Int) - toInteger (minBound::Int)
iLogBase :: Integer -> Integer -> Integer
iLogBase b i = if i < b then 1 else 1 + iLogBase b (i `div` b)
stdRange :: (Int,Int)
stdRange = (0, 2147483562)
stdNext :: StdGen -> (Int, StdGen)
-- Returns values in the range stdRange
stdNext (StdGen s1 s2) = (z', StdGen s1'' s2'')
where z' = if z < 1 then z + 2147483562 else z
z = s1'' - s2''
k = s1 `quot` 53668
s1' = 40014 * (s1 - k * 53668) - k * 12211
s1'' = if s1' < 0 then s1' + 2147483563 else s1'
k' = s2 `quot` 52774
s2' = 40692 * (s2 - k' * 52774) - k' * 3791
s2'' = if s2' < 0 then s2' + 2147483399 else s2'
stdSplit :: StdGen -> (StdGen, StdGen)
stdSplit std@(StdGen s1 s2)
= (left, right)
where
-- no statistical foundation for this!
left = StdGen new_s1 t2
right = StdGen t1 new_s2
new_s1 | s1 == 2147483562 = 1
| otherwise = s1 + 1
new_s2 | s2 == 1 = 2147483398
| otherwise = s2 - 1
StdGen t1 t2 = snd (next std)
-- The global random number generator
{- $globalrng #globalrng#
There is a single, implicit, global random number generator of type
'StdGen', held in some global variable maintained by the 'IO' monad. It is
initialised automatically in some system-dependent fashion, for example, by
using the time of day, or Linux's kernel random number generator. To get
deterministic behaviour, use 'setStdGen'.
-}
-- |Sets the global random number generator.
setStdGen :: StdGen -> IO ()
setStdGen sgen = writeIORef theStdGen sgen
-- |Gets the global random number generator.
getStdGen :: IO StdGen
getStdGen = readIORef theStdGen
theStdGen :: IORef StdGen
theStdGen = unsafePerformIO $ do
rng <- mkStdRNG 0
newIORef rng
-- |Applies 'split' to the current global random generator,
-- updates it with one of the results, and returns the other.
newStdGen :: IO StdGen
newStdGen = do
rng <- getStdGen
let (a,b) = split rng
setStdGen a
return b
{- |Uses the supplied function to get a value from the current global
random generator, and updates the global generator with the new generator
returned by the function. For example, @rollDice@ gets a random integer
between 1 and 6:
> rollDice :: IO Int
> rollDice = getStdRandom (randomR (1,6))
-}
getStdRandom :: (StdGen -> (a,StdGen)) -> IO a
getStdRandom f = do
rng <- getStdGen
let (v, new_rng) = f rng
setStdGen new_rng
return v
{- $references
1. FW #Burton# Burton and RL Page, /Distributed random number generation/,
Journal of Functional Programming, 2(2):203-212, April 1992.
2. SK #Park# Park, and KW Miller, /Random number generators -
good ones are hard to find/, Comm ACM 31(10), Oct 1988, pp1192-1201.
3. DG #Carta# Carta, /Two fast implementations of the minimal standard
random number generator/, Comm ACM, 33(1), Jan 1990, pp87-88.
4. P #Hellekalek# Hellekalek, /Don\'t trust parallel Monte Carlo/,
Department of Mathematics, University of Salzburg,
<http://random.mat.sbg.ac.at/~peter/pads98.ps>, 1998.
5. Pierre #LEcuyer# L'Ecuyer, /Efficient and portable combined random
number generators/, Comm ACM, 31(6), Jun 1988, pp742-749.
The Web site <http://random.mat.sbg.ac.at/> is a great source of information.
-}
|