-----------------------------------------------------------------------------
---
+-- |
-- 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.3 2002/04/11 12:03:44 simonpj 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.
+ -- * 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'.
+
+[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 "System.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
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 ->
(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.
+
+* 'random' does the same as 'randomR', but does not take a range.
--- The class definition - see library report for details.
+(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
+<http://www.haskell.org/onlinelibrary/random.html#global-rng>).
+-}
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
+ randoms g = (\(x,g') -> x : randoms g') (random g)
randomRs :: RandomGen g => (a,a) -> g -> [a]
randomRs ival g = x : randomRs ival g' where (x,g') = randomR ival 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
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
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,
+<http://random.mat.sbg.ac.at/~peter/pads98.ps>, 1998.
+
+The Web site <http://random.mat.sbg.ac.at/> is a great source of information.
+
+-}