George Russell wrote:
>
> Matt Harden wrote:
> > I don't think that's really true. If I understand it correctly, the
> > state can be any type; it doesn't have to fit in, say, an Int or other
> > small type. I think the Mersenne Twister could be implemented as an
> > instance of Random.RandomGen. The only thing is I don't really know the
> > best way to implement "split" for MT.
> Well yes you can implement MT using the Haskell Random's
> existing framework, but since the "next" function,
> which steps the generator, has type
> next :: g -> (Int,g)
> the compiler must either
> (1) update the entire state persistently, which probably
> means some horrid hack with trees, if you don't want
> to have to copy arrays around
> or
> (2) do static analysis to detect that (as in most cases)
> the generator is not being replicated, so you don't
> need persistence. I think the "Haskell Way", which
> is better, is instead to enforce single-threading via
> some kind of monad.
> Actually I would argue that this is a rare case where persistence is
> not only not wanted but dangerous. If you have old copies of the state
> hanging around they may get accidentally used so that you have the same
> non-random numbers occurring again. You do _sometimes_ want to set and
> unset the seed, perhaps once per program, but it is surely better to
> have explicit copying only in this case.
> [snip[
> > Yes, and the current interface provides randomIO and randomRIO for those
> > who don't want to have to pass the RandomGen instance around. The cost
> > is they have to use the IO monad.
> True, but a conformant implementation has to implement randomIO and randomRIO
> using the same type of state (see section 17.3 of the library standard) and
> so they will suffer from the same disadvantages. Also the interface I suggest
> is superior because it allows more than one random number generator. (You
> might for example have an independent part of the program which relies on
> having its own personal deterministic reseedable generator.)
I see your point, if you assume the MT is implemented in terms of
Haskell arrays. Although MT is "defined" in terms of mutable arrays
(the C code uses them), my particular implementation uses "infinite"
lazy lists instead. Also, even if MT is implemented with Haskell
arrays, the array itself is only rebuilt once every 624 longwords, and
that's the only time the array has to be copied. The state would just
be a reference to the array, and an integer pointing to the current
location in the array. When the array is recreated, a "smart" compiler
would realize that the old array is no longer needed, and would produce
code to update the array in place. A not-so-smart compiler would simply
collect the old arrays with the GC when they were no longer referenced.
I don't see how an old copy of the state could "accidentally" get used.
If you pass the same state or "seed" to two parallel routines, then of
course they would get the same random numbers, and that may have been
what you intended. You can't protect the programmer from his own bad
code. The compiler would not accidentally use some old version of the
state, unless it was a very brain dead compiler. If you want two
different random streams from the same seed, you are supposed to use
split().
Btw, I agree that if you have a RNG for which the state is large and
changes with each call to next(), then you can end up with a very
inefficient implementation in the current random framework. The
Mersenne Twister doesn't happen to fit that profile.
If you force all uses of random numbers to be done in a special monad
(or IO), you *might* make the situation better in those cases, but that
comes at a cost. I feel that if the monad is IO, that cost is too
high. If the monad is not IO, and gives you access to get/set the state
and run with multiple random streams, then it's equivalent to what we
have now, so I wouldn't argue too loudly against that.
Yes, your suggested interface allows more than one RNG, but then so does
the current system. There's nothing superior about your interface from
that perspective.
