%**<title>The Haskell 98 Library Report: Random Numbers</title>
%**~eheader
\section{Random Numbers}
\label{random numbers}

\outline {
\inputHS{headers/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
\indextt{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
\indextt{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'', Department of Mathematics,
University of Salzburg, @http://random.mat.sbg.ac.at/~peter/pads98.ps@, 1998.
\end{description}

The Web site @http://random.mat.sbg.ac.at/@ is a great source of information.


%**~efooter