-----------------------------------------------------------------------------
---
+-- |
-- 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
+-- Stability : stable
-- Portability : portable
--
--- $Id: Random.hs,v 1.2 2001/12/21 15:07:26 simonmar Exp $
+-- 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'.
--
--- Random numbers.
+-- * 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 GHC.Read ( readDec )
-import GHC.IOBase ( unsafePerformIO, stToIO )
-import System.Time ( getClockTime, ClockTime(..) )
+import Numeric ( readDec )
+
+-- 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
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 ->
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)
(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.
--- The class definition - see library report for details.
+Minimal complete definition: 'randomR' and 'random'.
+
+-}
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
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
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''
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
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,
+<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