Re: Simple Random Integer Generation

On Thu, 01 Jun 2006 13:57:11 +1000, Ben wrote:

Haskell has flummoxed me yet again with a seemingly simple task!

I simply need a function that will generate a random integer between say 1 and 999.
Looks like there's a library for this, but can't make head nor tail of it (haha a Haskell joke).

http://www.haskell.org/onlinereport/random.html

Can anyone give me a simple answer to this?

I'll give it a go. The reason it's tricky to read (until you get the hang
of it) is that it uses classes to make itself more general. This is
probably unnecessary, given that very few people are going to create a new
instance of RandomGen.

# ---------------- The RandomGen class ------------------------
#
# class RandomGen g where
# genRange :: g -> (Int, Int)
# next :: g -> (Int, g)
# split :: g -> (g, g)
#
# ---------------- A standard instance of RandomGen -----------
# data StdGen = ... -- Abstract

OK. This basically introduces StdGen, the standard random number
generator "object". Its an instance of the RandomGen class just in case
anyone wants to implement a different random number generator.

If you have r :: StdGen then you can say:

(x, r2) = next r

This gives you a random Int x and a new StdGen r2. The 'next' function is
defined in the RandomGen class, and you can apply it to something of type
StdGen because StdGen is an instance of the RandomGen class:

# instance RandomGen StdGen where ...
# instance Read StdGen where ...
# instance Show StdGen where ...

This also says that you can convert a StdGen to and from a string, which
is there as a handy way to save the state of the generator.

# mkStdGen :: Int -> StdGen

This is the factory function for StdGen objects. Put in a seed, get out a
generator.

The reason that the 'next' function also returns a new random number
generator is that Haskell is a functional language, so no side effects
are allowed. In most languages the random number generator routine has
the hidden side effect of updating the state of the generator ready for
the next call. Haskell can't do that. So if you want to generate three
random numbers you need to say something like

let
(x1, r2) = next r
(x2, r3) = next r2
(x3, r4) = next r3

Which is obviously a clumsy way of doing the same thing. Hold on to that
thought; I'll come back to it later.

The other thing is that the random values (x1, x2, x3) are random
integers. To get something in the range (0,999) you would have to take
the modulus yourself, which is silly. There ought to be a library routine
built on this, and indeed there is.



# ---------------- The Random class ---------------------------
# 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

This is what you are actually looking for. Remember that StdGen is the
only instance of type RandomGen (unless you roll your own random number
generator). So you can substitute StdGen for 'g' in the types above and
get this:

randomR :: (a, a) -> StdGen -> (a, StdGen)
random :: StdGen -> (a, StdGen)

randomRs :: (a, a) -> StdGen -> [a]
randoms :: StdGen -> [a]

But remember that this is all inside *another* class declaration "Random".
So what this says is that any instance of Random can use these functions.
The instances of Random are:

# instance Random Integer where ...
# instance Random Float where ...
# instance Random Double where ...
# instance Random Bool where ...
# instance Random Char where ...

So for any of these types you can get a random range. You can get a
random integer with:

(x1, r2) = randomR (0,999) r

And you can get a random upper case character with

(c2, r3) = randomR ('A', 'Z') r2

You can even get a random bit with

(b3, r4) = randomR (False, True) r3

So far so good, but threading the random number state through your entire
program like this is painful, error prone, and generally destroys the nice
clean functional properties of your program.

One partial solution is the "split" function in the RandomGen class. It
takes one generator and gives you two generators back. This lets you say
something like this:

(r1, r2) = split r
x = foo r1

In this case we are passing r1 down into function foo, which does
something random with it and returns a result "x", and we can then take
"r2" as the random number generator for whatever comes next. Without
"split" we would have to write

(x, r2) = foo r1


But even this is often too clumsy, so you can do it the quick and dirty
way by putting the whole thing in the IO monad. This gives you a standard
global random number generator just like any other language. But because
its just like any other language it has to do it in the IO monad.

# ---------------- The global random generator ----------------
# newStdGen :: IO StdGen
# setStdGen :: StdGen -> IO ()
# getStdGen :: IO StdGen
# getStdRandom :: (StdGen -> (a, StdGen)) -> IO a

The most useful routine is getStdRandom. The argument to this is a
function. Compare the type of that function to that of 'random' and
'randomR'. They both fit in rather well. To get a random integer in the
IO monad you can say:

x <- getStdRandom $ randomR (1,999)

The 'randomR (1,999)' has type "StdGen -> (Int, StdGen)", so it fits
straight into the argument required by getStdRandom.

But only being able to do random numbers in this nice straightforward way
inside the IO monad is a bit of a pain. Some function deep inside your
code needs a random number, and suddenly you have to rewrite half your
program as IO actions instead of nice pure functions, or else have an
StdGen parameter tramp its way down there through all the higher level
functions. Something a bit purer is needed.

If you have read anything about Monads then you might have recognized the
pattern I gave above:

let
(x1, r2) = next r
(x2, r3) = next r2
(x3, r4) = next r3

The job of a monad is to abstract out this pattern, leaving the programmer
to write something like:

x1 <- random
x2 <- random
x3 <- random

Of course you can do this in the IO monad, but it would be better if
random numbers had their own little monad that specialised in random
computations. And it just so happens that such a monad exists. It lives
in the Debug.QuickCheck library, and it's called "Gen". And it does lots
of very useful things with random numbers. But that will have to be the
subject of another tutorial.

Paul.

--
----------------------------------
Paul Johnson <paul at cogito dot org dot uk>

You are trapped in a twisty maze of little standards, all different.

.

Relevant Pages

  • Better use of random number genator bits?
    ... If I have a random number generator creating random binary digits, ... and I want to construct a random integer between 0 and say 40, ... Also another way we know is to produce a 226 bit random number but the math ...
    (sci.math)
  • Re: random data in structure - checking for no double values
    ... (it is in fact a generator for numbers like in a lotto), ... is there a possibility to circumvent packing an array with the values ... void KnuthShuffle(int n, int* deck) ... generating a random integer between 1 and 45 is better (if ...
    (comp.lang.c)
  • Re: Anyone have any ideas on this one.....
    ... generator with for instance srand)). ... fact it is better to generate random integer from set ... to be zeroed first of course. ... results using two nested for loops. ...
    (comp.lang.c)
  • Help!! Random Integer Generator Algorithm
    ... I need a generator of random integer between 0 and 36. ... this generator cannot contain any float operation. ... srand48+lrand48 in GNU C Library. ...
    (comp.theory)
  • Re: Floating Point Random Number Generator
    ... > I know how to use randto generate random POSITIVE-INTEGER numbers. ... To generate such doubles, ... first generate a random integer in [0,2^52) and then divide it by 2^52. ... You need to use a long period generator such as a Mersenne twister to really ...
    (microsoft.public.dotnet.languages.vc)
Loading