X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=System%2FRandom.hs;h=8b648a73654a2b1087e54b985dece207be395de1;hb=a2a70b9bf60672c72b35654105402cf21238b6f4;hp=47e3a480ed0929f4bd02ac6814700bf499a94a5d;hpb=ca13f11c4be43674515da0e41808d8627f2017e5;p=haskell-directory.git diff --git a/System/Random.hs b/System/Random.hs index 47e3a48..8b648a7 100644 --- a/System/Random.hs +++ b/System/Random.hs @@ -5,10 +5,31 @@ -- License : BSD-style (see the file libraries/base/LICENSE) -- -- Maintainer : libraries@haskell.org --- Stability : provisional +-- 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 @@ -44,80 +67,84 @@ module System.Random import Prelude +#ifdef __NHC__ +import CPUTime ( getCPUTime ) +import Foreign.Ptr ( Ptr, nullPtr ) +import Foreign.C ( CTime, CUInt ) +#else import System.CPUTime ( getCPUTime ) import System.Time ( getClockTime, ClockTime(..) ) +#endif import Data.Char ( isSpace, chr, ord ) import System.IO.Unsafe ( unsafePerformIO ) import Data.IORef import Numeric ( readDec ) -#ifdef __GLASGOW_HASKELL__ -import GHC.IOBase ( stToIO ) +-- 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. +#ifdef __NHC__ +data ClockTime = TOD Integer () +foreign import ccall "time.h time" readtime :: Ptr CTime -> IO CTime +getClockTime :: IO ClockTime +getClockTime = do CTime t <- readtime nullPtr; return (TOD (toInteger t) ()) #endif -{- $intro - -The "Random" 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 - --} - --- |RandomGen --- The class 'RandomGen' provides a common interface to random number generators. +-- | 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 + -- the generator. + -- + -- It is required that: + -- + -- * If @(a,b) = 'genRange' g@, then @a < b@. + -- + -- * '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 + -- 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'. + -- + -- The default definition spans the full range of 'Int'. genRange :: g -> (Int,Int) - -- default mathod + -- default method genRange g = (minBound,maxBound) -{- |The "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 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'\/'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@. +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' @@ -125,16 +152,10 @@ 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. +* It guarantees to consume only a finite portion of the string. * Different argument strings are likely to result in different results. -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'. - -} data StdGen @@ -143,6 +164,7 @@ data StdGen instance RandomGen StdGen where next = stdNext split = stdSplit + genRange _ = stdRange instance Show StdGen where showsPrec p (StdGen s1 s2) = @@ -171,6 +193,11 @@ stdFromString s = (mkStdGen num, rest) 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. +-} mkStdGen :: Int -> StdGen -- why not Integer ? mkStdGen s | s < 0 = mkStdGen (-s) @@ -189,51 +216,54 @@ createStdGen s -- FIXME: 1/2/3 below should be ** (vs@30082002) XXX -{- |The 'Random' class +{- | With a source of random number supply in hand, the 'Random' class allows the programmer to extract random values of a variety of types. -* 'randomR' 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. - -* 'random' does the same as 'randomR', but does not take a range. - -(1) For bounded types (instances of 'Bounded', such as 'Char'), the range is -normally the whole type. - -(2) For fractional types, the range is normally the semi-closed interval @[0,1)@. - -(3) For 'Integer', the range is (arbitrarily) the range of 'Int'. +Minimal complete definition: 'randomR' and 'random'. -* The plural versions, 'randomRs' and 'randoms', produce an infinite list of -random values, and do not return a new generator. - -* The 'IO' versions, 'randomRIO' and 'randomIO', use the global random number -generator (see Section 17.3 -). -} class Random a where - -- |Minimal complete definition: 'random' and 'randomR' - random :: RandomGen g => g -> (a, g) + -- | 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) - -- |Default methods - randoms :: RandomGen g => g -> [a] - randoms g = x : randoms g' where (x,g') = random 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 - randomIO :: IO a - randomIO = getStdRandom random + -- | 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 @@ -313,7 +343,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'' @@ -344,7 +378,7 @@ stdSplit std@(StdGen s1 s2) -- The global random number generator -{- $globalrng +{- $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 @@ -353,21 +387,21 @@ using the time of day, or Linux's kernel random number generator. To get deterministic behaviour, use 'setStdGen'. -} --- |'setStdGen' sets the global random number generator. +-- |Sets the global random number generator. setStdGen :: StdGen -> IO () setStdGen sgen = writeIORef theStdGen sgen --- |'getStdGen' gets the global random number generator. +-- |Gets the global random number generator. getStdGen :: IO StdGen getStdGen = readIORef theStdGen --- |'newStdGen' applies 'split' to the current global random generator, updates it --- with one of the results, and returns the other. 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 @@ -375,9 +409,10 @@ newStdGen = do setStdGen a return b -{- |'getStdRandom' 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: +{- |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)) @@ -393,19 +428,22 @@ 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 - +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 +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. -}