Folks
Guess what? I have been driven to the conclusion that
the Haskell 98 Random library contains a fundamental, but
easily fixed flaw. So I propose to declare a new 'typo'.
(Yes, I am all too aware of the danger of typo-creep.)
The library is currently based on the RandomGen class,
whose signature is:
class RandomGen g wher
next :: g -> (Int, g)
split :: g -> (g, g)
The difficulty is that there is absolutely no robust way to
use such a generator to generate random numbers uniformly
distributed in a given range. Why not? Because there's no
clue as to the precise range of Ints produced by next.
Suppose next produced output in the range 0..16. (It's specified
to produce "at least 30 bits", but the argument still holds.)
Suppose we want random numbers in the range 0..10. We can't just
take "mod 11" because that would produce too many values in the
range 0..5. Indeed, if we don't know the range of next's result,
we simply cannot generate uniformly distributed random numbers.
The fix is simple.
=============== Start of fix =================
Add a further operation to RandomGen:
class RandomGen g where
next :: g -> (Int, g)
split :: g -> (g, g)
genRange :: g -> (Int,Int)
with the constraints that
a) If (a,b) = genRange g, then a < b
b) genRange (snd (next g)) = genRange g
genRange (fst (split g)) = genRange g
genRange (snd (split g)) = genRange g
c) The Int output of (next g) is equally likely to be any of
the Ints in the range (genRange g), including both end points.
In exchange, we can remove the current unsatisfactory sentence
that says that next must deliver "at least 30 bits".
================== End of fix ===================
I regret the need for this change. Does anyone object to it? More
particularly, can anyone think of a flaw?
Many thanks to Matt Harden, who is the one who identified the problem,
and proposed the solution.
Simon
