X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=System%2FRandom.hs;h=f9762df70199662dcfc0af5b49155ce807138a2c;hb=9c28b7a82656c693abdb179dab927bb8c2238ba1;hp=a6320a94f6a86b8e91a414330383e546f287ec34;hpb=b5545b3c2d5a32dca848a17a9f4f05c0eb82ff3a;p=ghc-base.git diff --git a/System/Random.hs b/System/Random.hs index a6320a9..f9762df 100644 --- a/System/Random.hs +++ b/System/Random.hs @@ -5,7 +5,7 @@ -- License : BSD-style (see the file libraries/base/LICENSE) -- -- Maintainer : libraries@haskell.org --- Stability : provisional +-- Stability : stable -- Portability : portable -- -- Random numbers. @@ -14,50 +14,147 @@ 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 - ) where --- 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. + -- * References + -- $references --- Transliterator: Lennart Augustsson - --- sof 1/99 - code brought (kicking and screaming) into the new Random --- world.. + ) where import Prelude +#ifdef __NHC__ +import CPUTime ( getCPUTime ) +import Foreign.Ptr ( Ptr, nullPtr ) +#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 - -#ifdef __GLASGOW_HASKELL__ -import GHC.Show ( showSignedInt, showSpace ) import Numeric ( readDec ) -import GHC.IOBase ( unsafePerformIO, stToIO ) -import System.Time ( getClockTime, ClockTime(..) ) + +-- 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 () -> IO Int +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'. + +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 mathod + -- 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 @@ -66,21 +163,11 @@ instance RandomGen StdGen where next = stdNext split = stdSplit -#ifdef __GLASGOW_HASKELL__ -instance Show StdGen where - showsPrec p (StdGen s1 s2) = - showSignedInt p s1 . - showSpace . - showSignedInt p s2 -#endif - -#ifdef __HUGS__ instance Show StdGen where showsPrec p (StdGen s1 s2) = showsPrec p s1 . showChar ' ' . showsPrec p s2 -#endif instance Read StdGen where readsPrec _p = \ r -> @@ -103,6 +190,13 @@ 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. + +Programmers may, of course, supply their own instances of 'RandomGen'. +-} mkStdGen :: Int -> StdGen -- why not Integer ? mkStdGen s | s < 0 = mkStdGen (-s) @@ -119,26 +213,56 @@ createStdGen s (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'. --- The class definition - see library report for details. +-} 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) - - 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 @@ -176,20 +300,11 @@ instance Random Float where random g = randomIvalDouble (0::Double,1) realToFrac g randomR (a,b) g = randomIvalDouble (realToFrac a, realToFrac b) realToFrac g -#ifdef __GLASGOW_HASKELL__ mkStdRNG :: Integer -> IO StdGen mkStdRNG o = do ct <- getCPUTime (TOD sec _) <- getClockTime return (createStdGen (sec * 12345 + ct + o)) -#endif - -#ifdef __HUGS__ -mkStdRNG :: Integer -> IO StdGen -mkStdRNG o = do - ct <- getCPUTime - return (createStdGen (ct + o)) -#endif randomIvalInteger :: (RandomGen g, Num a) => (Integer, Integer) -> g -> (a, g) randomIvalInteger (l,h) rng @@ -256,10 +371,22 @@ stdSplit std@(StdGen s1 s2) 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 @@ -268,6 +395,8 @@ 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 @@ -275,9 +404,41 @@ newStdGen = do 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, +, 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. + +-}