-- 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.
--
-----------------------------------------------------------------------------
-- $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
, setStdGen
, newStdGen
+ -- * Random values of various types
+ , Random ( random, randomR,
+ randoms, randomRs,
+ randomIO, randomRIO )
+
-- * References
-- $references
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'
* 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
instance RandomGen StdGen where
next = stdNext
split = stdSplit
+ genRange _ = stdRange
instance Show StdGen where
showsPrec p (StdGen s1 s2) =
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)
-- 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
-<http://www.haskell.org/onlinelibrary/random.html#global-rng>).
-}
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
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''
-- 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
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
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))
{- $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,
<http://random.mat.sbg.ac.at/~peter/pads98.ps>, 1998.
+5. Pierre #LEcuyer# L'Ecuyer, /Efficient and portable combined random
+number generators/, Comm ACM, 31(6), Jun 1988, pp742-749.
+
The Web site <http://random.mat.sbg.ac.at/> is a great source of information.
-}
projects / haskell-directory.git / blobdiff