X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=System%2FRandom.hs;h=32ab0ae5a49288325b66a6a08b5327ef60ec0051;hb=997d903a5061d2eb60fea2ec12ef65392546a352;hp=59ff30066b65f965b9cf8a19096c60ee793ec441;hpb=9fa9bc17072a58c0bae2cce4764d38677e96ac29;p=ghc-base.git diff --git a/System/Random.hs b/System/Random.hs index 59ff300..32ab0ae 100644 --- a/System/Random.hs +++ b/System/Random.hs @@ -2,41 +2,45 @@ -- | -- Module : System.Random -- Copyright : (c) The University of Glasgow 2001 --- License : BSD-style (see the file libraries/core/LICENSE) +-- License : BSD-style (see the file libraries/base/LICENSE) -- -- Maintainer : libraries@haskell.org -- Stability : provisional -- Portability : portable -- --- $Id: Random.hs,v 1.4 2002/04/24 16:31:45 simonmar Exp $ --- -- Random numbers. -- ----------------------------------------------------------------------------- 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. --- Transliterator: Lennart Augustsson + -- * References + -- $references --- sof 1/99 - code brought (kicking and screaming) into the new Random --- world.. + ) where import Prelude @@ -44,22 +48,95 @@ import System.CPUTime ( getCPUTime ) import Data.Char ( isSpace, chr, ord ) import System.IO.Unsafe ( unsafePerformIO ) import Data.IORef +import Numeric ( readDec ) #ifdef __GLASGOW_HASKELL__ import GHC.Show ( showSignedInt, showSpace ) -import Numeric ( readDec ) import GHC.IOBase ( unsafePerformIO, stToIO ) import System.Time ( getClockTime, ClockTime(..) ) #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. + 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. 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 :: g -> (g, g) + genRange :: g -> (Int,Int) -- default mathod genRange g = (minBound,maxBound) +{- |The "Random" library provides one instance of 'RandomGen', the abstract data +type 'StdGen'. + +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@. + +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. + +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 = StdGen Int Int @@ -121,14 +198,41 @@ createStdGen s (q, s1) = s `divMod` 2147483562 s2 = q `mod` 2147483398 +-- 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. --- The class definition - see library report for details. +* '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'. + +* 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 + -- |Minimal complete definition: 'random' and 'randomR' random :: RandomGen g => g -> (a, g) 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 @@ -258,15 +362,31 @@ stdSplit std@(StdGen s1 s2) StdGen t1 t2 = snd (next std) +-- The global random number generator +{- $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'. +-} + +-- |'setStdGen' sets the global random number generator. setStdGen :: StdGen -> IO () setStdGen sgen = writeIORef theStdGen sgen +-- |'getStdGen' 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 (newIORef (createStdGen 0)) +theStdGen = unsafePerformIO $ do + rng <- mkStdRNG 0 + newIORef rng newStdGen :: IO StdGen newStdGen = do @@ -275,9 +395,37 @@ 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: + +> 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 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, /Don\'t trust parallel Monte Carlo/, +Department of Mathematics, University of Salzburg, +, 1998. + +The Web site is a great source of information. + +-}