On 09.02.2012 18:27, Duncan Coutts wrote:
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...
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].
This is very elegant trick! Ability to snapshot and restore generator is lost.
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.
There is another problem. Functions like `next' aren't meant to be used by humans. One have to thread state manually and this is tedious and error-prone. So PRNG should be wrapped into monad. Are `next'-like function needed at all? I'd expect that creation of generic and useful type class would be very nontrivial.