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

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?