Future of splittable PRNG and infinite structures support

[jmcarthur]

The direction of the random package in recent releases emphasizes using StatefulGen instances with strict monads. This has led to several API changes:

• Deprecation of RandomGenM
• Deprecation of the split function in RandomGen
• Introduction of the SplitGen class, which cannot be utilized in Random instances (with Random itself being discouraged)
• Recommendation to use Uniform and UniformRange, which are restricted to finite value generation and do not leverage splittable PRNGs

I understand that most PRNGs are not splittable, and it is sensible to optimize the API around this common scenario. The current direction makes considerable sense for these typical use cases. However, I am concerned about the diminished support for use cases involving splittable PRNGs.

My specific context: I'm developing a package that needs to generate infinite data structures lazily. Previously, this could have been neatly handled via type class instances. With the current changes, generating infinite structures requires standalone functions. Additionally, my package employs a QuickCheck-style monad for lazy generation. While it's not impossible to implement with StatefulGen, the FrozenGen abstraction feels significantly less elegant than the deprecated RandomGenM in this scenario.

My impression is that these design choices were made with full awareness of the trade-offs involved. However, I haven't found issues or design documents explicitly addressing these decisions. I'm opening this issue primarily for clarity: if the current direction is fully intentional, documenting the rationale here will help others who encounter similar questions. Alternatively, if there is a broader plan to support lazy and infinite random value generation alongside monadic contexts, having that plan documented would be beneficial.

[idontgetoutmuch]

It's a long time ago but one of the reasons for doing this work was that split as implemented did not give very "random" results. There was a lot of discussion:

• The seeds generated by split are not independent #25
• Hierarchical classes Splittable/Unsplittable Gen idontgetoutmuch/random#7

I can't add much more as I have been out of the Haskell loop for some time.

[jmcarthur]

I was aware of the poor behavior of StdGen back then, but wasn't it fixed by switching the implementation to to splitmix? From #62: "The split operation in splitmix showed no weakness in our tests. As a result, we replaced the pseudo-random number generator implementation in random by the one provided by splitmix."

It sounds like the current approach stakes a lot on the fact that RandomGen still has split, even though it's deprecated. From #160: "The benefit of this approach is that current user code does not break and gives a graceful path to upgrade to the new type class." Well, yeah, it doesn't break because the old split function is still there. Breakage will happen once that's gone. That's normal for a deprecation process, but what's less normal is that I don't see what the upgrade path is.

[jmcarthur]

One thought: Maybe the way forward is to add an associated constraint to Random so that each Random instance gets to control whether RandomGen or SplitGen (or other?) is needed.

[lehins]

The direction of the random package in recent releases emphasizes using StatefulGen instances with strict monads

Current API emphasizes that by using stateful API a user will be able to use more pseudo random number generators. For example it is possible to use functions like uniformM or uniformRM with mwc-random and even within QuickCheck Gen monad, which is not possible directly with RandomGen interface.
That being said, if one wants to use StdGen or some other immutable generator, there is nothing wrong with using uniform or uniformR instead.

Deprecation of RandomGenM

This deprecation is not related to stateful vs pure, it was deprecated because it was a more complex approach than using an existing FrozenGen.

FrozenGen abstraction feels significantly less elegant than the deprecated RandomGenM in this scenario.

FrozenGen is more powerful than RandomeGenM:

applyRandomGenM :: (r -> (a, r)) -> g -> m a

vs

modifyGen :: MutableGen f m -> (f -> (a, f)) -> m a

Difference in this subjective "elegance" comes from the fact that RandomGenM uses functional dependencies, while FrozenGen uses a type family. So, other than the order of arguments these two functions are equivalent. Besides that FrozenGen has another capability of converting mutable to frozen generator with feezeGen, which RandomGenM lacks.

Deprecation of the split function in RandomGen

This was a very much desired feature, because only a handful generators are splittable and majority of generators implemented it using error. Therefore introduction of SplitGen makes the interface more type safe. This change too is unrelated to stateful vs pure.

Introduction of the SplitGen class, which cannot be utilized in Random instances

I honestly didn't think about Random when introducing SplitGen type class. Random in general is not a really good type class to use. The only reason why it was not (and probably never will be) deprecated in favor of Uniform and UniformRange is because it has been around for something like 3 decades and a lot of code in the wild relies on it. A great example why Random is bad it's instances for types like Integer or Float/Double. It is not really random when you select a small range of all of the available values to pick from.

These are just my comments on your points that you brought up about stateful interface and introduction of SplitGen.

With respect to inability of using splittable generators in Uniform and UniformRange is certainly a valid point and it is indeed an unfortunate limitation. Initial focus when we started random overhaul was on three points:

• Fixing issues with performance, thus lazy and splittable generators were secondary concerns.
• Adding monadic interface that would be usable for both pure and stateful generators (StatefulGen vs RandomGen)
• Improving correctness of value generation (i.e Uniform and UniformRange vs Random)

I think we succeeded on all points. Now question is what can we do about improving the story for splittable and lazy generators. Despite that lazy generators naturally come with penalty to performance when comparing to strict generators, they are useful in their own right.

Your idea to "add an associated constraint to Random" would work in theory, however it would be a massive breaking change for downstream users. Anyone who had ever used Random type class would be broken by this approach due to a missing constraint. For example change like this:

class Random a where
  type AssGen a g :: Constraint
  type AssGen a g = ()
  randomR :: (AssGen a g, RandomGen g) => (a, a) -> g -> (a, g)
  random  :: (AssGen a g, RandomGen g) => g -> (a, g)
  ...

would lead to anyone using any function from Random today would start getting this kind of type error:

    • Could not deduce (AssGen e g) arising from a use of ‘random’

I honestly don't think we need to waste effort on improving Random, since, as mentioned earlier, it is an incorrect interface and is kept around solely for backwards compatibility.

... doesn't break because the old split function is still there. Breakage will happen once that's gone.

There are no plans on removing split, so it is still possible to continue using it with Random. Maybe we should replace DERPECATED with WARNING, to emphasize its partiality and promote usage of SplitGen instead.

That being said, I would love to solve this issue properly for Uniform and UniformRange.
I haven't thought about it in too much detail, but from usability perspective, I believe the best way forward would be to create a separate lazy module with the same interface as strict, similarly to how it is done in many libraries (eg, bytestring, text, containers, etc.). This would involve addition of lazy variants Uniform and UniformRange that would be split capable, eg:

class UniformLazy a where
  uniformLazyM :: (SplitGen f, FrozenGen f m) => MutableGen f m -> m a
  default uniformLazyM :: (Uniform a, SplitGen f, FrozenGen f m) => MutableGen f m -> m a
  uniformLazyM g = fst . uniform <$> splitGenM g

class UniformRangeLazy a where
  uniformLazyRM :: (SplitGen f, FrozenGen f m) => (a, a) -> MutableGen f m -> m a
  default uniformLazyRM :: (UniformRange a, SplitGen f, FrozenGen f m) => (a, a) -> MutableGen f m -> m a
  uniformLazyRM r g = fst . uniformR r <$> splitGenM g

We'd also need to add lazy variants of all generators: StateGen, AtomicGen, etc.
Naturally this would result in quite a bit of work and some duplication, but it would give full power of laziness to splittable generators:

λ> (res :: [Int], newGen) = runLazyStateGen (mkStdGen 1234) (replicateM maxBound . uniformLazyM)
λ> take 10 res
[-1456589047846719235,-1864319212160933848,2729596810608909097,3421538474897665715,2011114786220377274,9062864965255987894,-8206543229573612062,-9167618825787840756,-5946320430173711477,-2112880982125910862]

Thoughts, suggestions, critiques?