System/Random.hs

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