More small changes to
[haskell-report.git] / report / random.verb
1 %**<title>The Haskell 98 Library Report: Random Numbers</title>
2 %**~header
3 \section{Random Numbers}
4 \label{random numbers}
5
6 \outline {
7 \inputHS{lib-hdrs/Random}
8 }
9
10 The @Random@ library deals with the common task of 
11 pseudo-random number generation.  The library makes it possible to
12 generate repeatable results, by starting with a specified initial
13 random number generator; or to get different results on each run
14 by using the system-initialised generator, or by supplying a seed
15 from some other source.
16
17 The library is split into two layers:
18 \begin{itemize}
19 \item A core {\em random number generator} provides a supply of bits.
20 The class @RandomGen@ provides a common interface to such generators.
21
22 \item The class @Random@ provides a way to extract particular values from
23 a random number generator.  For example, the @Float@ instance of @Random@ 
24 allows one to generate random values of type @Float@.
25 \end{itemize}
26
27 \subsection{The @RandomGen@ class, and the @StdGen@ generator}
28
29 The class @RandomGen@ provides a common interface to random number generators.
30 \bprog
31 @
32   class RandomGen g where
33     genRange :: g -> (Int,Int)
34     next     :: g  -> (Int, g)
35     split    :: g -> (g, g)
36   
37     -- Default method
38     genRange g = (minBound,maxBound)
39 @
40 \eprog
41 \indextt{next}
42 \indextt{split}
43 \indextt{genRange}
44 \indextt{RandomGen}
45 \begin{itemize}
46 \item The @genRange@ operation yields the range of values returned by
47 the generator. 
48
49 It is required that:
50 \begin{itemize}
51 \item If $(a,b) ~=~ @genRange@~ g$, then $a < b$.
52 \item $@genRange@~\bot ~\neq~ \bot$.  
53 \end{itemize}
54 The second condition ensures that @genRange@ cannot examine its
55 argument, and hence the value it returns can be determined only by the
56 instance of @RandomGen@.  That in turn allows an implementation to make
57 a single call to @genRange@ to establish a generator's range, without
58 being concerned that the generator returned by (say) @next@ might have a different
59 range to the generator passed to @next@.
60
61 \item The @next@ operation returns an @Int@ that is uniformly distributed
62 in the range returned by @genRange@ (including both end points), and a new
63 generator.
64
65 \item The @split@ operation allows one to obtain two independent random number
66 generators.  This is very useful in functional programs (for example, when
67 passing a random number generator down to recursive calls), but very little work
68 has been done on statistically robust implementations of @split@
69 ([1,4] are the only examples we know of).
70 \end{itemize}
71
72 The @Random@ library provides one instance of @RandomGen@, the abstract data
73 type @StdGen@:
74 \bprog
75 @
76   data StdGen = ...     -- Abstract
77   
78   instance RandomGen StdGen where ...
79   instance Read      StdGen where ...
80   instance Show      StdGen where ...
81   
82   mkStdGen :: Int -> StdGen
83 @
84 \eprog
85 \indextycon{StdGen}
86 \indextt{mkStdGen}
87 The @StgGen@ instance of @RandomGen@ has a @genRange@ of at least 30 bits.
88
89 The result of repeatedly using @next@ should be at least as
90 statistically robust as the ``Minimal Standard Random Number Generator''
91 described by [2,3].  Until more is known about implementations of @split@,
92 all we require is that @split@ deliver generators that are (a) not identical
93 and (b) independently robust in the sense just given.
94
95 The @Show@/@Read@ instances of @StdGen@ provide a primitive way to save
96 the state of a random number generator.
97 It is required that @read (show g) == g@.
98
99 In addition, @read@ may be used to map an arbitrary string (not
100 necessarily one produced by @show@) onto a value of type @StdGen@.
101 In general, the @read@ instance of @StdGen@ has the following properties:
102 \begin{itemize}
103 \item It guarantees to succeed on any string.
104 \item It guarantees to consume only a finite portion of the string.
105 \item Different argument strings are likely to result in different results.
106 \end{itemize}
107
108 The function @mkStdGen@ provides an alternative way of producing an initial generator,
109 by mapping an @Int@ into a generator.  Again, distinct arguments should be likely
110 to produce distinct generators.
111
112 Programmers may, of course, supply their own instances of @RandomGen@.
113
114 {\em Implementation warning.}  A superficially attractive implementation of @split@ is
115 \bprog
116 @
117   instance RandomGen MyGen where
118     ...
119     split g = (g, variantOf g)
120 @
121 \eprog
122 Here, @split@ returns @g@ itself and a new generator derived from @g@.
123 But now consider these two apparently-independent generators:
124 \bprog
125 @
126   g1 = snd (split g)
127   g2 = snd (split (fst (split g)))
128 @
129 \eprog
130 If @split@ genuinely delivers independent generators (as specified), then @g1@ and
131 @g2@ should be independent, but in fact they are both equal to @variantOf g@.
132 Implementations of the above form do not meet the specification.
133
134 \subsection{The @Random@ class}
135
136 With a source of random number supply in hand, the @Random@ class allows
137 the programmer to extract random values of a variety of types:
138 \bprog
139 @
140 class Random a where
141    randomR :: RandomGen g => (a, a) -> g -> (a, g)
142    random  :: RandomGen g => g -> (a, g)
143
144    randomRs :: RandomGen g => (a, a) -> g -> [a]
145    randoms  :: RandomGen g => g -> [a]
146
147    randomRIO :: (a,a) -> IO a
148    randomIO :: IO a
149
150      -- Default methods
151    randoms g = x : randoms g' 
152                    where 
153                      (x,g') = random g
154    randomRs = ...similar...
155
156    randomIO        = getStdRandom random
157    randomRIO range = getStdRandom (randomR range)
158
159
160 instance Random Int     where ...
161 instance Random Integer where ...
162 instance Random Float   where ...
163 instance Random Double  where ...
164 instance Random Bool    where ...
165 instance Random Char    where ...
166 @
167 \eprog
168 \indexclass{Random}
169 \indextt{random}
170 \indextt{randomR}
171 \indextt{randoms}
172 \indextt{randomRs}
173 \indextt{randomIO}
174 \indextt{randomRIO}
175 \begin{itemize}
176 \item @randomR@ takes a range "(lo,hi)" and a random number generator "g",
177 and returns a random value uniformly distributed in the closed interval "[lo,hi]", together
178 with a new generator.  It is unspecified what happens if "lo>hi".
179 For continuous types there is no requirement that the values "lo" and "hi" are
180 ever produced, but they may be, depending on the implementation and the interval.
181
182 % \begin{itemize}
183 % \item For discrete types (such as @Int@ or @Bool@), 
184 % ``uniformly distributed'' means that each value is equally likely to occur.
185 % \item For floating-point types (instances of @Floating@, such as @Float@ or @Double@),
186 % the probability of any particular (representable) value "v"
187 % occurring is proportional to "ulp(v)/(h-l)", where "ulp(v)" is the
188 % size of a unit change in the least significant bit position of "v".
189 % \item For continuous types, such as @Rational@, ``uniformly distributed'' means
190 % that the probability distribution of returned values is uniform over the interval.
191 % \end{itemize}
192
193 % \begin{itemize}
194 % \item For discrete types (such as @Int@ or @Bool@), the range is the closed interval "[l,h]".
195 % \item For fractional types (instances of @Fractional@, such as @Float@ or @Double@),
196 % the range is the semi-closed interval "[l,h)".
197 % \end{itemize}
198 % for discrete types, or if "l \geq h" for fractional types.
199
200 \item @random@ does the same as @randomR@, but does not take a range.
201 \begin{itemize}
202 \item For bounded types (instances of @Bounded@, such as @Char@), 
203 the range is normally the whole type.
204 \item For fractional types, the range is normally the semi-closed interval "[0,1)".
205 \item For @Integer@, the range is (arbitrarily) the range of @Int@.
206 \end{itemize}
207
208 \item The plural versions, @randomRs@ and @randoms@, produce an infinite list of random
209 values, and do not return a new generator.
210
211 \item The @IO@ versions, @randomRIO@ and @randomIO@, use the global random number
212 generator (see Section~\ref{global-rng}).
213 \end{itemize}
214
215 \subsection{The global random number generator}
216 \label{global-rng}
217
218 There is a single, implicit, global random number generator
219 of type @StdGen@, held in some global variable maintained by the @IO@ monad.
220 It is initialised automatically in some system-dependent fashion,
221 for example, by using the time of day, or Linux's kernel random number generator.
222 To get deterministic behaviour, use @setStdGen@.
223 \bprog
224 @
225   setStdGen    :: StdGen -> IO ()       
226   getStdGen    :: IO StdGen             
227   newStdGen    :: IO StdGen
228   getStdRandom :: (StdGen -> (a, StdGen)) -> IO a
229 @
230 \eprog
231 \indextt{setStdGen}
232 \indextt{getStdGen}
233 \indextt{newStdGen}
234 \indextt{getStdRandom}
235 \begin{itemize}
236 \item @getStdGen@ and @setStdGen@ get and set the global random
237 number generator, respectively.
238
239 \item @newStdGen@ applies @split@ to the current global random generator,
240 updates it with one of the results, and returns the other.
241
242 \item @getStdRandom@ uses the supplied function to get a value from
243 the current global random generator, and updates the
244 global generator with the new generator returned by the function.
245 For example, @rollDice@ gets a random integer between 1 and 6:
246 \bprog
247 @
248   rollDice :: IO Int
249   rollDice = getStdRandom (randomR (1,6))
250 @
251 \eprog
252 \end{itemize}    
253
254 \subsection*{References}
255 \begin{description}
256 \item[{[1]}] FW Burton and RL Page, ``Distributed random number generation'',
257         Journal of Functional Programming, 2(2):203-212, April 1992.
258
259 \item[{[2]}] SK Park, and KW Miller, ``Random number generators - good ones are hard to find'',
260         Comm ACM 31(10), Oct 1988, pp1192-1201.
261
262 \item[{[3]}] DG Carta, ``Two fast implementations of the minimal standard random number generator'',
263         Comm ACM, 33(1), Jan 1990, pp87-88.
264
265 \item[{[4]}] P Hellekalek, ``Don't trust parallel Monte Carlo'', 
266 ACM SIGSIM Simulation Digest 28(1), pp82-89, July 1998.
267 \end{description}
268
269 The Web site @http://random.mat.sbg.ac.at/@ is a great source of information.
270
271
272 %**~efooter
273