Stateful generator application is sometimes too strict

[treeowl]

We certainly want generator application to modify the generator strictly, but it's not always reasonable to produce the result strictly. I think applyRandomGenM itself probably shouldn't force the result, but there should be a strict function based on it for implementing, e.g., uniformWord32R. For most RandomGenM instances, the change is trivial. For AtomicGenM, we'd need a half-strict version of atomicModifyIORef. For all vaguely recent GHC versions, it would look like this:

import GHC.IORef (atomicModifyIORef2)

atomicModifyIORefHS :: IORef a -> (a -> (a,b)) -> IO b
atomicModifyIORefHS ref f = do
  (_old, (_new, res)) <- atomicModifyIORef2 ref $
    \old -> case f old of
       r@(!_new, _res) -> r
  pure res

It's also possible to implement for older versions, but a bit less efficiently.

[lehins]

This is only really applicable for generating some basic types in the full range, because in many cases without forcing the new value you cannot get the new generator.

I think we need ask a more general question. Should we provide a lazy version of a generator? If yes such generator can only be implemented if RNG is splittable, because to get a new generator without a value produced it needs to be split first. That would be quite bit less efficient, but I can see it being useful in some scenarios.

@treeowl A related question for you that has been bugging me for a while. Why does atomicModifyIORef' force both the result AND the new value? IMHO it really only makes sense to force the new value because the user can always call seq or stick a bang on the produced result. This seems to me like a serious oversight in base. If it was bad design originally and was kept to avoid breakage then we should provide such function in base, so people don't have to re-implement in libraries. Would you agree?

[treeowl]

I don't understand the first paragraph, sorry. Can you explain more? As for the second, there's a note in the source for atomicMidifyIORef' that says the same thing, pretty much, that I wrote when I was adding atomicModifyIORef2# and such. As I recall, the historical reason is that it was implemented using atomicModifyIORef, which makes it hard/expensive to do the right thing. Now it's easy. Unfortunately, support for the new primops in library code is lousy.

[lehins]

I don't understand the first paragraph, sorry. Can you explain more?

Certainly. For example you want to generate an Int in the range [0,10]. In order to avoid bias we use bitmasking with rejection, which means that the value will be forced as soon as the new generator is forced. See here for the logic:

random/src/System/Random/Internal.hs

Lines 1117 to 1129 in 96957e5

	unsignedBitmaskWithRejectionM ::
	forall a g m . (Ord a, FiniteBits a, Num a, StatefulGen g m) => (g -> m a) -> a -> g -> m a
	unsignedBitmaskWithRejectionM genUniformM range gen = go
	where
	mask :: a
	mask = complement zeroBits `shiftR` countLeadingZeros (range .|. 1)
	go = do
	x <- genUniformM gen
	let x' = x .&. mask
	if x' > range
	then go
	else pure x'
	{-# INLINE unsignedBitmaskWithRejectionM #-}

With respect to this ticket:

• I recommend adding implementation of atomicModifyIORefHS to base (maybe with a better name)
• Implementing your suggestion in random with some CPP for older GHC. One way or another it is an improvement.

I don't see it being a high priority, but next major version of random should definitely include such patch