X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=System%2FRandom.hs;h=8b648a73654a2b1087e54b985dece207be395de1;hb=a2a70b9bf60672c72b35654105402cf21238b6f4;hp=e3fa8b9c5613865608c44dad877ff5ed9b7c18e7;hpb=f7a485978f04e84b086f1974b88887cc72d832d0;p=haskell-directory.git diff --git a/System/Random.hs b/System/Random.hs index e3fa8b9..8b648a7 100644 --- a/System/Random.hs +++ b/System/Random.hs @@ -5,59 +5,158 @@ -- 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. -- ----------------------------------------------------------------------------- module System.Random ( + + -- $intro + + -- * Random number generators + RandomGen(next, split, genRange) + + -- ** Standard random number generators , StdGen , mkStdGen - , 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. + -- * Random values of various types + , Random ( random, randomR, + randoms, randomRs, + randomIO, randomRIO ) --- Transliterator: Lennart Augustsson + -- * References + -- $references --- 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 ) +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 - -#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 CTime -> IO CTime +getClockTime :: IO ClockTime +getClockTime = do CTime t <- readtime nullPtr; return (TOD (toInteger t) ()) #endif +-- | The class 'RandomGen' provides a common interface to random number +-- generators. +-- +-- Minimal complete definition: 'next' and 'split'. + 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' 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 '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 @@ -65,22 +164,13 @@ data StdGen instance RandomGen StdGen where next = stdNext split = stdSplit + genRange _ = stdRange -#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 +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) @@ -119,26 +214,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 +301,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 @@ -227,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'' @@ -256,16 +376,32 @@ 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 theStdGen :: IORef StdGen -theStdGen = unsafePerformIO (newIORef (createStdGen 0)) +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 @@ -273,9 +409,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. + +-}