Future of splittable PRNG and infinite structures support #188

Activity

1. idontgetoutmuch commented on Jun 30, 2025

   

   idontgetoutmuch

   on Jun 30, 2025

   Member

   More actions

   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.
2. jmcarthur commented on Jul 4, 2025

   

   jmcarthur

   on Jul 4, 2025

   Author

   More actions

   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.
3. jmcarthur commented on Jul 4, 2025

   

   jmcarthur

   on Jul 4, 2025

   Last edited by jmcarthur

   Author

   More actions

   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.
4. lehins commented on Jul 4, 2025

   

   lehins

   on Jul 4, 2025

   Contributor

   More actions

   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?