%**The Haskell 98 Library Report: Random Numbers %**~header \section{Random Numbers} \label{random numbers} \outline { \inputHS{lib-hdrs/Random} } 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: \begin{itemize} \item A core {\em random number generator} provides a supply of bits. The class @RandomGen@ provides a common interface to such generators. \item 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@. \end{itemize} \subsection{The @RandomGen@ class, and the @StdGen@ generator} The class @RandomGen@ provides a common interface to random number generators. \bprog @ class RandomGen g where genRange :: g -> (Int,Int) next :: g -> (Int, g) split :: g -> (g, g) -- Default method genRange g = (minBound,maxBound) @ \eprog \indextt{next} \indextt{split} \indextt{genRange} \indextt{RandomGen} \begin{itemize} \item The @genRange@ operation yields the range of values returned by the generator. It is required that: \begin{itemize} \item If $(a,b) ~=~ @genRange@~ g$, then $a < b$. \item $@genRange@~\bot ~\neq~ \bot$. \end{itemize} 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@. \item The @next@ operation returns an @Int@ that is uniformly distributed in the range returned by @genRange@ (including both end points), and a new generator. \item The @split@ operation allows one to obtain two independent 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). \end{itemize} The @Random@ library provides one instance of @RandomGen@, the abstract data type @StdGen@: \bprog @ data StdGen = ... -- Abstract instance RandomGen StdGen where ... instance Read StdGen where ... instance Show StdGen where ... mkStdGen :: Int -> StdGen @ \eprog \indextycon{StdGen} \indextt{mkStdGen} The @StgGen@ 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 [2,3]. 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: \begin{itemize} \item It guarantees to succeed on any string. \item It guarantees to consume only a finite portion of the string. \item Different argument strings are likely to result in different results. \end{itemize} 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@. {\em Implementation warning.} A superficially attractive implementation of @split@ is \bprog @ instance RandomGen MyGen where ... split g = (g, variantOf g) @ \eprog Here, @split@ returns @g@ itself and a new generator derived from @g@. But now consider these two apparently-independent generators: \bprog @ g1 = snd (split g) g2 = snd (split (fst (split g))) @ \eprog If @split@ genuinely delivers independent generators (as specified), then @g1@ and @g2@ should be independent, but in fact they are both equal to @variantOf g@. Implementations of the above form do not meet the specification. \subsection{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: \bprog @ class Random a where randomR :: RandomGen g => (a, a) -> g -> (a, g) random :: RandomGen g => g -> (a, g) randomRs :: RandomGen g => (a, a) -> g -> [a] randoms :: RandomGen g => g -> [a] randomRIO :: (a,a) -> IO a randomIO :: IO a -- Default methods randoms g = x : randoms g' where (x,g') = random g randomRs = ...similar... randomIO = getStdRandom random randomRIO range = getStdRandom (randomR range) instance Random Int where ... instance Random Integer where ... instance Random Float where ... instance Random Double where ... instance Random Bool where ... instance Random Char where ... @ \eprog \indexclass{Random} \indextt{random} \indextt{randomR} \indextt{randoms} \indextt{randomRs} \indextt{randomIO} \indextt{randomRIO} \begin{itemize} \item @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. % \begin{itemize} % \item For discrete types (such as @Int@ or @Bool@), % ``uniformly distributed'' means that each value is equally likely to occur. % \item For floating-point types (instances of @Floating@, such as @Float@ or @Double@), % the probability of any particular (representable) value "v" % occurring is proportional to "ulp(v)/(h-l)", where "ulp(v)" is the % size of a unit change in the least significant bit position of "v". % \item For continuous types, such as @Rational@, ``uniformly distributed'' means % that the probability distribution of returned values is uniform over the interval. % \end{itemize} % \begin{itemize} % \item For discrete types (such as @Int@ or @Bool@), the range is the closed interval "[l,h]". % \item For fractional types (instances of @Fractional@, such as @Float@ or @Double@), % the range is the semi-closed interval "[l,h)". % \end{itemize} % for discrete types, or if "l \geq h" for fractional types. \item @random@ does the same as @randomR@, but does not take a range. \begin{itemize} \item For bounded types (instances of @Bounded@, such as @Char@), the range is normally the whole type. \item For fractional types, the range is normally the semi-closed interval "[0,1)". \item For @Integer@, the range is (arbitrarily) the range of @Int@. \end{itemize} \item The plural versions, @randomRs@ and @randoms@, produce an infinite list of random values, and do not return a new generator. \item The @IO@ versions, @randomRIO@ and @randomIO@, use the global random number generator (see Section~\ref{global-rng}). \end{itemize} \subsection{The global random number generator} \label{global-rng} 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@. \bprog @ setStdGen :: StdGen -> IO () getStdGen :: IO StdGen newStdGen :: IO StdGen getStdRandom :: (StdGen -> (a, StdGen)) -> IO a @ \eprog \indextt{setStdGen} \indextt{getStdGen} \indextt{newStdGen} \indextt{getStdRandom} \begin{itemize} \item @getStdGen@ and @setStdGen@ get and set the global random number generator, respectively. \item @newStdGen@ applies @split@ to the current global random generator, updates it with one of the results, and returns the other. \item @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: \bprog @ rollDice :: IO Int rollDice = getStdRandom (randomR (1,6)) @ \eprog \end{itemize} \subsection*{References} \begin{description} \item[{[1]}] FW Burton and RL Page, ``Distributed random number generation'', Journal of Functional Programming, 2(2):203-212, April 1992. \item[{[2]}] SK Park, and KW Miller, ``Random number generators - good ones are hard to find'', Comm ACM 31(10), Oct 1988, pp1192-1201. \item[{[3]}] DG Carta, ``Two fast implementations of the minimal standard random number generator'', Comm ACM, 33(1), Jan 1990, pp87-88. \item[{[4]}] P Hellekalek, ``Don't trust parallel Monte Carlo'', ACM SIGSIM Simulation Digest 28(1), pp82-89, July 1998. \end{description} The Web site @http://random.mat.sbg.ac.at/@ is a great source of information. %**~efooter