[Haskell-cafe] Mersenne-random and standard random API

[Duncan Coutts]

On 9 February 2012 10:59, Aleksey Khudyakov <alexey.skladnoy at gmail.com> wrote:

>> So is it possible to use the fast and efficient mersenne generator with
>> the convenient and general random API?
>>
> I think design of Random type class basically precludes efficient generators
> with large periods and consequently large state.
> Look at next function:
>
>> next :: g -> (Int, g)
>
> It means that state has to be copied but for efficiency we want to
> mutate it in place. I consider Random type class a failure and ignore
> it.

Actually it is not true that the state has to be copied. Using the
lazy ST monad we can implement this interface and internally use
mutable ST arrays.

See for example
http://web.archive.org/web/20090108050217/http://www.augustsson.net/Darcs/MT/MersenneTwister.hs

It ends up with this function that generates the infinite lazy
sequence of words from a seed word. This can be then made to fit the
next :: g -> (Int, g) interface, with g = [W].

mersenneTwister :: W -> [W]
mersenneTwister s = L.runST (mersenneTwisterST s)

For reference:

import Control.Monad.ST.Lazy as L
type W = Word32
mersenneTwisterST :: W -> L.ST s [W]

So yes this looses a small constant factor because of the extra lazy
list (which could be reduced somewhat), so it's not suitable for the
absolutely max performance interface, but it certainly allows the use
of traditional mutable PRNGs with the nice interface with decent
performance.

Certainly none of these PRNGs support split, but that's a separate
issue. Overall, I think the Random type class is salvageable given a
few changes. In the end, the Random module probably needs both an
ST-monadic interface and a pure one. People can use the ST one if it
happens to be more convenient or if they need to squeeze the last drop
of performance out.

Duncan