X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=System%2FRandom.hs;h=d6517b1c2e31bc6f2fcd47a2bf1b0f2d4dbd678d;hb=f24ac6ce51fab30b74e9ec828d1d5302df75db97;hp=dd6e9edfb7368828a5d58e54cf67b3e88af66660;hpb=24260b389852ab109de6b62822d889d0e66ae723;p=ghc-base.git diff --git a/System/Random.hs b/System/Random.hs index dd6e9ed..d6517b1 100644 --- a/System/Random.hs +++ b/System/Random.hs @@ -8,7 +8,28 @@ -- Stability : stable -- Portability : portable -- --- Random numbers. +-- 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 library provides one instance of 'RandomGen', the abstract +-- data type 'StdGen'. Programmers may, of course, supply their own +-- instances of 'RandomGen'. +-- +-- * The class 'Random' provides a way to extract values of a particular +-- type 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. -- ----------------------------------------------------------------------------- @@ -17,18 +38,15 @@ module System.Random -- $intro - -- * The 'RandomGen' class, and the 'StdGen' generator + -- * Random number generators RandomGen(next, split, genRange) + + -- ** Standard random number generators , StdGen , mkStdGen - -- * The 'Random' class - , Random ( random, randomR, - randoms, randomRs, - randomIO, randomRIO ) - - -- * The global random number generator + -- ** The global random number generator -- $globalrng @@ -37,6 +55,11 @@ module System.Random , setStdGen , newStdGen + -- * Random values of various types + , Random ( random, randomR, + randoms, randomRs, + randomIO, randomRIO ) + -- * References -- $references @@ -66,50 +89,24 @@ getClockTime :: IO ClockTime getClockTime = do t <- readtime nullPtr; return (TOD (toInteger t) ()) #endif -{- $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'. - -[Comment found in this file when merging with Library Report:] - -The June 1988 (v31 \#6) issue of the Communications of the ACM has an -article by Pierre L'Ecuyer called, /Efficient and Portable Combined -Random Number Generators/. Here is the Portable Combined Generator of -L'Ecuyer for 32-bit computers. It has a period of roughly 2.30584e18. - -Transliterator: Lennart Augustsson - --} - -- | The class 'RandomGen' provides a common interface to random number -- generators. +-- +-- Minimal complete definition: 'next' and 'split'. class RandomGen g where - -- |The 'next' operation allows one to extract at least 30 bits (one 'Int''s - -- worth) from the generator, returning a new generator as well. The - -- integer returned may be positive or negative. + -- |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' ([1,4] are the only examples we know 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 @@ -119,7 +116,7 @@ class RandomGen g where -- -- * If @(a,b) = 'genRange' g@, then @a < b@. -- - -- * 'genRange' is not strict. + -- * 'genRange' always returns a pair of defined 'Int's. -- -- The second condition ensures that 'genRange' cannot examine its -- argument, and hence the value it returns can be determined only by the @@ -127,14 +124,14 @@ class RandomGen g where -- 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'. + -- + -- The default definition spans the full range of 'Int'. 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 @@ -144,7 +141,7 @@ 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'\/'Read' instances of 'StdGen' provide a primitive way to save the +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@. @@ -166,6 +163,7 @@ data StdGen instance RandomGen StdGen where next = stdNext split = stdSplit + genRange _ = stdRange instance Show StdGen where showsPrec p (StdGen s1 s2) = @@ -198,8 +196,6 @@ stdFromString s = (mkStdGen num, rest) 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 @@ -346,7 +342,11 @@ 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'' @@ -427,7 +427,7 @@ getStdRandom f = do {- $references -1. FW Burton and RL Page, /Distributed random number generation/, +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 - @@ -436,10 +436,13 @@ 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, /Don\'t trust parallel Monte Carlo/, +4. P #Hellekalek# Hellekalek, /Don\'t trust parallel Monte Carlo/, Department of Mathematics, University of Salzburg, , 1998. +5. Pierre #LEcuyer# L'Ecuyer, /Efficient and portable combined random +number generators/, Comm ACM, 31(6), Jun 1988, pp742-749. + The Web site is a great source of information. -}