fix nhc98 build: recent change to use picoseconds was not portable
[packages/random.git] / System / Random.hs
1 -----------------------------------------------------------------------------
2 -- |
3 -- Module : System.Random
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
6 --
7 -- Maintainer : libraries@haskell.org
8 -- Stability : stable
9 -- Portability : portable
10 --
11 -- This library deals with the common task of pseudo-random number
12 -- generation. The library makes it possible to generate repeatable
13 -- results, by starting with a specified initial random number generator,
14 -- or to get different results on each run by using the system-initialised
15 -- generator or by supplying a seed from some other source.
16 --
17 -- The library is split into two layers:
18 --
19 -- * A core /random number generator/ provides a supply of bits.
20 -- The class 'RandomGen' provides a common interface to such generators.
21 -- The library provides one instance of 'RandomGen', the abstract
22 -- data type 'StdGen'. Programmers may, of course, supply their own
23 -- instances of 'RandomGen'.
24 --
25 -- * The class 'Random' provides a way to extract values of a particular
26 -- type from a random number generator. For example, the 'Float'
27 -- instance of 'Random' allows one to generate random values of type
28 -- 'Float'.
29 --
30 -- This implementation uses the Portable Combined Generator of L'Ecuyer
31 -- ["System.Random\#LEcuyer"] for 32-bit computers, transliterated by
32 -- Lennart Augustsson. It has a period of roughly 2.30584e18.
33 --
34 -----------------------------------------------------------------------------
35
36 module System.Random
37 (
38
39 -- $intro
40
41 -- * Random number generators
42
43 RandomGen(next, split, genRange)
44
45 -- ** Standard random number generators
46 , StdGen
47 , mkStdGen
48
49 -- ** The global random number generator
50
51 -- $globalrng
52
53 , getStdRandom
54 , getStdGen
55 , setStdGen
56 , newStdGen
57
58 -- * Random values of various types
59 , Random ( random, randomR,
60 randoms, randomRs,
61 randomIO, randomRIO )
62
63 -- * References
64 -- $references
65
66 ) where
67
68 import Prelude
69
70 import Data.Int
71
72 #ifdef __NHC__
73 import CPUTime ( getCPUTime )
74 import Foreign.Ptr ( Ptr, nullPtr )
75 import Foreign.C ( CTime, CUInt )
76 #else
77 import System.CPUTime ( getCPUTime )
78 import System.Time ( getClockTime, ClockTime(..) )
79 #endif
80 import Data.Char ( isSpace, chr, ord )
81 import System.IO.Unsafe ( unsafePerformIO )
82 import Data.IORef
83 import Numeric ( readDec )
84
85 -- The standard nhc98 implementation of Time.ClockTime does not match
86 -- the extended one expected in this module, so we lash-up a quick
87 -- replacement here.
88 #ifdef __NHC__
89 data ClockTime = TOD Integer Integer
90 foreign import ccall "time.h time" readtime :: Ptr CTime -> IO CTime
91 getClockTime :: IO ClockTime
92 getClockTime = do CTime t <- readtime nullPtr; return (TOD (toInteger t) 0)
93 #endif
94
95 -- | The class 'RandomGen' provides a common interface to random number
96 -- generators.
97 --
98 -- Minimal complete definition: 'next' and 'split'.
99
100 class RandomGen g where
101
102 -- |The 'next' operation returns an 'Int' that is uniformly distributed
103 -- in the range returned by 'genRange' (including both end points),
104 -- and a new generator.
105 next :: g -> (Int, g)
106
107 -- |The 'split' operation allows one to obtain two distinct random number
108 -- generators. This is very useful in functional programs (for example, when
109 -- passing a random number generator down to recursive calls), but very
110 -- little work has been done on statistically robust implementations of
111 -- 'split' (["System.Random\#Burton", "System.Random\#Hellekalek"]
112 -- are the only examples we know of).
113 split :: g -> (g, g)
114
115 -- |The 'genRange' operation yields the range of values returned by
116 -- the generator.
117 --
118 -- It is required that:
119 --
120 -- * If @(a,b) = 'genRange' g@, then @a < b@.
121 --
122 -- * 'genRange' always returns a pair of defined 'Int's.
123 --
124 -- The second condition ensures that 'genRange' cannot examine its
125 -- argument, and hence the value it returns can be determined only by the
126 -- instance of 'RandomGen'. That in turn allows an implementation to make
127 -- a single call to 'genRange' to establish a generator's range, without
128 -- being concerned that the generator returned by (say) 'next' might have
129 -- a different range to the generator passed to 'next'.
130 --
131 -- The default definition spans the full range of 'Int'.
132 genRange :: g -> (Int,Int)
133
134 -- default method
135 genRange g = (minBound,maxBound)
136
137 {- |
138 The 'StdGen' instance of 'RandomGen' has a 'genRange' of at least 30 bits.
139
140 The result of repeatedly using 'next' should be at least as statistically
141 robust as the /Minimal Standard Random Number Generator/ described by
142 ["System.Random\#Park", "System.Random\#Carta"].
143 Until more is known about implementations of 'split', all we require is
144 that 'split' deliver generators that are (a) not identical and
145 (b) independently robust in the sense just given.
146
147 The 'Show' and 'Read' instances of 'StdGen' provide a primitive way to save the
148 state of a random number generator.
149 It is required that @'read' ('show' g) == g@.
150
151 In addition, 'read' may be used to map an arbitrary string (not necessarily one
152 produced by 'show') onto a value of type 'StdGen'. In general, the 'read'
153 instance of 'StdGen' has the following properties:
154
155 * It guarantees to succeed on any string.
156
157 * It guarantees to consume only a finite portion of the string.
158
159 * Different argument strings are likely to result in different results.
160
161 -}
162
163 data StdGen
164 = StdGen Int32 Int32
165
166 instance RandomGen StdGen where
167 next = stdNext
168 split = stdSplit
169 genRange _ = stdRange
170
171 instance Show StdGen where
172 showsPrec p (StdGen s1 s2) =
173 showsPrec p s1 .
174 showChar ' ' .
175 showsPrec p s2
176
177 instance Read StdGen where
178 readsPrec _p = \ r ->
179 case try_read r of
180 r@[_] -> r
181 _ -> [stdFromString r] -- because it shouldn't ever fail.
182 where
183 try_read r = do
184 (s1, r1) <- readDec (dropWhile isSpace r)
185 (s2, r2) <- readDec (dropWhile isSpace r1)
186 return (StdGen s1 s2, r2)
187
188 {-
189 If we cannot unravel the StdGen from a string, create
190 one based on the string given.
191 -}
192 stdFromString :: String -> (StdGen, String)
193 stdFromString s = (mkStdGen num, rest)
194 where (cs, rest) = splitAt 6 s
195 num = foldl (\a x -> x + 3 * a) 1 (map ord cs)
196
197
198 {- |
199 The function 'mkStdGen' provides an alternative way of producing an initial
200 generator, by mapping an 'Int' into a generator. Again, distinct arguments
201 should be likely to produce distinct generators.
202 -}
203 mkStdGen :: Int -> StdGen -- why not Integer ?
204 mkStdGen s = mkStdGen32 $ fromIntegral s
205
206 mkStdGen32 :: Int32 -> StdGen
207 mkStdGen32 s
208 | s < 0 = mkStdGen32 (-s)
209 | otherwise = StdGen (s1+1) (s2+1)
210 where
211 (q, s1) = s `divMod` 2147483562
212 s2 = q `mod` 2147483398
213
214 createStdGen :: Integer -> StdGen
215 createStdGen s = mkStdGen32 $ fromIntegral s
216
217 -- FIXME: 1/2/3 below should be ** (vs@30082002) XXX
218
219 {- |
220 With a source of random number supply in hand, the 'Random' class allows the
221 programmer to extract random values of a variety of types.
222
223 Minimal complete definition: 'randomR' and 'random'.
224
225 -}
226
227 class Random a where
228 -- | Takes a range /(lo,hi)/ and a random number generator
229 -- /g/, and returns a random value uniformly distributed in the closed
230 -- interval /[lo,hi]/, together with a new generator. It is unspecified
231 -- what happens if /lo>hi/. For continuous types there is no requirement
232 -- that the values /lo/ and /hi/ are ever produced, but they may be,
233 -- depending on the implementation and the interval.
234 randomR :: RandomGen g => (a,a) -> g -> (a,g)
235
236 -- | The same as 'randomR', but using a default range determined by the type:
237 --
238 -- * For bounded types (instances of 'Bounded', such as 'Char'),
239 -- the range is normally the whole type.
240 --
241 -- * For fractional types, the range is normally the semi-closed interval
242 -- @[0,1)@.
243 --
244 -- * For 'Integer', the range is (arbitrarily) the range of 'Int'.
245 random :: RandomGen g => g -> (a, g)
246
247 -- | Plural variant of 'randomR', producing an infinite list of
248 -- random values instead of returning a new generator.
249 randomRs :: RandomGen g => (a,a) -> g -> [a]
250 randomRs ival g = x : randomRs ival g' where (x,g') = randomR ival g
251
252 -- | Plural variant of 'random', producing an infinite list of
253 -- random values instead of returning a new generator.
254 randoms :: RandomGen g => g -> [a]
255 randoms g = (\(x,g') -> x : randoms g') (random g)
256
257 -- | A variant of 'randomR' that uses the global random number generator
258 -- (see "System.Random#globalrng").
259 randomRIO :: (a,a) -> IO a
260 randomRIO range = getStdRandom (randomR range)
261
262 -- | A variant of 'random' that uses the global random number generator
263 -- (see "System.Random#globalrng").
264 randomIO :: IO a
265 randomIO = getStdRandom random
266
267
268 instance Random Int where
269 randomR (a,b) g = randomIvalInteger (toInteger a, toInteger b) g
270 random g = randomR (minBound,maxBound) g
271
272 instance Random Char where
273 randomR (a,b) g =
274 case (randomIvalInteger (toInteger (ord a), toInteger (ord b)) g) of
275 (x,g) -> (chr x, g)
276 random g = randomR (minBound,maxBound) g
277
278 instance Random Bool where
279 randomR (a,b) g =
280 case (randomIvalInteger (toInteger (bool2Int a), toInteger (bool2Int b)) g) of
281 (x, g) -> (int2Bool x, g)
282 where
283 bool2Int False = 0
284 bool2Int True = 1
285
286 int2Bool 0 = False
287 int2Bool _ = True
288
289 random g = randomR (minBound,maxBound) g
290
291 instance Random Integer where
292 randomR ival g = randomIvalInteger ival g
293 random g = randomR (toInteger (minBound::Int), toInteger (maxBound::Int)) g
294
295 instance Random Double where
296 randomR ival g = randomIvalDouble ival id g
297 random g = randomR (0::Double,1) g
298
299 -- hah, so you thought you were saving cycles by using Float?
300 instance Random Float where
301 random g = randomIvalDouble (0::Double,1) realToFrac g
302 randomR (a,b) g = randomIvalDouble (realToFrac a, realToFrac b) realToFrac g
303
304 mkStdRNG :: Integer -> IO StdGen
305 mkStdRNG o = do
306 ct <- getCPUTime
307 (TOD sec psec) <- getClockTime
308 return (createStdGen (sec * 12345 + psec + ct + o))
309
310 randomIvalInteger :: (RandomGen g, Num a) => (Integer, Integer) -> g -> (a, g)
311 randomIvalInteger (l,h) rng
312 | l > h = randomIvalInteger (h,l) rng
313 | otherwise = case (f n 1 rng) of (v, rng') -> (fromInteger (l + v `mod` k), rng')
314 where
315 k = h - l + 1
316 b = 2147483561
317 n = iLogBase b k
318
319 f 0 acc g = (acc, g)
320 f n acc g =
321 let
322 (x,g') = next g
323 in
324 f (n-1) (fromIntegral x + acc * b) g'
325
326 randomIvalDouble :: (RandomGen g, Fractional a) => (Double, Double) -> (Double -> a) -> g -> (a, g)
327 randomIvalDouble (l,h) fromDouble rng
328 | l > h = randomIvalDouble (h,l) fromDouble rng
329 | otherwise =
330 case (randomIvalInteger (toInteger (minBound::Int32), toInteger (maxBound::Int32)) rng) of
331 (x, rng') ->
332 let
333 scaled_x =
334 fromDouble ((l+h)/2) +
335 fromDouble ((h-l) / realToFrac int32Range) *
336 fromIntegral (x::Int32)
337 in
338 (scaled_x, rng')
339
340 int32Range :: Integer
341 int32Range = toInteger (maxBound::Int32) - toInteger (minBound::Int32)
342
343 iLogBase :: Integer -> Integer -> Integer
344 iLogBase b i = if i < b then 1 else 1 + iLogBase b (i `div` b)
345
346 stdRange :: (Int,Int)
347 stdRange = (0, 2147483562)
348
349 stdNext :: StdGen -> (Int, StdGen)
350 -- Returns values in the range stdRange
351 stdNext (StdGen s1 s2) = (fromIntegral z', StdGen s1'' s2'')
352 where z' = if z < 1 then z + 2147483562 else z
353 z = s1'' - s2''
354
355 k = s1 `quot` 53668
356 s1' = 40014 * (s1 - k * 53668) - k * 12211
357 s1'' = if s1' < 0 then s1' + 2147483563 else s1'
358
359 k' = s2 `quot` 52774
360 s2' = 40692 * (s2 - k' * 52774) - k' * 3791
361 s2'' = if s2' < 0 then s2' + 2147483399 else s2'
362
363 stdSplit :: StdGen -> (StdGen, StdGen)
364 stdSplit std@(StdGen s1 s2)
365 = (left, right)
366 where
367 -- no statistical foundation for this!
368 left = StdGen new_s1 t2
369 right = StdGen t1 new_s2
370
371 new_s1 | s1 == 2147483562 = 1
372 | otherwise = s1 + 1
373
374 new_s2 | s2 == 1 = 2147483398
375 | otherwise = s2 - 1
376
377 StdGen t1 t2 = snd (next std)
378
379 -- The global random number generator
380
381 {- $globalrng #globalrng#
382
383 There is a single, implicit, global random number generator of type
384 'StdGen', held in some global variable maintained by the 'IO' monad. It is
385 initialised automatically in some system-dependent fashion, for example, by
386 using the time of day, or Linux's kernel random number generator. To get
387 deterministic behaviour, use 'setStdGen'.
388 -}
389
390 -- |Sets the global random number generator.
391 setStdGen :: StdGen -> IO ()
392 setStdGen sgen = writeIORef theStdGen sgen
393
394 -- |Gets the global random number generator.
395 getStdGen :: IO StdGen
396 getStdGen = readIORef theStdGen
397
398 theStdGen :: IORef StdGen
399 theStdGen = unsafePerformIO $ do
400 rng <- mkStdRNG 0
401 newIORef rng
402
403 -- |Applies 'split' to the current global random generator,
404 -- updates it with one of the results, and returns the other.
405 newStdGen :: IO StdGen
406 newStdGen = atomicModifyIORef theStdGen split
407
408 {- |Uses the supplied function to get a value from the current global
409 random generator, and updates the global generator with the new generator
410 returned by the function. For example, @rollDice@ gets a random integer
411 between 1 and 6:
412
413 > rollDice :: IO Int
414 > rollDice = getStdRandom (randomR (1,6))
415
416 -}
417
418 getStdRandom :: (StdGen -> (a,StdGen)) -> IO a
419 getStdRandom f = atomicModifyIORef theStdGen (swap . f)
420 where swap (v,g) = (g,v)
421
422 {- $references
423
424 1. FW #Burton# Burton and RL Page, /Distributed random number generation/,
425 Journal of Functional Programming, 2(2):203-212, April 1992.
426
427 2. SK #Park# Park, and KW Miller, /Random number generators -
428 good ones are hard to find/, Comm ACM 31(10), Oct 1988, pp1192-1201.
429
430 3. DG #Carta# Carta, /Two fast implementations of the minimal standard
431 random number generator/, Comm ACM, 33(1), Jan 1990, pp87-88.
432
433 4. P #Hellekalek# Hellekalek, /Don\'t trust parallel Monte Carlo/,
434 Department of Mathematics, University of Salzburg,
435 <http://random.mat.sbg.ac.at/~peter/pads98.ps>, 1998.
436
437 5. Pierre #LEcuyer# L'Ecuyer, /Efficient and portable combined random
438 number generators/, Comm ACM, 31(6), Jun 1988, pp742-749.
439
440 The Web site <http://random.mat.sbg.ac.at/> is a great source of information.
441
442 -}