Is it possible to uniformly generate a random infinite bitstring lazily?-CodePudding

I tried to build an RNG that uniformly randomly chooses amongst 3 items. Because, the common idiom (something like C's rand() % 3) is prone to modulo bias, and thus not uniform.

As per the notion of admissibility, my idea was to uniformly generate a random infinite bitstring, and map it through a function. The following statements shall satisfy:

The function halts for almost all inputs (This "almost all" is a well-defined notion in measure theory)
The induced probability distribution over the 3 items is uniform

As such, my sketch of code was, in Haskell:

import Data.Word

import System.Random

infixr 5 :!

data InfWord64 = Word64 :! InfWord64

execute :: (InfWord64 -> a) -> IO a
execute f = do
    let getWordString = do
        headWord <- randomIO
        tailWords <- getWordString
        pure (headWord :! tailWords)
    fmap f getWordString

randomOrderingMap :: InfWord64 -> Ordering
randomOrderingMap (headWord :! tailWords)
  | headWord < 0x5555555555555555 = LT
  | 0x5555555555555555 < headWord && headWord < 0xAAAAAAAAAAAAAAAA = EQ
  | 0xAAAAAAAAAAAAAAAA < headWord = GT
  | otherwise = randomOrderingMap tailWords

randomOrdering :: IO Ordering
randomOrdering = execute randomOrderingMap

But it doesn't work properly. It seems execute would fall into an infinite loop for every input. It seems the monadic statement headWord <- randomIO would be executed infinitely.

I would need some kind of lazy IO, but it doesn't exist for good reasons. Lazy ST RealWorld would be an alternative, but I don't see any way to use this when the random package supports only strict ST. So what's the workaround?

CodePudding user response：

Here is one possible approach:

import System.Random

randomWords :: IO [Word64]
randomWords = do
  gen <- initStdGen
  let words g = case random g of
        (w, g') -> w:words g'
  return (words gen)

which uses IO once, to initialize a random number generator, and then uses it IOlessly from that point on.

CodePudding user response：

In your code, it seems you want to work with a lazy list (or stream) of random numbers via getWordString, and then consume it in the pure function randomOrderingMap. Not an unreasonable approach to play around with, but creating such a lazy list, and actually deferring the execution of the next call to getWordString, requires lazy IO.

So if you replace the recursive call to getWordString with unsafeInterleaveIO getWordString (see docs), then it should work.

Try adding a putStrLn statement to getWordString to observe when exactly the IO action in this function is executed.

This is not necessarily the most direct or idiomatic way of solving this problem, and usually one does not reach for unsafe function, but as a learning experience this is useful.