1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
|
<title>The Haskell 98 Library Report: Random Numbers</title>
<body bgcolor="#ffffff"> <i>The Haskell 98 Library Report</i><br> <a href="index.html">top</a> | <a href="cputime.html">back</a> | next | <a href="libindex.html">contents</a> <br><hr>
<a name="random numbers"></a><a name="sect17"></a>
<h2>17<tt> </tt>Random Numbers</h2>
<p>
<table border=2 cellpadding=3>
<tr><td>
<tt><br>
module Random (<br>
RandomGen(next, split),<br>
StdGen, mkStdGen,<br>
Random( random, randomR, <br>
randoms, randomRs,<br>
randomIO, randomRIO ),<br>
getStdRandom, getStdGen, setStdGen, newStdGen<br>
) where<br>
<br>
---------------- The RandomGen class ------------------------<br>
<br>
class RandomGen g where<br>
next :: g -> (Int, g)<br>
split :: g -> (g, g)<br>
<br>
---------------- A standard instance of RandomGen -----------<br>
data StdGen = ... -- Abstract<br>
<br>
instance RandomGen StdGen where ...<br>
instance Read StdGen where ...<br>
instance Show StdGen where ...<br>
<br>
mkStdGen :: Int -> StdGen<br>
<br>
---------------- The Random class ---------------------------<br>
class Random a where<br>
randomR :: RandomGen g => (a, a) -> g -> (a, g)<br>
random :: RandomGen g => g -> (a, g)<br>
<br>
randomRs :: RandomGen g => (a, a) -> g -> [a]<br>
randoms :: RandomGen g => g -> [a]<br>
<br>
randomRIO :: (a,a) -> IO a<br>
randomIO :: IO a<br>
<br>
instance Random Int where ...<br>
instance Random Integer where ...<br>
instance Random Float where ...<br>
instance Random Double where ...<br>
instance Random Bool where ...<br>
instance Random Char where ...<br>
<br>
---------------- The global random generator ----------------<br>
newStdGen :: IO StdGen<br>
setStdGen :: StdGen -> IO ()<br>
getStdGen :: IO StdGen <br>
getStdRandom :: (StdGen -> (a, StdGen)) -> IO a<br>
<br>
<br>
</tt></td></tr></table>
<p>
The <tt>Random</tt> 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.<p>
The library is split into two layers:
<UL><LI>A core <I>random number generator</I> provides a supply of bits.
The class <tt>RandomGen</tt> provides a common interface to such generators.<p>
<LI>The class <tt>Random</tt> provides a way to extract particular values from
a random number generator. For example, the <tt>Float</tt> instance of <tt>Random</tt>
allows one to generate random values of type <tt>Float</tt>.
</UL><p>
<a name="sect17.1"></a>
<h3>17.1<tt> </tt>The <tt>RandomGen</tt> class, and the <tt>StdGen</tt> generator</h3><p>
The class <tt>RandomGen</tt> provides a common interface to random number generators.
<tt><br>
<br>
class RandomGen g where<br>
next :: g -> (Int, g)<br>
split :: g -> (g, g)<br>
<br>
</tt><UL><LI>The <tt>next</tt> operation allows one to extract at least 30 bits (one <tt>Int</tt>'s worth)
from the generator, returning a new generator as well. The integer returned
may be positive or negative.<p>
<LI>The <tt>split</tt> 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 <tt>split
</tt>([1,4] are the only examples we know of).
</UL><p>
The <tt>Random</tt> library provides one instance of <tt>RandomGen</tt>, the abstract data
type <tt>StdGen</tt>:
<tt><br>
<br>
data StdGen = ... -- Abstract<br>
<br>
instance RandomGen StdGen where ...<br>
instance Read StdGen where ...<br>
instance Show StdGen where ...<br>
<br>
mkStdGen :: Int -> StdGen<br>
<br>
</tt>The result of repeatedly using <tt>next</tt> 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 <tt>split</tt>,
all we require is that <tt>split</tt> deliver generators that are (a) not identical
and (b) independently robust in the sense just given.<p>
The <tt>show</tt>/<tt>Read</tt> instances of <tt>StdGen</tt> provide a primitive way to save
the state of a random number generator.
It is required that <tt>read (show g) == g</tt>.<p>
In addition, <tt>read</tt> may be used to map an arbitrary string (not
necessarily one produced by <tt>show</tt>) onto a value of type <tt>StdGen</tt>.
In general, the <tt>read</tt> instance of <tt>StdGen</tt> has the following properties:
<UL><LI>It guarantees to succeed on any string.
<LI>It guarantees to consume only a finite portion of the string.
<LI>Different argument strings are likely to result in different results.
</UL><p>
The function <tt>mkStdGen</tt> provides an alternative way of producing an initial generator,
by mapping an <tt>Int</tt> into a generator. Again, distinct arguments should be likely
to produce distinct generators.<p>
Programmers may, of course, supply their own instances of <tt>RandomGen</tt>.<p>
<a name="sect17.2"></a>
<h3>17.2<tt> </tt>The <tt>Random</tt> class</h3><p>
With a source of random number supply in hand, the <tt>Random</tt> class allows
the programmer to extract random values of a variety of types:
<tt><br>
<br>
class Random a where<br>
randomR :: RandomGen g => (a, a) -> g -> (a, g)<br>
random :: RandomGen g => g -> (a, g)<br>
<br>
randomRs :: RandomGen g => (a, a) -> g -> [a]<br>
randoms :: RandomGen g => g -> [a]<br>
<br>
randomRIO :: (a,a) -> IO a<br>
randomIO :: IO a<br>
<br>
-- Default methods<br>
randoms g = x : randoms g' <br>
where <br>
(x,g') = random g<br>
randomRs = ...similar...<br>
<br>
randomIO = getStdRandom random<br>
randomRIO range = getStdRandom (randomR range)<br>
<br>
<br>
instance Random Int where ...<br>
instance Random Integer where ...<br>
instance Random Float where ...<br>
instance Random Double where ...<br>
instance Random Bool where ...<br>
instance Random Char where ...<br>
<br>
</tt><UL><LI><tt>randomR</tt> takes a range <I>(lo,hi)</I> and a random number generator <I>g</I>,
and returns a random value uniformly distributed in the closed interval <I>[lo,hi]</I>, together
with a new generator. It is unspecified what happens if <I>lo>hi</I>.
For continuous types there is no requirement that the values <I>lo</I> and <I>hi</I> are
ever produced, but they may be, depending on the implementation and the interval.<p>
<LI><tt>random</tt> does the same as <tt>randomR</tt>, but does not take a range.
<UL><LI>For bounded types (instances of <tt>Bounded</tt>, such as <tt>Char</tt>),
the range is normally the whole type.
<LI>For fractional types, the range is normally the semi-closed interval <I>[0,1)</I>.
<LI>For <tt>Integer</tt>, the range is (arbitrarily) the range of <tt>Int</tt>.
</UL><p>
<LI>The plural versions, <tt>randomRs</tt> and <tt>randoms</tt>, produce an infinite list of random
values, and do not return a new generator.<p>
<LI>The <tt>IO</tt> versions, <tt>randomRIO</tt> and <tt>randomIO</tt>, use the global random number
generator (see Section <a href="random.html#global-rng">17.3</a>).
</UL><a name="global-rng"></a><p>
<a name="sect17.3"></a>
<h3>17.3<tt> </tt>The global random number generator</h3>
<p>
There is a single, implicit, global random number generator
of type <tt>StdGen</tt>, held in some global variable maintained by the <tt>IO</tt> monad.
It is initialised automatically in some system-dependent fashion,
for example, by using the time of day, or Linux's kernal random number generator.
To get deterministic behaviour, use <tt>setStdGen</tt>.
<tt><br>
<br>
setStdGen :: StdGen -> IO () <br>
getStdGen :: IO StdGen <br>
newStdGen :: IO StdGen<br>
getStdRandom :: (StdGen -> (a, StdGen)) -> IO a<br>
<br>
</tt><UL><LI><tt>getStdGen</tt> and <tt>setStdGen</tt> get and set the global random
number generator, respectively.<p>
<LI><tt>newStdGen</tt> applies <tt>split</tt> to the current global random generator,
updates it with one of the results, and returns the other.<p>
<LI><tt>getStdRandom</tt> 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, <tt>rollDice</tt> gets a random integer between 1 and 6:
<tt><br>
<br>
rollDice :: IO Int<br>
rollDice = getStdRandom (randomR (1,6))<br>
<br>
</tt></UL> <p>
<h3>References</h3>
<DL><DT>
[1]
</DT>
FW Burton and RL Page, "Distributed random number generation",
Journal of Functional Programming, 2(2):203-212, April 1992.<p>
<DT>
[2]
</DT>
SK Park, and KW Miller, "Random number generators - good ones are hard to find",
Comm ACM 31(10), Oct 1988, pp1192-1201.<p>
<DT>
[3]
</DT>
DG Carta, "Two fast implementations of the minimal standard random number generator",
Comm ACM, 33(1), Jan 1990, pp87-88.<p>
<DT>
[4]
</DT>
P Hellekalek, "Don't trust parallel Monte Carlo", Department of Mathematics,
University of Salzburg, <tt>http://random.mat.sbg.ac.at/~peter/pads98.ps</tt>, 1998.
</DL><p>
The Web site <tt>http://random.mat.sbg.ac.at/</tt> is a great source of information.<p>
<hr><i>The Haskell 98 Library Report</i><br><a href="index.html">top</a> | <a href="cputime.html">back</a> | next | <a href="libindex.html">contents</a> <br><font size=2>1 February, 1999</font>
<p>
|
