[Haskell-cafe] Mersenne-random and standard random API
duncan.coutts at googlemail.com
Thu Feb 9 15:27:45 CET 2012
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
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
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)
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
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.
More information about the Haskell-Cafe